Back to Lesson

Teacher Guide: Proof by Contradiction

Learn to prove a statement by assuming it is false and showing that this leads to something impossible, with classic proofs such as the irrationality of the square root of 2.

Present LessonShare to ClassroomView Student Page

Use this lesson with your class

Free, no student accounts needed.

Share with students

Students open the lesson and practise with instant feedback.

Printable worksheet

All practice problems on paper, with a separate answer key.

Worksheet Answer key

Class quiz

10 questions on Mathematical Proofs. Students join with a name, you see everyone's score.

For Teachers

Learning Objectives
  • Write the correct negation of a statement as the first line of a proof
  • Explain why reaching a contradiction proves the original statement
  • Reproduce the classic proofs that the square root of 2 is irrational and that there are infinitely many primes
  • Apply the pigeonhole principle to counting problems
  • Distinguish proof by contradiction from direct proof and proof by contrapositive
Prerequisites
  • • Introduction to Mathematical Proofs: hypothesis, conclusion, QED
  • • Direct Proof, including the facts that even numbers are 2k2k and that the square of an odd number is odd
  • • Negation and the contrapositive of an if-then statement
  • • Rational numbers as fractions and simplifying fractions to lowest terms
  • • Prime numbers and prime factors
Discussion Starters
  • 1. How is proof by contradiction similar to a detective ruling out a suspect?
  • 2. Why does the proof that root 2 is irrational need the words "in lowest terms"?
  • 3. Euclid's number N=2⋅3⋅5⋅7⋅11⋅13+1N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 is not prime. Does that break the proof?
  • 4. Can you think of a statement that would be very hard to prove directly but easy by contradiction?
Common Misconceptions

The negation of "all" is "none"

Remediation: Use a class example: "All students in this room wear glasses" is false as soon as ONE student does not. So its negation is "at least one student does not wear glasses".

In Euclid's proof, the number p1p2⋯pn+1p_1 p_2 \cdots p_n + 1 is always prime

Remediation: Compute 2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509. The proof only needs a prime factor outside the list, not a new prime equal to NN.

Proof by contradiction is just a direct proof with extra words

Remediation: Show a proof where the assumption is essential, like root 2: without assuming ab\frac{a}{b} exists, there is nothing to calculate with.

Differentiation Ideas

For Struggling Students:

  • • Start with the no largest even number and birth month proofs, which use only counting
  • • Practise writing negations before writing any proof
  • • Give the root 2 proof as a scaffold with blanks for each step

For On-Level Students:

  • • Prove that there is no smallest positive rational number on their own
  • • Rewrite Euclid's proof with the primes 2, 3 and 5 and check the numbers
  • • Solve pigeonhole problems with socks, birthdays and codes

For Advanced Students:

  • • Prove that the square root of 3 is irrational and explain why the same method fails for the square root of 4
  • • Prove that the sum of a rational and an irrational number is irrational
  • • Compare a contrapositive proof and a contradiction proof of the same statement
Standards Alignment
  • MP3 (CCSS.MATH.PRACTICE.MP3)

    Construct viable arguments and critique the reasoning of others

  • HSN-RN.B.3 (CCSS.MATH.CONTENT.HSN.RN.B.3)

    Explain why the sum or product of two rational numbers is rational, and that the sum of a rational number and an irrational number is irrational

  • 8.NS.A.1 (CCSS.MATH.CONTENT.8.NS.A.1)

    Know that numbers that are not rational are called irrational

Lesson Resources
  • visualTruth Table: P AND NOT P

    Students check that P AND NOT P is false in every row, the logical core of every contradiction

  • activityNegation Relay

    Teams take turns writing the negation of statements with every, some, none, greater than and infinitely many

  • worksheetClassic Proofs Scaffold

    Fill-in-the-blank versions of the root 2, infinitely many primes and pigeonhole proofs

Lesson Content

Everything students see: definition, examples, common mistakes, applications. Tap to open.

Definition

A proof by contradiction (also called an indirect proof) proves a statement PP in a roundabout way: you assume that PP is false and show that this assumption leads to something impossible. Since a correct chain of reasoning can never produce an impossibility from a true assumption, the assumption must be wrong, so PP is true.
The method has four steps:
  1. 1.Assume the negation: the first line is "Assume, for contradiction, that ¬P\neg P."
  2. 2.Reason with definitions and known facts, exactly as in a direct proof.
  3. 3.Reach a contradiction: a statement QQ and its opposite ¬Q\neg Q both hold (for example "a/ba/b is in lowest terms" and "aa and bb are both even"), or a known fact is broken (like 1=01 = 0).
  4. 4.Conclude: the assumption ¬P\neg P was false, so PP is true.
