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 , if is odd, then is odd.
We can assign the statements above to P (the hypothesis) and Q (the conclusion) as follows.
P: is odd
Q: 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 “ is NOT odd” or equivalently, “x is even.” This is also the same with P. The statement NOT P is the same as “ is NOT odd” or equivalently “ is even.” Therefore, the statement in the form of “if NOT Q, then NOT P” can be stated as follows.
Theorem: If is even, then is even.
If is even, then it is divisible by 2, which means that x is a product of 2 and some integer . So, .
Squaring, we have
Now, is a multiple of 2 since is an integer. Therefore, is divisible by 2 which means that it is even.
Since is even, 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.