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.

Teacher Resources

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.

Advanced30 minLesson

Printable worksheet

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.

Try it now

You want to prove by contradiction that

\sqrt{3}

is irrational. What is the correct first line?

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.

Interactive Visual

Truth Table

Select Operator

P ∧ Q

P	Q	P ∧ Q
F	F	F
F	T	F
T	F	F
T	T	T

T= TrueF= False

Interactive Sandbox

Expression Calculator

Try these:

History

No calculations yet

Practice Problems

18 problems

Problem 1 of 18

Easy

You want to prove by contradiction that $\sqrt{3}$ is irrational. What is the correct first line?

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

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.

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

Proof by Contradiction

Definition

Worked Examples

Common Mistakes

Interactive Visual

Truth Table

Interactive Sandbox

Expression Calculator

History

Practice Problems

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