Proof by Contradiction
Neil Trivedi
Teacher
Proof By Contradiction
When proving using contradiction, we are essentially observing the converse of statement (opposite statement) and proving that if that were to be true, it would lead to a contradiction.
A statement is either true or false. So, if we would like to prove the truth behind a statement, we use these steps:
1) Assume the statement is false (i.e., negating the statement).
2) Go on to prove that it is impossible for the false statement to be true (the contradiction).
3) If the false statement makes no sense, then clearly the original statement was in fact true.
Here are few examples of negating statements:
• The negation of “nobody likes oranges” is “at least one person likes oranges.”
• The negation of “ is irrational” is “ is rational.”
Example 1:
Prove by contradiction that there is no greatest odd integer.
Step 1: Assume that statement is false (i.e., negating the statement).
Assume there is a greatest odd integer,
Step 2: Prove that it is impossible for the false statement to be true, and thus, our original statement must be true.
Since is odd, is also an odd number.
However, which contradicts our assumption.
there is no greatest odd integer.
No answer provided.
Example 2:
Prove by contradiction that is irrational. You may assume that if is divisible by then is divisible by
Step 1: Assume the statement is false (i.e., negating the statement).
Assume is rational.
Step 2: Prove that it is impossible for the false statement to be true, and thus, our original statement must be true.
Since is rational, we can write where and and are coprime (the HCF of and is meaning the fraction is in its simplest form).
We have,
square both sides,
multiply both sides by
This implies that is a multiple of and by our assumption, implies that is also a multiple of
Let for some
We have,
substitute
divide both sides by
This implies that is a multiple of and by our assumption, implies that is also a multiple of
Since both and are multiples of they are not coprime. This contradicts our assumption.
is irrational.
No answer provided.
Challenging Question