In symbols: if ¬P⇒(Q∧¬Q)\neg P \Rightarrow (Q \land \neg Q), then PP. This works because Q∧¬QQ \land \neg Q is always false. In the interactive truth table further down this page, choose NOT to see that ¬P\neg P is always the opposite of PP, then choose AND: in the two rows where QQ is the opposite of PP (F, T and T, F), P∧QP \land Q is F. So P∧¬PP \land \neg P is F in every row.
Writing the negation correctly is the most important line of the proof:
  • "2\sqrt{2} is irrational" becomes "2\sqrt{2} is rational"
  • "There are infinitely many primes" becomes "There are only finitely many primes"
  • "There is no largest even number" becomes "There is a largest even number"
  • "x>5x > 5" becomes "x≤5x \le 5"
  • "Every ... has the property" becomes "At least one ... does not have the property"
Contradiction or contrapositive? A proof by contrapositive (previous lesson) proves "if pp, then qq" by assuming only ¬q\neg q and working toward one fixed target, ¬p\neg p. A proof by contradiction assumes the whole statement is false (for an if-then statement: pp and ¬q\neg q together) and may end at any impossibility at all.

Worked Examples

Prove that there is no largest even number.
1

Write the negation as the first line

Assume, for contradiction, that there is a largest even number NN → Assumption: NN is even and N≥N \ge every even number
2

Use the definition of even

N=2kN = 2k for some integer kk, so N+2=2k+2=2(k+1)N + 2 = 2k + 2 = 2(k + 1) → N+2N + 2 is even
3

Compare the two numbers

N+2>NN + 2 > N → An even number larger than NN exists
4

Spot the contradiction and conclude

NN is the largest even number, yet N+2N + 2 is a larger even number → The assumption is false

Common Mistakes

Negating "There are infinitely many primes" as "There are no primes"

Why it's wrong: The opposite of "infinitely many" is not "none". The negation must cover every case where the statement fails, and that is "only finitely many".

Correct: Assume "There are only finitely many primes". In the same way, the negation of "every prime is odd" is "at least one prime is not odd", not "every prime is even".

Negating x>5x > 5 as x<5x < 5

Why it's wrong: The case x=5x = 5 is forgotten. If the proof only rules out x<5x < 5, the number 55 is still possible.

Correct: The negation of x>5x > 5 is x≤5x \le 5, and the negation of x≥5x \ge 5 is x<5x < 5.

Forgetting "in lowest terms" in the proof that 2\sqrt{2} is irrational

Why it's wrong: Without that condition, finding that aa and bb are both even is no contradiction at all: 42\frac{4}{2} has an even numerator and denominator.

Correct: Write 2=ab\sqrt{2} = \frac{a}{b} in lowest terms. Every fraction can be reduced, so this costs nothing, and it is exactly the fact the proof later breaks.

Calling a surprising result a contradiction

Why it's wrong: A result that looks strange (a very large number, a fraction you did not expect) is not impossible. A contradiction must clash with the assumption or with a known fact.

Correct: Name the two statements that clash, for example "rr is the smallest" and "r2<r\frac{r}{2} < r", and then write the conclusion.

Why It Matters

Some of the most famous results in mathematics are most naturally proved by contradiction:
  • Irrational numbers: the Greeks proved that 2\sqrt{2} is not a fraction about 2,500 years ago, which changed how people thought about numbers
  • Prime numbers: Euclid's proof that the primes never run out is still used in every number theory course
  • Computer science: the pigeonhole principle explains why two files can get the same short fingerprint (a hash collision) and why perfect compression of every file is impossible
  • Puzzles: solving a Sudoku often means saying "if this cell were 5, two 5s would end up in the same row, so it is not 5"
  • Everyday reasoning: detectives and doctors rule out possibilities by showing that they lead to something impossible
Whenever a statement says something does NOT exist (no largest number, no fraction equal to 2\sqrt{2}), proof by contradiction is usually the natural tool.

Real World Applications

Matching Socks in the Dark

The pigeonhole principle, proved by contradiction, tells you the smallest number of items that guarantees a repeat.

Example:

A drawer holds black, white and grey socks. If you could take 4 socks that were all different colors, you would need 4 colors, but there are only 3. So 4 socks always contain a matching pair.

