1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

MAT385-Proof by contraposition

  1. Feb 17, 2014 #1
    1. The problem statement, all variables and given/known data
    28. Prove the given statement:
    If the product of two integers is not divisible by an integer n, then neither integer is divisible by n.

    2. Relevant equations
    Proof by contraposition

    3. The attempt at a solution
    Originally the problem states:
    (xy/n)'→(x/n /\ y/n)'
    This seems like a handy time for contraposition because it makes more intuitive sense that:
    (x/n /\ y/n) [itex]\rightarrow[/itex] (xy/n^2)

    To which I think
    Where it gets hazy is where to go from here. If I wanted to do proof by induction then I would need some guidance on what to aim for. Would it be:
    Any advice/guidance would be appreciated.
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution

    Attached Files:

  2. jcsd
  3. Feb 17, 2014 #2
    Assuming ##p'## is meant to denote the negation of ##p## and ##x/n## denotes "##x## is divisible by ##n##" (which is almost universally denoted ##n|x## in my experience), the form of the original claim is ##(xy/n)'\rightarrow[(x/n)'\land( y/n)']##, not what you have written. Or equivalently, by DeMorgan, ##(xy/n)'\rightarrow(x/n\lor y/n)'##.

    The contrapositive, which I agree is much easier to prove, would be ##(x/n\lor y/n)\rightarrow (xy/n)##. You don't need anything fancy (like induction) to prove this. Just write down the definition of ##x/n## and follow your nose.
  4. Feb 17, 2014 #3
    I see. Seeing the implication differently does change quite a bit. Thank you.
  5. Feb 18, 2014 #4
    Is this sufficient?

    Is the attached sufficient. By write the definition of x, did you mean x=kn?

    Attached Files:

  6. Feb 18, 2014 #5
    Not as a proof of the given statement. Some of it looks like good scratch work that might lead to a proof and perhaps get incorporated into that proof. Other parts of it (like whatever is going on off to the side with ##k^2n^2=k^2n## and the fact that you have essentially stated that ##x=y## when that isn't necessarily true and the fact that you have assumed that both ##x/n## and ##y/n## when that isn't necessarily true) need to be discarded.

    Also, don't be afraid to use words in your proof. A good proof really should read like what we would consider "standard" prose written in English (or whatever language you speak) with mathematical notation used to make the proof more readable. Look at the statement that you're proving; the only mathematical notation used is the letter ##n## so that the second half of the statement could refer to that integer by name.

    Alright. So you're reading and writing mathematical proofs, which means you need to read carefully and also choose your words carefully.

    I said
    I'm not even sure what "the definition of x" would even mean in this problem.

    Now, ##x=kn## is part of the definition of ##x/n##, but there's more. the full definition should look something like

    ##x/n## if and only if there is an integer ##k## such that ##x=kn##.

    I know it might seem like I'm being a stickler, but all of the definition is important, not just the equation.

    When you start off by writing "If ##x/n##, then there is an integer ##k## such that ##x=kn##," and you're trying to prove something about ##xy##, what's the next thing you might say? Oh, hey, "then ##xy=kny##." And if what you're trying to say about ##xy## is that it is also divisible by ##n## ...
  7. Feb 18, 2014 #6

    Let x be divisible by n:
    xy is a multiple of n, so xy is divisible by n.
    Proof by contraposition.

    This is my first introduction to formal logic and proofs (MAT385) aside from proofs like those found in calc III. Thus, I thank you for the pointers on specifics.
  8. Feb 18, 2014 #7
    It looks like you have the basic gist of the argument, though I'd point out that you haven't actually proven the contrapositive of the original claim.

    Here's how I might write it up, just as a guide.

    (*) There isn't a math teacher/grader on the planet who won't love you for writing out the problem statement/claim before the solution. Do it. Seriously, do it. Be careful with paraphrasing the assigned problem, but do it.

    (**) I've always been advised to let the proof reader know ahead of time what sort of proof they're about read in most instances that aren't straightforward, direct proofs. When you jump right in with "let x be divisible by n", the reader's fist though is "Why?! That's not one of the assumptions, and is actually the OPPOSITE of what you're trying to prove!" And then they read further and go "Oh, ok. I get it now." But for a second, they were confused and annoyed. You don't want the grader to be confused and annoyed by something you wrote, not even for a moment. It can also serve as a reference for YOU for what you need to get done in the proof; i.e. this is what I said I was gonna do, and I'm not done until I do it.

    (***) The proof of this sentence is almost the same as the previous proof; we're just switching around the roles of some of the letters. Be very careful with using "similarly" (or "trivial" or "obvious"). When in doubt, write it out.

    My advisor always says, with regards to homework-style proofs, (1) tell me what you're going to do (i.e. the claim) (2) tell me how you're going to do it (3) do it (4) let me know when you're done, and, if it's not too much trouble, remind me what you did.

    Also, I would encourage you to read out loud what you have written. Or rewrite what you have written without using mathematical notation. If it sounds silly, you may want to jazz it up a bit (just a bit) with some exposition. A few "so"s and "then"s and "therefore"s go a long way.

    Finally, read a lot of proofs. And watch your professor(s) do proofs. Listen to what they say as much (if not more) than you read what they write. Most of the proof is coming out of their mouth, and probably doesn't end up on the blackboard. I learned a lot about the proof-writing process just by seeing other people's proofs.
  9. Feb 18, 2014 #8


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You're making this way too complicated!

    The first thing to do is write down the contraposition in plain English. Then, you should be almost there! To help you a bit, I've put some variables in:

    "If x = yz is the product of two integers and x is not divisible by an integer n, then neither integer y nor z is divisible by n."

    Try to write down the contraposition of that statement.
  10. Feb 18, 2014 #9
    Cool. Thanks for all the help. I'm a chemistry major who keeps taking math classes for some reason.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Threads - MAT385 Proof contraposition Date
Lim sup proof Mar 12, 2018
Real Analysis Proof Mar 11, 2018
Proof that a recursive sequence converges Mar 8, 2018
Bland rule proof linear programming Mar 7, 2018
Prove Using the Method of Contrapositive Jan 28, 2016