Proof by Contradiction

Proof by contradiction is a workhorse across essentially all of pure mathematics: Cantor's diagonal argument establishing the uncountability of the real numbers is a contradiction proof (assume a bijection $\mathbb{N} \to \mathbb{R}$ exists, construct a real number not in its range); the irrationality of $e$ and $\pi$, the non-existence of a rational number whose square is any non-perfect-square integer, and Gödel's own incompleteness theorems (assuming completeness and deriving a self-referential contradiction) all rely on it. In computer science, many undecidability results (the Halting Problem is undecidable) are contradiction proofs: assume a deciding algorithm exists, construct a diagonal program that contradicts its own claimed output. In cryptography, security proofs frequently argue "if an efficient adversary broke this scheme, we could use it to solve a hard problem (like factoring), contradicting its assumed hardness" — a reduction that is itself a disguised proof by contradiction. In statistics, hypothesis testing is philosophically modeled on the same shape: assume the null hypothesis, show the observed data would be extremely improbable under it, and treat that near-impossibility as grounds to reject the assumption (though this is a probabilistic, not strict logical, contradiction). In physics and engineering, impossibility results — no perpetual motion machine, no signal traveling faster than light in special relativity without violating causality — are argued by assuming the forbidden device or process exists and deriving a violation of a conservation law or an established physical law treated as background axiom.

Ask the tutor: How does combining proof by contradiction with the Well-Ordering Principle produce a "minimal counterexample" argument, and how is that different from ordinary induction?

Think of all statements as living in a two-valued world: every proposition is either True or False, with no third option — this is the Law of Excluded Middle baked into classical logic. Proof by contradiction exploits this rigid binary structure like a wall with only two rooms. If you can show that being in the "False" room for $P$ (that is, assuming $\neg P$) forces you into a room that is simultaneously lit and dark — a statement $R$ that is both true and false — then the "False" room must not have been accessible after all. Since there are only two rooms, $P$ must be in the "True" room. It helps to picture this as a decision tree that terminates in an impossible leaf. You start at the root with the assumption $\neg P$. You walk down branches of valid logical deduction. If every possible path from that root eventually hits a leaf labeled "$R$ and $\neg R$," the entire subtree rooted at $\neg P$ is logically poisoned — nothing consistent can grow from it — so the root itself must be pruned as a live possibility, leaving $P$ as the only surviving branch.

The picture also explains why the auxiliary statement $R$ can be anything: the contradiction does not need to be about $P$ directly. It only needs to be a genuine logical impossibility, because the tautology powering the method treats $R$ as a free, arbitrary placeholder. This is precisely what makes contradiction more flexible than Proof by Contrapositive, which is locked into rearranging a specific conditional $P \Rightarrow Q$ and cannot touch a bare, implication-free claim like "$\sqrt2$ is irrational."

Example 1: $\sqrt{2}$ is irrational. Claim. There is no rational number $r$ with $r^2 = 2$. Proof. Suppose, for contradiction, that $\sqrt 2$ is rational. Then there exist integers $a, b$ with $b \neq 0$ such that $\sqrt2 = a/b$, and we may choose $a, b$ so that $\gcd(a,b) = 1$ (any fraction can be reduced to lowest terms). Squaring both sides gives

Hence $a^2$ is even. If $a$ were odd, say $a = 2k+1$, then $a^2 = 4k^2+4k+1$ would be odd, contradicting that $a^2 = 2b^2$ is even; so $a$ must be even. Write $a = 2m$ for some integer $m$. Substituting,

So $b^2$ is even, and by the same parity argument $b$ is even. But then both $a$ and $b$ are even, so $2$ divides $\gcd(a,b)$, contradicting $\gcd(a,b)=1$. We have derived $R :=$ "$\gcd(a,b) = 1$" (assumed at the outset, hence still true) and $\neg R :=$ "$2 \mid \gcd(a,b)$" (just derived), giving $R \wedge \neg R$. By the Theorem, our assumption that $\sqrt2$ is rational is false; $\sqrt2$ is irrational. $\blacksquare$ Note the structure: $P$ is "$\sqrt2$ is irrational," an atomic statement with no visible conditional to contrapose, which is exactly the setting where contradiction is essential rather than merely convenient.

Example 2: There are infinitely many prime numbers (Euclid). Claim. The set of prime numbers is infinite. Proof. Suppose, for contradiction, that there are only finitely many primes, say exactly $n$ of them, listed as $p_1, p_2, \dots, p_n$ with no repeats and (by the assumption of finiteness) this list is exhaustive — every prime equals some $p_i$. Consider the integer

Since each $p_i \geq 2$, we have $N \geq 2 \cdot 1 + 1 = 3 > 1$ (checking the smallest possible case $n=1$; in general $N$ is at least $2+1=3$), so $N > 1$. By the Fundamental Theorem of Arithmetic (every integer greater than $1$ has a prime divisor), $N$ has some prime divisor $q$. Because the list $p_1,\dots,p_n$ is exhaustive, $q = p_i$ for some index $i \in \{1,\dots,n\}$. Since $q = p_i$ divides $N = p_1\cdots p_n + 1$, and $q$ also divides the product $p_1 p_2 \cdots p_n$ (as $q$ is one of its factors), $q$ divides the difference:

So $q \mid 1$. But $q$ is prime, hence $q \geq 2$, and no integer $\geq 2$ divides $1$ (the only positive divisor of $1$ is $1$ itself). This gives $R :=$ "$q \mid 1$" and $\neg R :=$ "$q \nmid 1$" (since $q \geq 2 > 1$), a contradiction of the form $R \wedge \neg R$. By the Theorem, the assumption that the primes are finite in number is false. Hence there are infinitely many primes. $\blacksquare$ Here the contradiction $R \wedge \neg R$ is about an auxiliary object $q \mid 1$ that never appears in the original statement $P$ = "there are infinitely many primes," illustrating that $R$ is a free choice, not a rephrasing of $P$.