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

    pwsnafu

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proofs by contradiction
  1. Proof by contradiction? (Replies: 12)

  2. Proof by contradiction (Replies: 1)

Loading...