2.7 Proof by contradiction

Definition and purpose

Proof by contradiction is a technique for establishing the truth of a statement indirectly. Instead of building a direct path from assumptions to conclusion, you assume the opposite of what you want to prove and show that this assumption leads to a logical impossibility. Once you hit that impossibility, you know the original statement must be true.

This approach is especially useful when a direct proof feels difficult or unnatural, such as when you're trying to prove something doesn't exist or that something is unique.

Concept of contradiction

The core idea: assume the opposite of your claim, then follow the logic until something breaks. That "break" is a contradiction, a situation where two things that can't both be true are forced to be true simultaneously.

This technique is sometimes called reductio ad absurdum (Latin for "reduction to absurdity"). You're literally reducing the opposing assumption to an absurd conclusion.

• A contradiction arises when a statement and its negation would both have to hold (e.g., a number being both even and odd)
• The principle of non-contradiction says a statement and its negation cannot both be true
• Proof by contradiction is often the go-to method when direct approaches hit a wall

Logical foundations

Proof by contradiction rests on the law of excluded middle: every proposition is either true or false, with no third option. So if assuming a statement is false leads to nonsense, the statement must be true.

• You'll use logical connectives (and, or, not) and their truth tables to build your argument
• The reasoning chain typically involves if-then implications: if the negation is true, then some known fact is violated
• Familiarity with how negations work is critical. For example, the negation of "all X are Y" is "there exists an X that is not Y," not "no X are Y"

Structure of proof

Steps in a contradiction proof

Here's the general process:

1. State the proposition you want to prove.
2. Assume the negation of the proposition is true.
3. Derive logical consequences from that assumption, using valid deductive reasoning.
4. Arrive at a contradiction between those consequences and some known mathematical fact (or between two consequences themselves).
5. Conclude that the negation must be false, so the original proposition is true.

Every step needs to be rigorously justified. The proof's strength depends entirely on the logical chain being airtight.

Assumption of falsehood

Getting the negation right is one of the trickiest parts. You need to negate the entire proposition precisely.

• For a statement like "there is no integer $n$ such that...," the negation becomes "there exists an integer $n$ such that..."
• For "$\sqrt{2}$ is irrational," the negation is "$\sqrt{2}$ is rational"
• Depending on the proposition, you may end up working with inequalities, set complements, or existential vs. universal quantifiers

Once you have the negation, you treat it as temporarily true and chase its implications until something contradicts established mathematics.

Common applications

Number theory proofs

Number theory is where proof by contradiction really shines. Classic uses include:

• Proving the irrationality of numbers like $\sqrt{2}$, $\sqrt{3}$, etc.
• Demonstrating that there are infinitely many primes
• Establishing properties of divisibility and factorization (e.g., if a prime divides a product, it must divide one of the factors)
• Proving the non-existence of integer solutions to certain equations (Diophantine equations)

Geometry proofs

• Proving the impossibility of certain constructions (e.g., trisecting an arbitrary angle with compass and straightedge alone)
• Establishing uniqueness of geometric objects, such as showing there's exactly one line through a point parallel to a given line
• Demonstrating properties of parallel lines, triangle congruence, and circle theorems where direct approaches are awkward

Examples of famous proofs

Irrationality of $\sqrt{2}$

This is the classic first example of proof by contradiction. Here's the full argument:

1. Assume $\sqrt{2}$ is rational. Then it can be written as $\frac{a}{b}$ where $a$ and $b$ are integers with no common factors (the fraction is in lowest terms).
2. Square both sides: $2 = \frac{a^2}{b^2}$
3. Multiply both sides by $b^2$: $2b^2 = a^2$
4. This means $a^2$ is even. Since the square of an odd number is always odd, $a$ itself must be even.
5. Write $a = 2k$ for some integer $k$. Substitute: $2b^2 = (2k)^2 = 4k^2$
6. Simplify: $b^2 = 2k^2$
7. Now $b^2$ is even, so $b$ must be even too.
8. Contradiction: Both $a$ and $b$ are even, meaning they share a factor of 2. But we assumed the fraction was in lowest terms (no common factors).
9. Conclusion: The assumption that $\sqrt{2}$ is rational must be false. Therefore, $\sqrt{2}$ is irrational.

Infinitude of primes

This proof goes back to Euclid, and it's still one of the most elegant arguments in all of mathematics.

