A proof by contradiction assumes the negation of the claim and reaches something impossible, so the claim must be true; this is how we show that 2
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
write a proof by contradiction;
prove that 2 is irrational and that there are infinitely many primes;
split a proof into cases that cover every possibility;
use the pigeonhole principle.
The idea of a proof by contradiction
A detective says: "Suppose the butler did it. Then he was in the kitchen at nine. But at nine he was on a train. That is impossible. So the butler did not do it."
A proof by contradiction works the same way.
Assume that the claim is false.
Reason correctly from that assumption.
Reach a statement that is impossible, such as q∧∼q.
So the assumption was wrong, and the claim is true.
It works because a true assumption cannot lead, by valid steps, to a false statement.
The square root of 2 is irrational
Claim.2 is not a rational number.
Proof.
Suppose, for a contradiction, that 2=ba. Here a and b are whole numbers, b=0, and the fraction is in lowest terms.
Squaring gives a2=2b2. So a2 is even.
If a2 is even, then a is even. We proved this in the last lesson. Write a=2c.
Then 4c2=2b2, so b2=2c2. So b2 is even, and b is even.
Now a and b are both even, so the fraction was not in lowest terms. This contradicts step 1.
So 2 is irrational.
There are infinitely many primes
Claim. There is no largest prime number.
Proof.
Suppose there are only finitely many primes: p1,p2,…,pk.
Let N=p1p2⋯pk+1.
Dividing N by any pi leaves remainder 1. So no pi divides N.
But N>1, so N has a prime factor. That prime is not in the list.
This contradicts step 1. So there are infinitely many primes.
N itself need not be prime. With the primes 2,3,5 and 7, N=211, which is prime. The proof only needs a prime factor outside the list.
Proof by cases
Sometimes the possibilities split into a few cases. Prove the claim in each one. The cases must cover everything.
Claim. For every integer n, n2+n is even.
Case 1: n is even. Then n2+n=n(n+1) has the even factor n.
Case 2: n is odd. Then n+1 is even, so n(n+1) is even.
Every integer is even or odd, so the claim is proved.
Claim. For every integer n, n2 leaves remainder 0 or 1 on division by 3.
Every integer is 3k, 3k+1 or 3k+2.
(3k)2=3(3k2): remainder 0.
(3k+1)2=3(3k2+2k)+1: remainder 1.
(3k+2)2=3(3k2+4k+1)+1: remainder 1.
So a number such as 3m+2 is never a perfect square.
The pigeonhole principle
If more than k letters go into k boxes, some box gets at least two. The proof is a contradiction: if every box had at most one, there would be at most k letters.
The general form: if more than kq objects go into k boxes, some box gets at least q+1.
Example. Among any 13 people, two were born in the same month. There are 12 months and 13 people.
Practise with new numbers
Try it in Python
A computer cannot check every fraction, but it can search far. The program looks for whole numbers with a2=2b2 for b up to 10000 and finds none, as the proof says. Then it checks the cases for squares on division by 3.
Common mistakes
Not stating the assumption. Begin with "Suppose, for a contradiction, that ...".
Assuming the wrong negation. The negation of "2 is irrational" is "2 is rational", written as a fraction in lowest terms.
Cases that miss something. "n>0 and n<0" forgets n=0.
Thinking N=p1⋯pk+1 is always prime. It need not be. It only has a prime factor outside the list.
Remember these
Contradiction: assume the claim is false, reach the impossible.
2 is irrational; there are infinitely many primes.
Cases must cover every possibility.
More than kq objects in k boxes put q+1 in some box.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
What do you assume first, to prove "there is no smallest positive rational number" by contradiction?
Prove by cases that n3−n is even for every integer n.
Why does the proof that 2 is irrational need "lowest terms"?
Is 3m+2 ever a perfect square, for an integer m?
A drawer has socks of 5 colours. How many must you take out to be sure of two of the same colour?
References
NCERT, Mathematics Textbook for Class XII, Part II, Appendix 1, Proofs in Mathematics.
Richard Hammack, Book of Proof, third edition, Chapter 6, Proof by Contradiction.
Enroll free in Valid Arguments and Methods of Proof
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.