Proof by contradiction
Studying this course? Keep your progress in one place.
Key facts
- To prove by contradiction, assume the negation of and show this is impossible.
- A correct negation is the key: "all" becomes "some ... does not".
- is irrational: assume in lowest terms, then and are both even.
- There are infinitely many primes: has a prime factor not on the list.
- State the assumption, each step with a reason, the contradiction and the conclusion.
The method
To prove a statement by contradiction, assume the opposite and show that this is impossible.
Write the conclusion explicitly: "this is a contradiction, so the assumption is false, hence ...".
The contradiction may be with the assumption itself or with something already known.
- 1
Assume the negation
Assume is false, that is, assume the negation of .
- 2
Reason logically
Use correct logical steps from that assumption.
- 3
Reach a contradiction
Something impossible, such as a number that is both odd and even.
- 4
Conclude
The assumption was wrong, so is true.
To prove by contradiction that "there is no largest even integer", what do you assume first?
Writing the negation
A correct negation is the key to a correct proof. Write the statement with "all" and "there exists", and negate each.
A rational number can be written as with , integers, . In lowest terms, and have no common factor greater than . Taking lowest terms is what produces the contradiction in irrationality proofs.
- 1
Write the statement in full
with “all” or “there exists”
- 2
Swap the quantifier
“all” becomes “there exists”, and the reverse
- 3
Negate the property
for example irrational becomes rational
- 4
Assume the negation is true
this is the start of the contradiction proof
Statement
- is irrational
- There are no integers with property
- There are finitely many primes
- All satisfy
Negation
- is rational
- There exist integers with
- There are infinitely many primes
- Some does not satisfy
What is the negation of "all prime numbers are odd"?
√2 is irrational
Assume in lowest terms. Squaring shows and are both even, contradicting lowest terms.
The same method proves irrational: gives , so (as is prime), and then .
- 1
Assume
in lowest terms
- 2
Square
, so is even
- 3
Substitute
gives , so is even
- 4
Contradict
p and q share the factor 2
Worked example
Prove that is irrational.
- 1
Assume with , integers and no common factor (lowest terms).
- 2
Square both sides: , so is even.
- 3
So is even, because an odd number squared is odd.
- 4
Write . Then , so and is even.
- 5
So is even. Then and share the factor .
In the proof for , why does imply ?
Infinitely many primes
Assume finitely many primes, multiply them and add 1. The result has a prime factor not on the list.
Assume there are finitely many primes , and let . Dividing by any leaves remainder , so no divides . But is either prime or has a prime factor, which is not on the list.
need not itself be prime: , with both factors new primes.
- 1
Assume
finitely many primes,
- 2
Build N
- 3
Remainder 1
no divides
- 4
Contradict
N has a prime factor not on the list
If the "list of all primes" is 2, 3, 5, what is N, and what does it show?
Unfamiliar proofs
Typical approaches use parity, a known irrational, or factorising. Always state the assumption, each step with a reason, the contradiction and the conclusion.
To show is irrational, assume , so : an odd number equal to an even one.
To show is irrational, assume it equals , so , rational: a contradiction.
To show has no positive integer solutions, forces , so .
- 1
Assume log₂3 = p/q
with p, q positive integers
- 2
Rearrange
3^q = 2^p
- 3
Compare parity
3^q is odd but 2^p is even
- 4
Contradiction
so log₂3 is irrational
Parity
- gives
- Odd equals even
Known irrational
- is rational
Factorising
- Forces
Assume with integers , and . Which statement leads to the contradiction?
Try an exam question
Prove by contradiction that there are no positive integers and such that .
[4 marks]
- [1]Assumes there exist positive integers and with .
- [1]Factorises: .
- [1]Both factors are positive integers with product , so .
- [1]Then , contradicting positive, so no such integers exist.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which of these is the correct first line of the proof?
1 mark, marked against the mark scheme
Which of these is the correct first line of the proof?
1 mark, marked against the mark scheme