1. Assume there are only finitely many primes: $p_1, p_2, \ldots, p_n$.
2. Construct the number $N = (p_1 \times p_2 \times \cdots \times p_n) + 1$.
3. Now consider: is $N$ prime or composite?
4. If $N$ is prime, then it's a prime not in our list (since it's larger than all of them). That contradicts our assumption that the list contains all primes.
5. If $N$ is composite, it must have some prime factor. But dividing $N$ by any prime in our list leaves a remainder of 1, so none of them divide $N$. That means $N$ has a prime factor not on our list.
6. Either way, there's a prime missing from the supposedly complete list.
7. Conclusion: The assumption of finitely many primes is false. There are infinitely many primes.

Strengths and limitations

Power of indirect reasoning

• Proof by contradiction lets you tackle statements that resist direct proof, especially claims about non-existence or uniqueness
• It provides a systematic framework: negate, deduce, find the contradiction
• The resulting proofs are often surprisingly concise and elegant
• It deepens your understanding of why something must be true by showing what goes wrong when you assume otherwise

Potential pitfalls

• Circular reasoning is a real danger. If you accidentally use the thing you're trying to prove as part of your deduction chain, the proof is invalid.
• Contradiction proofs don't always tell you why something is true in a constructive sense. They tell you the opposite can't be true, which is subtly different.
• Getting the negation wrong will derail the entire proof. Be precise.
• Sometimes a simpler direct proof exists, and using contradiction just makes the argument harder to follow than it needs to be.

Comparison with other methods

Direct proof vs. contradiction

Contraposition vs. contradiction

These two are closely related but distinct.

• Contraposition proves "if $P$, then $Q$" by instead proving "if not $Q$, then not $P$." It maintains a direct logical flow.
• Contradiction assumes "$P$ and not $Q$" simultaneously, then derives an impossibility. It's more flexible because you have both $P$ and not-$Q$ to work with.

Contraposition tends to produce cleaner proofs for conditional (if-then) statements. Contradiction is more versatile and works for a wider range of propositions, including existential and universal claims.

Historical development

Ancient Greek contributions

• Zeno of Elea (c. 490–430 BCE) used contradiction-style reasoning in his famous paradoxes about motion and infinity
• Euclid (c. 300 BCE) employed proof by contradiction throughout his Elements, including the proof of infinitely many primes
• Aristotle (384–322 BCE) formalized the law of non-contradiction as a foundational principle of logic
• The Pythagorean school likely discovered the irrationality of $\sqrt{2}$ through contradiction, a result that reportedly shocked them since it challenged their belief that all numbers were rational

Modern refinements

• The development of formal logic in the 19th and 20th centuries made contradiction proofs more rigorous
• Georg Cantor (1845–1918) used contradiction to prove the real numbers are uncountable (his famous diagonal argument)
• Kurt Gödel (1906–1978) employed contradiction in his incompleteness theorems
• Intuitionistic logic, developed by Brouwer and others, challenges the universal validity of proof by contradiction. Intuitionists reject the law of excluded middle, so they don't accept all contradiction proofs as valid. This remains a genuine philosophical divide in the foundations of mathematics.

Practical problem-solving

Identifying when to use contradiction

Not every proof calls for contradiction. Here are signs it might be the right tool:

• The statement involves non-existence ("there is no...") or uniqueness ("there is exactly one...")
• A direct approach doesn't have an obvious starting point
• The negation of the statement gives you something concrete to work with (e.g., assuming a number is rational gives you a fraction to manipulate)
• You notice mutually exclusive conditions that could collide under the right assumption

Constructing effective arguments

1. Write out the proposition clearly before you begin.
2. Formulate the precise negation. Double-check it.
3. Build a logical chain from the negation, justifying each step.
4. Keep your eye on what known facts or earlier results might conflict with your deductions.
5. When you reach the contradiction, state it explicitly: "This contradicts the fact that..."
6. Close the proof by concluding the original proposition must be true.

A common mistake is being vague about what contradicts what. Always name both sides of the contradiction clearly.

Advanced techniques

Double contradiction

Sometimes you need to prove that two statements are equivalent ($A \iff B$). One approach is to assume the negation of each direction separately and derive contradictions for both.

• This requires careful tracking of which assumption you're working under at each stage
• It's common in abstract algebra and analysis where equivalences between definitions need to be established

Proof by infinite descent

This is a specialized form of contradiction used heavily in number theory, and it was a favorite technique of Fermat.

1. Assume a solution exists (say, a smallest positive integer with some property).
2. Show that this solution implies the existence of an even smaller positive integer with the same property.
3. But that contradicts the assumption that you started with the smallest one.
4. Since you can't descend through positive integers forever, no such solution exists.

This technique is particularly effective for proving that certain Diophantine equations have no positive integer solutions. The key insight is that the positive integers have a floor (there's no positive integer less than 1), so an infinite descent is impossible.