Proof by Contradiction
Neil Trivedi
Teacher
Proof By Contradiction
When proving using contradiction, we are essentially assuming the negation of a 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 a statement is true, 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) Since the negation leads to a contradiction, the original statement must be true.
Here are a 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 the 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, is an odd integer greater than , which contradicts the assumption that is the greatest odd integer.
Therefore, 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,
squaring both sides,
multiplying both sides by
This implies that is divisible by , and so, by the given result, is also divisible by
Let for some
We have,
substituting
dividing both sides by
This implies that is divisible by , and so, by the given result, is also divisible by
Since both and are divisible by they are not coprime. This contradicts our assumption.
Therefore, is irrational.
No answer provided.
Challenging Question