1Try It Yourself

A drawer holds loose socks in 5 different colors, and it is too dark to see them.

How many socks must you take to be sure that two have the same color?

Step 1: Write the mathematical expression

Number of colors plus one:

Hash Collisions in Computer Science

Computers give files short codes called hashes. Because there are more possible files than codes, two different files must sometimes share a code.

Example:

A system gives every file a code from 00 to 99. Among 101 files, assuming all codes are different would need 101 codes, but there are only 100, so two files share a code.

2Try It Yourself

A system gives every file a 3-digit code from 000 to 999.

How many files guarantee that two of them have the same code?

Step 1: Write the mathematical expression

Number of codes plus one:

Why Calculators Never Show the Exact Square Root of 2

Because $\sqrt{2}$ is irrational, its decimal expansion never ends and never repeats. Any decimal on a screen is only an approximation, which engineers must keep in mind when they compute diagonals.

Example:

A square tile with side 1 m has a diagonal of 2≈1.4142\sqrt{2} \approx 1.4142 m. The value 1.4142 is close, but not exact.

3Try It Yourself

A calculator shows 2≈1.4142\sqrt{2} \approx 1.4142.

Check that 1.4142 is not exactly the square root of 2.

Step 1: Write the mathematical expression

Square the decimal:

Key Takeaways

  • 1A proof by contradiction assumes the statement is false and shows that this leads to something impossible
  • 2The first line is the correct negation: "infinitely many" becomes "only finitely many", x>5x > 5 becomes x≤5x \le 5, "every" becomes "at least one ... not"
  • 3A contradiction means two statements that cannot both be true, such as Q∧¬QQ \land \neg Q, which is false in every row of a truth table
  • 4Classic results proved this way: 2\sqrt{2} is irrational, there are infinitely many primes, there is no largest even number and no smallest positive rational number
  • 5The pigeonhole principle: if more than nn objects go into nn boxes, some box holds at least two objects
  • 6Proof by contrapositive proves "if not q, then not p" directly, while proof by contradiction assumes the whole statement is false and looks for any impossibility

Frequently Asked Questions

Why is it enough to reach a contradiction?

Correct reasoning from true statements only ever produces true statements. If we reach something impossible, at least one starting point was false, and the only starting point we added ourselves was the assumption ¬P\neg P. So ¬P\neg P is false and PP is true.

When should I use proof by contradiction?

It is a good choice when the statement says something does not exist (no largest number, no fraction equal to 2\sqrt{2}) or that there are infinitely many of something. In those cases assuming the opposite gives you a concrete object to work with.

Is a proof by contradiction the same as a proof by contrapositive?

No. A proof by contrapositive proves "if not q, then not p" directly and ends at "not p". A proof by contradiction assumes the statement is false and may end at any impossibility. Every proof by contrapositive can be rewritten as a proof by contradiction, but not every proof by contradiction is a proof by contrapositive.

What does QED mean, and what is "reductio ad absurdum"?

QED (quod erat demonstrandum, "which was to be shown") marks the end of a proof. Reductio ad absurdum, "reduction to the absurd", is the Latin name of proof by contradiction.

Glossary

Proof by contradiction
A proof that assumes the statement is false and derives an impossibility, so the statement must be true (also called indirect proof)
Contradiction
A pair of statements that cannot both be true, such as QQ and ¬Q\neg Q; the statement Q∧¬QQ \land \neg Q is always false
Negation
The opposite of a statement, written ¬P\neg P; it is true exactly when PP is false
Irrational number
A real number that cannot be written as a fraction ab\frac{a}{b} of integers, for example 2\sqrt{2}
Pigeonhole principle
If more than nn objects are placed into nn boxes, at least one box contains two or more objects

Formula Card

Proof by contradiction

¬P⇒(Q∧¬Q)   so   P\neg P \Rightarrow (Q \land \neg Q) \;\text{ so }\; P

If assuming not P leads to a contradiction, then P is true

A contradiction is always false

Q∧¬Q=FQ \land \neg Q = F

A statement and its negation can never both be true

Pigeonhole principle

n+1 objects in n boxesn + 1 \text{ objects in } n \text{ boxes}

At least one box receives two or more objects

More in This Topic

Introduction to Mathematical Proofs

Advanced25 min

Direct Proof

Advanced25 min

Two-Column Proofs

Intermediate25 min

Paragraph Proofs

Advanced30 min