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 LessonView 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 $2k$ 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 \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 $p_1 p_2 \cdots p_n + 1$ is always prime

Remediation: Compute $2 \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 $N$ .

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 $\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

P

in a roundabout way: you assume that

P

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

P

is true.

The method has four steps:

1.Assume the negation: the first line is "Assume, for contradiction, that $\neg P$ ."
2.Reason with definitions and known facts, exactly as in a direct proof.
3.Reach a contradiction: a statement $Q$ and its opposite $\neg Q$ both hold (for example " $a/b$ is in lowest terms" and " $a$ and $b$ are both even"), or a known fact is broken (like $1 = 0$ ).
4.Conclude: the assumption $\neg P$ was false, so $P$ is true.

In symbols: if

\neg P \Rightarrow (Q \land \neg Q)

, then

P

. This works because

Q \land \neg Q

is always false. In the interactive truth table further down this page, choose NOT to see that

\neg P

is always the opposite of

P

, then choose AND: in the two rows where

Q

is the opposite of

P

(F, T and T, F),

P \land Q

is F. So

P \land \neg P

is F in every row.

Writing the negation correctly is the most important line of the proof:

" $\sqrt{2}$ is irrational" becomes " $\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 > 5$ " becomes " $x \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

p

, then

q

" by assuming only

\neg q

and working toward one fixed target,

\neg p

. A proof by contradiction assumes the whole statement is false (for an if-then statement:

p

and

\neg q

together) and may end at any impossibility at all.

Worked Examples

Prove that there is no largest even number.

Write the negation as the first line

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

Use the definition of even

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

Compare the two numbers

$N + 2 > N$ → An even number larger than $N$ exists

Spot the contradiction and conclude

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

Answer: The assumption leads to a contradiction, so there is no largest even number. QED

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 > 5$ as $x < 5$

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

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

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

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

Correct: Write $\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 " $r$ is the smallest" and " $\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 $\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

\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 $\sqrt{2} \approx 1.4142$ m. The value 1.4142 is close, but not exact.

3Try It Yourself

A calculator shows $\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 > 5$ becomes $x \le 5$ , "every" becomes "at least one ... not"
3A contradiction means two statements that cannot both be true, such as $Q \land \neg Q$ , which is false in every row of a truth table
4Classic results proved this way: $\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 $n$ objects go into $n$ 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

\neg P

. So

\neg P

is false and

P

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

\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 $Q$ and $\neg Q$ ; the statement $Q \land \neg Q$ is always false
Negation: The opposite of a statement, written $\neg P$ ; it is true exactly when $P$ is false
Irrational number: A real number that cannot be written as a fraction $\frac{a}{b}$ of integers, for example $\sqrt{2}$
Pigeonhole principle: If more than $n$ objects are placed into $n$ boxes, at least one box contains two or more objects

Formula Card

Proof by contradiction

\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 \land \neg Q = F

A statement and its negation can never both be true

Pigeonhole principle

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

At least one box receives two or more objects

Teacher Guide: Proof by Contradiction

Use this lesson with your class

For Teachers

For Struggling Students:

For On-Level Students:

For Advanced Students:

Lesson Content

Definition

Worked Examples

Common Mistakes

Why It Matters

Real World Applications

Matching Socks in the Dark

Hash Collisions in Computer Science

Why Calculators Never Show the Exact Square Root of 2

Key Takeaways

Frequently Asked Questions

Glossary

Formula Card

Proof by contradiction

A contradiction is always false

Pigeonhole principle

More in This Topic

Introduction to Mathematical Proofs

Direct Proof

Two-Column Proofs

Paragraph Proofs