Proof by Contradiction

Proof by Contradiction
Indirect Proof

Proving a conjecture by assuming that the conjecture is false. If this assumption leads to a contradiction, the original conjecture must have been true. This technique employs the logical method known as modus tolens.

Proof by contradiction that √2 is irrational: assumes √2=a/b, derives 2b²=a², showing 2 divides both a and b, contradicting...

Key Formula

\text{To prove } P\text{: Assume } \neg P. \quad \neg P \Rightarrow \text{contradiction} \quad \therefore P \text{ is true.}

Where:

$P$ = The statement (conjecture) you want to prove is true
$\neg P$ = The negation of P — the assumption that P is false
$\Rightarrow$ = Logical implication: the assumption leads to what follows
$\therefore$ = Therefore — indicates the conclusion

Example

Problem: Prove that the square root of 2 is irrational.

Step 1: Assume the opposite: suppose √2 is rational. Then it can be written as a fraction in lowest terms.

\text{Assume } \sqrt{2} = \frac{a}{b}, \text{ where } a, b \in \mathbb{Z},\; b \neq 0,\; \gcd(a, b) = 1

Step 2: Square both sides to eliminate the square root.

2 = \frac{a^2}{b^2} \implies a^2 = 2b^2

Step 3: Since a² = 2b², the value a² is even. An integer whose square is even must itself be even, so a = 2k for some integer k.

a = 2k \implies a^2 = 4k^2

Step 4: Substitute a² = 4k² back into the equation from Step 2.

4k^2 = 2b^2 \implies b^2 = 2k^2

Step 5: Now b² is also even, which means b is even. But we said gcd(a, b) = 1, meaning a and b share no common factors. Having both a and b even contradicts this. The assumption that √2 is rational is therefore false.

a \text{ even and } b \text{ even} \implies \gcd(a,b) \geq 2 \;\; \text{— contradiction!}

Answer: Since assuming √2 is rational leads to a contradiction, √2 must be irrational.

Another Example

This classic proof (attributed to Euclid) shows proof by contradiction applied to an existence/infinity claim rather than an irrationality claim, demonstrating the technique's broad versatility.

Problem: Prove that there are infinitely many prime numbers.

Step 1: Assume the opposite: suppose there are only finitely many primes. List all of them.

\text{Assume the primes are } p_1, p_2, p_3, \ldots, p_n \text{ and no others exist.}

Step 2: Construct a new number N by multiplying all the primes together and adding 1.

N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1

Step 3: Consider what happens when you divide N by any prime on the list. Each prime pᵢ divides the product p₁·p₂·…·pₙ exactly, so dividing N by pᵢ always leaves a remainder of 1.

N \div p_i \text{ has remainder } 1 \text{ for every } i = 1, 2, \ldots, n

Step 4: Since no prime on our list divides N, either N is itself prime or N has a prime factor not on the list. Either way, there exists a prime not among p₁, p₂, …, pₙ. This contradicts our assumption that the list contained all primes.

\text{A prime exists that is not in } \{p_1, p_2, \ldots, p_n\} \;\; \text{— contradiction!}

Answer: Since assuming finitely many primes leads to a contradiction, there must be infinitely many primes.

Frequently Asked Questions

What is the difference between proof by contradiction and proof by contrapositive?

Proof by contrapositive proves 'if P then Q' by instead proving the logically equivalent statement 'if not Q then not P.' Proof by contradiction is more general: you assume the negation of whatever you want to prove and derive any contradiction at all, not necessarily 'not P.' Every proof by contrapositive can be reframed as a proof by contradiction, but not every proof by contradiction is a contrapositive argument.

When should you use proof by contradiction?

Use proof by contradiction when a direct proof seems difficult or when the statement involves non-existence, uniqueness, or irrationality. If you find it hard to move forward from the hypotheses, try assuming the conclusion is false and see where the logic leads. The technique is especially powerful for proving that something cannot happen or that a certain kind of number does not exist.

Why does proof by contradiction actually work?

It relies on the law of excluded middle: every mathematical statement is either true or false; there is no third option. If assuming a statement is false produces a logical impossibility, then the 'false' option is ruled out, and the statement must be true. This reasoning pattern is called modus tollens in formal logic.

Proof by Contradiction vs. Direct Proof

	Proof by Contradiction	Direct Proof
Starting point	Assume the statement is false	Start from known truths or given hypotheses
Goal	Derive a logical impossibility (contradiction)	Derive the statement itself through a chain of reasoning
Typical use	Irrationality, infiniteness, non-existence claims	Algebraic identities, divisibility results, straightforward implications
Logical basis	Modus tollens and the law of excluded middle	Modus ponens (if P then Q; P is true; therefore Q)
Difficulty	Can feel indirect; requires creativity to find the contradiction	Often more intuitive when a clear path from hypothesis to conclusion exists

Why It Matters

Proof by contradiction is one of the most frequently used proof techniques in all of mathematics, from introductory geometry courses through advanced university-level analysis and number theory. Many landmark results — the irrationality of √2, the infinitude of primes, Cantor's proof that the real numbers are uncountable — rely on this method. Learning it well prepares you for any course that requires writing rigorous proofs.

Common Mistakes

Mistake: Forgetting to clearly state the assumption at the beginning of the proof.

Correction: Always start by writing 'Assume, for the sake of contradiction, that [negation of the statement].' Without a clear negation, the reader (and you) can lose track of what you're trying to contradict.

Mistake: Reaching a result that seems unlikely or surprising but is not actually a logical contradiction.

Correction: A valid contradiction must be a statement that is provably false — such as 'an integer is both even and odd' or '0 = 1.' A result that is merely unintuitive does not count. Make sure you identify two statements that directly conflict with each other.

Related Terms

Conjecture — The statement assumed false in the proof
Modus Tollens — Logical rule underlying proof by contradiction
Irrational Numbers — Often proved irrational via contradiction
Rational Numbers — Assumed form in irrationality proofs
Integers — Number set used in many contradiction proofs
Factor of an Integer — Divisibility facts used to reach contradictions
Relatively Prime — Key condition violated in the √2 proof