Proof by Contradiction: Odd and Its Square

We have had several examples on proof by contradiction in this blog like irrationality of square root of 3 and the sum of root of 2 and root of 3. In this post, we will have another detailed example.

In proof by contradiction, we want to change the statement “if P then Q” to “if NOT Q then NOT P.” These two statements are equivalent, so if we can prove the latter, then we have proved the former. Consider the following theorem.

Theorem: For any integer x, if x^2 is odd, then x is odd.

We can assign the statements above to P (the hypothesis) and Q (the conclusion) as follows.

P: x^2 is odd

Q: x is odd.

If we are going to change this statement to “if NOT Q then NOT P,” then, we have to find the opposite of P and opposite of Q. 

For Q, what is the opposite of “x is odd”? This can mean “x is NOT odd” or equivalently, “x is even.”  This is also the same with P. The statement NOT P is the same as “x^2 is NOT odd” or equivalently “x^2 is even.” Therefore, the statement in the form of  “if NOT Q, then NOT P” can be stated as follows.

Theorem: If x is even, then x^2 is even.

Proof

If x is even, then it is divisible by 2, which means that x is a product of 2 and some integer k. So, x = 2k.

Squaring, we have

x^2 = (2k)^2 = 4k^2.

Now, 4k^2 is a multiple of 2 since k is an integer. Therefore, 4k^2 is divisible by 2 which means that it is even.

Since 4k^2 is even, x^2 is also even and this proves the theorem.

Notice that the restated theorem (or the contrapositive) is a lot easier to prove that its equivalent statement above.

Leave a Reply