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!

Proofs by contradiction

  1. Jul 14, 2011 #1
    Sometimes I find that while a proof can be carried out "by contradiction", this is a pretty sloppy way of proving the desired statement. I wonder if the "←" direction of the following proof is sound presentation of proof by contradiction.

    Statement. An integer is even if and only if its square is even.

    Proof. First suppose the integer n is even. Then for some k ∈ ℤ, n = 2k and n2 = 4k2 = 2(2k2), so n2 is even. Conversely, if n2 is even, suppose n is odd. Then n = 2k + 1 with k ∈ ℤ. Then n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1, so n2 is odd; a contradiction. Thus n must be even. □

    Is it messy to prove "n2 is even ⇒ n is even" (*) via contradiction? It seems like a jumble of words in this case. I didn't actually rely on the assumption "n2 is even" when directly showing that n = 2k + 1 leads to contradict that. I feel like all I've done is shown that the square of an odd integer is also odd. It seems like a messy way to go about it, there should be a more well-crafted proof for that.

    In my opinion the next proof is a strong example of proof by contradiction:

    Statement. Every integer greater than 1 can be written as a product of prime numbers.

    Proof. Suppose towards contradiction that the result is false. Then let n > 1 be the smallest integer that cannot be written as a product of primes. n is not prime, so n = pq for some integers p, q with 1 < p ≤ q < n. Since p and q are both smaller than n, it must be possible to factor them into primes; thus n can be written as a product of primes after all, a contradiction. □

    The difference between this and the previous statement proven is that the assumption made (towards contradiction) directly contradicts itself: we assumed n cannot be written as a product of primes, and showed that this implies that it indeed can be. I tend to think that presenting it this way really strikes at the core of proving by contradictions.

    For the first proof about even numbers, I think there's a better way to carry that out. It just seemed to work when worded as a "proof by contradiction", but it's actually a simpler proof in disguise.
  2. jcsd
  3. Jul 14, 2011 #2


    User Avatar
    Science Advisor

    I removed the first part of the proof. This is more of a contrapositive proof than contradiction:

    n is odd => n2 is odd

    is the same thing as

    n is even <= n2 is even.

    Amusingly, in the http://en.wikipedia.org/wiki/Proof_by_contrapositive" [Broken] on the topic uses this example.
    Last edited by a moderator: May 5, 2017
  4. Jul 14, 2011 #3
    LOL, oh wow yeah that is indeed amusing.

    I guess the kinks I'm trying to work out are regarding the presentation of the proof. It seemed pretty ugly when shown as a "proof by contradiction". Stating it as showing the contrapositive works a lot nicer there, thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook