Proof by contradiction
Studying this course? Keep your progress in one place.
Key facts
- Assume the opposite of what you want to prove, then reach a contradiction.
- The assumption must be the faulty step, so the original statement is true. Always write a concluding sentence.
- A rational number is with integers , ; assume it is in lowest terms.
- If is even then is even, because an odd number squared is odd.
- Negate carefully: the opposite of "no integers exist" is "there exist integers".
The method
Assume the opposite, work logically to something impossible, then conclude the assumption is false so the statement is true.
In proof by contradiction you assume the opposite of what you want to prove, then use correct steps to reach something impossible: a contradiction.
Every step was valid, so the faulty item must be the assumption, and the original statement is true.
- State the assumption clearly, such as "Assume is rational".
- Work logically from it.
- Reach a contradiction, such as a number that is both even and odd.
- Conclude: "this is a contradiction, so the assumption is false".
- 1
Assume the opposite
of what you want to prove
- 2
Work logically
every step must be valid
- 3
Reach a contradiction
something impossible
- 4
Conclude
the assumption is false, so the statement is true
To prove is irrational by contradiction, what do you assume first?
Rational and irrational numbers
A rational number is in lowest terms. Contradiction proofs about irrationals use this and facts about even and odd squares.
A rational number can be written as with integers and . An irrational number cannot.
Any rational number can be written in lowest terms, where and share no factor other than 1. Contradiction proofs about irrationals rely on this, so assume it at the start. Without it, "both even" is not a contradiction.
If is even then is even.
The same idea works for multiples of 3: if then is not a multiple of 3.
| Rational | Irrational | |
|---|---|---|
| Written as | with integers, | cannot be written as |
| Examples | , 0.75, 5 | , |
Rational
- Written as:
- with integers,
- Examples:
- , 0.75, 5
Irrational
- Written as:
- cannot be written as
- Examples:
- ,
Worked example
Show that if is even then is even.
- 1
Suppose is odd, so for some integer .
- 2
Then .
- 3
This has the form , so is odd.
Why must be assumed to be in lowest terms?
The irrationality of root 2
Assume in lowest terms. Both and turn out even, contradicting lowest terms.
Assume with integers in lowest terms.
Square: , so . Hence is even, so is even. Write .
Then , so , which is even, so is even.
Now and are both even, so they share the factor 2. This contradicts lowest terms. Hence is irrational.
The same pattern proves irrational, using multiples of 3.
- 1
Assume
in lowest terms
- 2
so is even
- 3
is even
write
- 4
so is even
- 5
Contradiction
both even, so not in lowest terms
In the proof, what is the contradiction?
The infinity of primes
Assume a finite list of primes, multiply them and add 1. The result gives a prime not in the list.
Assume there are finitely many primes .
Let . Dividing by any leaves remainder 1, so no divides .
Either is prime, or it has a prime factor. In both cases there is a prime not in the list. This contradicts the assumption that the list held all primes, so there are infinitely many primes.
need not be prime itself. Its factors are new primes.
- 1
Assume
a finite list of all primes
- 2
Form N
the product of the list, plus 1
- 3
Remainder 1
no prime in the list divides N
- 4
New prime
N or a prime factor of N is not in the list: contradiction
Worked example
Take the first six primes 2, 3, 5, 7, 11, 13. Is prime?
- 1
The product is 30030, so .
- 2
Dividing by any of 2, 3, 5, 7, 11, 13 leaves remainder 1.
- 3
But , so is not prime.
What does leave when divided by any prime in the list?
Unfamiliar proofs
Negate it carefully, translate the assumption into algebra, then manipulate until you reach a contradiction.
Strategy for a new statement: (1) negate it carefully, (2) translate the assumption into algebra, (3) manipulate to a contradiction.
Typical contradictions: even equals odd; a fraction not in lowest terms; an integer between 0 and 1; a number divisible by 5 that equals 1.
If you are stuck, write down exactly what the contradiction would look like and work towards it.
- 1
Negate the statement
write exactly what "not true" means
- 2
Translate into algebra
for example a rational number is a/b in lowest terms
- 3
Manipulate
use only valid steps
- 4
Reach a contradiction
so the assumption was false and the statement is true
| Statement | Negation | |
|---|---|---|
| Example 1 | is irrational | is rational |
| Example 2 | there are no integers with | there are integers with |
Statement
- Example 1:
- is irrational
- Example 2:
- there are no integers with
Negation
- Example 1:
- is rational
- Example 2:
- there are integers with
Worked example
Prove that is irrational.
- 1
Assume with positive integers.
- 2
Then , so .
- 3
is even and is odd.
What is the negation of "there are no integers with "?
Try an exam question
Prove by contradiction that is irrational.
[4 marks]
- [1]Assume with integers in lowest terms.
- [1], so is a multiple of 3, so is a multiple of 3. Write .
- [1], so and is a multiple of 3.
- [1] and share the factor 3, contradicting lowest terms, so is irrational.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What further assumption must be made at the start of the proof?
1 mark, marked against the mark scheme
What further assumption must be made at the start of the proof?
1 mark, marked against the mark scheme