Proof by Contradiction

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.

There Is No Largest Even Number

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

Two of 13 People Share a Birth Month

Prove that in any group of 13 people, at least two were born in the same month.

Write the negation: Assume, for contradiction, that all 13 people were born in different months = Assumption: 13 different months

Count what the assumption needs: 13 people with no repeated month need at least 13 different months = At least $13$ months needed

Compare with the facts: A year has only $12$ months, and $13 > 12$ = Impossible

Conclude: The assumption is false = Two people share a month

Answer: At least two of the 13 people were born in the same month. This is the pigeonhole principle: 13 pigeons, 12 holes. QED

There Is No Smallest Positive Rational Number

Prove that there is no smallest positive rational number.

Write the negation: Assume, for contradiction, that $r$ is the smallest positive rational number = Assumption: $r > 0$, $r$ rational, nothing smaller

Build a new number: If $r = \frac{a}{b}$, then $\frac{r}{2} = \frac{a}{2b}$, a fraction of integers = $\frac{r}{2}$ is rational

Check its size: $r > 0$, so $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ is positive and smaller than $r$

Spot the contradiction and conclude: $r$ was the smallest, yet $\frac{r}{2}$ is smaller = The assumption is false

Answer: There is no smallest positive rational number. For example, if someone claims $\frac{1}{1000}$, then $\frac{1}{2000}$ is smaller. QED

The Square Root of 2 Is Irrational

Prove that $\sqrt{2}$ is irrational.

Write the negation: Assume, for contradiction, that $\sqrt{2}$ is rational: $\sqrt{2} = \frac{a}{b}$ with integers $a, b$, $b \neq 0$, and the fraction in lowest terms = $a$ and $b$ have no common factor

Square both sides: $2 = \frac{a^2}{b^2}$, so $a^2 = 2b^2$ = $a^2$ is even

Conclude that a is even: If $a$ were odd, $a^2$ would be odd (proved in the direct proof lesson) = $a = 2k$ for some integer $k$

Substitute: $(2k)^2 = 2b^2$, so $4k^2 = 2b^2$, so $b^2 = 2k^2$ = $b^2$ is even, so $b$ is even

Spot the contradiction: Both $a$ and $b$ are even, so both are divisible by $2$ = This breaks "lowest terms"

Answer: The assumption that $\sqrt{2}$ is rational leads to a contradiction, so $\sqrt{2}$ is irrational. QED

There Are Infinitely Many Primes (Euclid)

Prove that there are infinitely many prime numbers.

Write the negation: Assume, for contradiction, that there are only finitely many primes: $p_1, p_2, \ldots, p_n$ = The list contains every prime

Build a new number: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Divide N by each prime on the list: $N$ is one more than a multiple of every $p_i$ = The remainder is always $1$, so no $p_i$ divides $N$

Use a known fact: Every integer greater than $1$ has at least one prime factor = $N$ has a prime factor that is not on the list

Spot the contradiction: The list was supposed to contain every prime = The assumption is false

Answer: There are infinitely many primes. Careful: $N$ itself need not be prime. With the primes up to 13, $N = 30031 = 59 \times 509$, and 59 and 509 are primes missing from the list. QED

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.

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

Why: 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".

Mistake: Negating $x > 5$ as $x < 5$

Why: 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$.

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

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

Mistake: Calling a surprising result a contradiction

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

Matching Socks in the Dark

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

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.

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.

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.

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.

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.

A proof by contradiction assumes the statement is false and shows that this leads to something impossible

The first line is the correct negation: "infinitely many" becomes "only finitely many", $x > 5$ becomes $x \le 5$, "every" becomes "at least one ... not"

A 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

Classic 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

The pigeonhole principle: if more than $n$ objects go into $n$ boxes, some box holds at least two objects

Proof 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

Q: Why is it enough to reach a contradiction?

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

Q: When should I use proof by contradiction?

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

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

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

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

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

Exit Presentation

Proof by Contradiction

1 / 14

Logic & Sets / Mathematical Proofs

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 min

Use arrow keys or spacebar to navigate