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 min18 problems
Practice Problems

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.

Try it now

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

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.

Interactive Visual

Truth Table

P ∧ Q
PQP ∧ Q
FFF
FTF
TFF
TTT

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

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.
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.
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.
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.
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

Today's challengeOne problem, three tries

More in This Topic

Introduction to Mathematical Proofs

Advanced25 min

Direct Proof

Advanced25 min

Two-Column Proofs

Intermediate25 min

Paragraph Proofs

Advanced30 min