Techniques of Proof: Why Induction and Contradiction Are Valid

0. Key points

• What the inductive step proves is not ”$P(n)$ is true” but the implication “if $P(n)$ then $P(n+1)$”. Mistake this point and induction looks like circular reasoning.
• The validity of induction follows from the well-ordering property of the natural numbers, and conversely well-ordering follows from induction. In the Peano system, induction is the fifth axiom — part of the very definition of the natural numbers. Whether it is a theorem to be proved or an axiom to be posited depends on where one starts.
• Drop the base step and the conclusion may be false for every $n$, however flawless the inductive step. In the false proof that all horses are the same colour, by contrast, the base step is correct and the inductive step fails at $n = 1$ alone.
• Proof by contradiction assumes $\lnot P$ and derives some contradiction; proof by contraposition assumes $\lnot Q$ and derives $\lnot P$. The latter is a special case of the former, and whenever an argument can be rewritten in contrapositive form it becomes easier to read.
• That no rational number satisfies $x^2 = 2$ can be shown in two ways: with fractions in lowest terms, and by infinite descent. The second uses well-ordering — induction turned upside down — directly.

1. Motivation: writing infinitely many statements on finitely much paper

Most mathematical assertions have the shape “for every natural number $n$, …”. For instance,

$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

states infinitely many things at once: the claim for $n = 1$, the claim for $n = 2$, the claim for $n = 3$, and so on. Checking them one by one from $n = 1$ disposes of everything up to $n = 100$ in finite time. But whoever stops there has no answer when asked about $n = 101$. A policy of piling up verifications never terminates.

To write a proof of infinitely many statements on finitely much paper, we need a device of a qualitatively different kind. Mathematical induction is the chief example. The idea is simple: show only two things — that the first domino falls, and that whichever domino falls knocks over the next — and the whole infinite row goes down. Infinitely many verifications have been compressed into finitely many proofs (two, in this case).

Sometimes, on the other hand, the content of the proposition cannot be assembled directly. The claim that $\sqrt2$ cannot be written as a fraction asserts an impossibility, so building something and displaying it is no help. In such a case we ask what would happen if it could be written, and hunt for the breakdown. That is proof by contradiction.

Both techniques are ancient. The discovery of incommensurable magnitudes — two quantities with no common measure — goes back to the Pythagoreans of the fifth century BC, and the incommensurability of the diagonal and the side of a square was shown by contradiction. Explicit use of mathematical induction appears in Maurolico in the sixteenth century and in Pascal’s Traité du triangle arithmétique in the seventeenth, and at the end of the nineteenth Peano formulated it as part of an axiom system for the natural numbers.

Learning merely how to use these tools would take a single page. This article spends its space on why they are valid because, without knowing the grounds, one cannot detect a faulty induction. Faulty inductions do occur, and they look almost exactly like sound ones.

2. Preliminaries: implication and its converse, inverse and contrapositive

We write $\mathbb{N} = \{1, 2, 3, \ldots\}$ for the natural numbers; in this article $0$ is not a natural number. The integers are $\mathbb{Z}$, the rationals $\mathbb{Q}$ and the reals $\mathbb{R}$. For the number systems themselves (that $\mathbb{Q}$ and $\mathbb{R}$ are ordered fields（Definition 2.1）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］) see What is a number?; for the handling of logical notation (logical connectives（Definition 2.3）［The Grammar of Mathematics］ and quantifiers) see The grammar of mathematics: sets and logic.

For propositions $P$ and $Q$, the truth value of $P \Rightarrow Q$ (“if $P$ then $Q$”) is fixed by the table below. In particular, if $P$ is false then $P \Rightarrow Q$ is true whatever the truth value of $Q$. This convention will pay off repeatedly.

Definition 2.1（Converse, inverse, contrapositive）

Given a proposition $P \Rightarrow Q$, we call

• $Q \Rightarrow P$ its converse,
• $\lnot P \Rightarrow \lnot Q$ its inverse,
• $\lnot Q \Rightarrow \lnot P$ its contrapositive.

The truth values match up as follows.

$P$	$Q$	$P \Rightarrow Q$	Contrapositive $\lnot Q \Rightarrow \lnot P$	Converse $Q \Rightarrow P$
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	T	T

The third and fourth columns agree everywhere; the fifth does not. Read the table this way: a proposition and its contrapositive say the same thing, while the converse says something else.

3. Mathematical induction and why it is valid

The set of natural numbers has the following property, which the reals and the rationals lack.

Axiom 3.1（Well-ordering property）

Every non-empty subset of $\mathbb{N}$ has a least element. That is, if $S \subseteq \mathbb{N}$ and $S \ne \emptyset$, then there exists $m \in S$ such that $m \le n$ for every $n \in S$.

That this is not a triviality becomes clear on comparison with the rationals. The set $\{x \in \mathbb{Q} : x > 0\}$ is a non-empty subset of $\mathbb{Q}$ with no least element: given a positive rational $x$, the number $x/2$ is a smaller positive rational. The guarantee that one “cannot go any lower” is a consequence of the natural numbers being spread out discretely.

Theorem 3.2（Principle of mathematical induction）

Suppose that a proposition $P(n)$ is given for each $n \in \mathbb{N}$, and assume the following two conditions.

1. (Base step) $P(1)$ is true.
2. (Inductive step) For every $n \in \mathbb{N}$, “if $P(n)$ is true then $P(n+1)$ is true”.

Then $P(n)$ is true for every $n \in \mathbb{N}$.

Proof（Theorem 3.2）

Consider the set of counterexamples

$$S = \{\, n \in \mathbb{N} : P(n) \text{ is false} \,\} .$$

The conclusion we want is precisely $S = \emptyset$.

Suppose then that $S \ne \emptyset$ (here we argue by contradiction; the justification of that mode of argument is given in Proposition 6.2, but for the moment we use it as known logic). Since $S$ is a non-empty subset of $\mathbb{N}$, the well-ordering property（Axiom 3.1） supplies a least element $m \in S$.

First, $m \ne 1$. Indeed, hypothesis 1 says $P(1)$ is true, so $1 \notin S$, whereas $m \in S$. As $m \in \mathbb{N}$ and $m \ne 1$, we have $m \ge 2$, so $m - 1$ is again a natural number.

Next, $m - 1 \notin S$, because $m - 1 < m$ and $m$ is the least element of $S$. And $m - 1 \notin S$ means that $P(m-1)$ is true.

Now apply hypothesis 2 with $n = m - 1$. Since $P(m-1)$ is true, so is $P((m-1)+1) = P(m)$. But $m \in S$ meant that $P(m)$ is false. Thus $P(m)$ is both true and false, a contradiction.

Hence the assumption $S \ne \emptyset$ is untenable: $S = \emptyset$, that is, $P(n)$ is true for every $n$.

∎

flowchart LR
Z["Base step: prove P(1)"] --> A["P(1)"]
A -->|"inductive step (n=1)"| B["P(2)"]
B -->|"inductive step (n=2)"| C["P(3)"]
C -->|"inductive step (n=3)"| D["P(4)"]
D -->|"and so on"| E["…"]

The base step topples the first domino; the inductive step passes the fall along

Remark 3.3（Why this is not circular reasoning）

Almost everyone meeting induction for the first time asks: if we assume $P(n)$ in order to prove $P(n+1)$, are we not assuming what we set out to prove?

We are not. What the inductive step proves is not $P(n)$ but the implication $P(n) \Rightarrow P(n+1)$. By the truth table of §2, that implication is automatically true whenever $P(n)$ is false. So proving the inductive step alone gives no guarantee that $P$ holds for even a single $n$. Indeed, Example 5.1 exhibits a perfectly correct inductive step for a $P$ that is false for every $n$.

The phrase “assume $P(n)$” signals a conditional argument — “if we are in a world where $P(n)$ is true” — and does not grant $P(n)$.

Example 3.4（The sum of the first n integers）

For every $n \in \mathbb{N}$ we have $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.

Let $P(n)$ be this identity.

Base step. For $n = 1$ the left-hand side is $1$ and the right-hand side is $\dfrac{1 \cdot 2}{2} = 1$. They agree, so $P(1)$ is true.

Inductive step. Take an arbitrary $n \in \mathbb{N}$ and assume $P(n)$, that is, $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$. Then

$$\begin{aligned} \sum_{k=1}^{n+1} k &= \left(\sum_{k=1}^{n} k\right) + (n+1) \\ &= \frac{n(n+1)}{2} + (n+1) && \text{(by the induction hypothesis)} \\ &= (n+1)\left(\frac{n}{2} + 1\right) \\ &= \frac{(n+1)(n+2)}{2}. \end{aligned}$$

The last expression is exactly $\dfrac{(n+1)\bigl((n+1)+1\bigr)}{2}$, so $P(n+1)$ holds.

By Theorem 3.2, $P(n)$ holds for every $n$.

Example 3.5（Bernoulli's inequality, and what happens when the hypothesis is dropped）

Let $x$ be a real number with $x \ge -1$ and let $n \in \mathbb{N}$. Then $(1+x)^n \ge 1 + nx$.

Base step. For $n = 1$ both sides equal $1 + x$, so equality holds.

Inductive step. Assume $(1+x)^n \ge 1 + nx$. The hypothesis $x \ge -1$ gives $1 + x \ge 0$, so multiplying both sides of the inequality by $1+x$ does not reverse it. Hence

$$(1+x)^{n+1} = (1+x)^n (1+x) \ge (1+nx)(1+x) = 1 + (n+1)x + n x^2 \ge 1 + (n+1)x .$$

The last inequality holds because $n x^2 \ge 0$.

What if the hypothesis $x \ge -1$ is dropped? We used $1+x \ge 0$ in the inductive step, so that is where the argument breaks. Concretely, take $x = -4$ and $n = 3$: the left-hand side is $(1-4)^3 = -27$ and the right-hand side is $1 + 3 \cdot (-4) = -11$, and $-27 \ge -11$ is false. Hypotheses are not decoration; they are used somewhere in every proof.

4. The Peano axioms: is induction a theorem or an axiom?

We proved Theorem 3.2 from well-ordering. But where does well-ordering come from? In fact well-ordering can itself be proved from induction. The two are equivalent properties: grant either one of them for the natural numbers and the other follows.

That forces us back to the question of what the natural numbers are. The answer Peano gave at the end of the nineteenth century is the following axiom system. Here $s(n)$ denotes the successor of $n$.

Axiom 4.1（The Peano axioms）

Let a set $\mathbb{N}$, an element $1$ of it, and a map $s : \mathbb{N} \to \mathbb{N}$ satisfy the following.

1. $1 \in \mathbb{N}$.
2. $s(n) \in \mathbb{N}$ for every $n \in \mathbb{N}$.
3. $s(n) \ne 1$ for every $n \in \mathbb{N}$ ($1$ is the successor of no number).
4. For all $m, n \in \mathbb{N}$, if $s(m) = s(n)$ then $m = n$ ($s$ is injective).
5. (Axiom of induction) If $S \subseteq \mathbb{N}$ satisfies "$1 \in S$" and ”$n \in S$ implies $s(n) \in S$”, then $S = \mathbb{N}$.

We then call $(\mathbb{N}, 1, s)$ a system of natural numbers.

The fifth axiom is Theorem 3.2 itself. Taking $S$ to be the set of those $n$ for which $P(n)$ is true, the hypotheses translate into the base step and the inductive step, and the conclusion into ”$P(n)$ for every $n$”. So from Peano’s standpoint induction is not a theorem to be proved but part of the stipulation of what a natural number is.

Peano’s own paper of 1889 started from $1$. Most textbooks today start from $0$, and the theory develops in the same way either way.

Remark 4.2（Which axiom carries which load）

Looking at what breaks when an axiom is removed shows what each axiom does.

Drop axiom 3. Let $\mathbb{N}' = \{1, 2, 3\}$ with $s(1) = 2$, $s(2) = 3$, $s(3) = 1$. Since $s$ is a bijection of $\mathbb{N}'$, axiom 4 holds. Axiom 5 holds as well: any $S$ containing $1$ and closed under $s$ contains $1, 2, 3$, so $S = \mathbb{N}'$. But $s(3) = 1$, so axiom 3 fails. Thus without axiom 3 a “pseudo-natural-number system” with only finitely many elements is permitted: induction alone does not deliver infinitude.

Drop axiom 5. Adjoin to $\mathbb{N}$ a family of elements $\ldots, a_{-1}, a_0, a_1, \ldots$ arranged like the integers, obtaining a set $\mathbb{N}^{*}$, and set $s(a_k) = a_{k+1}$. Since no $a_k$ equals $1$ or $s(n)$ for an ordinary natural number $n$, axioms 1 through 4 all hold. Yet $S = \mathbb{N}$ contains $1$, is closed under $s$, and is not all of $\mathbb{N}^{*}$. Axiom 5 is exactly the demand that there be no superfluous elements beyond the reach of iterating $s$ from $1$.

These “natural numbers with extra elements attached” are called non-standard models, and they lead to the question whether a formal system can pin down its intended object uniquely. On this theme see An invitation to mathematical logic: the incompleteness theorems, and in particular Example 5.4［ゲーデルの不完全性定理］.

Theorem 4.3（Strong induction）

Suppose that a proposition $P(n)$ is given for each $n \in \mathbb{N}$, and assume:

• for every $n \in \mathbb{N}$, if $P(k)$ is true for every $k \in \mathbb{N}$ with $k < n$, then $P(n)$ is true.

Then $P(n)$ is true for every $n \in \mathbb{N}$.

Proof（Theorem 4.3）

Let $Q(n)$ be the proposition ”$P(k)$ is true for every $k \in \mathbb{N}$ with $k \le n$”, and apply Theorem 3.2 to $Q$.

Base step. Apply the hypothesis with $n = 1$. There is no natural number smaller than $1$, so ”$P(k)$ for every $k < 1$” is vacuously true (there is nothing at all to be said about any such $k$). Hence the hypothesis yields that $P(1)$ is true. Since $1$ is the only natural number $\le 1$, this gives $Q(1)$.

Inductive step. Assume $Q(n)$: that is, $P(k)$ is true for every $k \le n$. For natural numbers, $k < n+1$ and $k \le n$ are equivalent, so this says ”$P(k)$ for every $k < n+1$”. Applying the hypothesis with $n+1$ therefore makes $P(n+1)$ true. Together, $P(k)$ holds for every $k \le n+1$, which is $Q(n+1)$.

By Theorem 3.2, $Q(n)$ is true for every $n$; in particular $P(n)$ is true.

∎

Tip

Strong induction appears to have no base step, but the base step has not vanished. As the proof above shows, the case $n = 1$ has been absorbed into the inductive step in the form of a vacuously true hypothesis. When actually using strong induction, always check that the argument really goes through at $n = 1$. Skipping that check is the commonest error with strong induction.

Example 4.4（Existence of prime factorizations）

Every natural number $\ge 2$ can be written as a product of primes (a product of a single prime is allowed).

Let $P(n)$ be the statement “if $n \ge 2$ then $n$ is a product of primes”. For $n = 1$ the antecedent is false, so $P(1)$ is true (by the truth table of §2).

Let $n \ge 2$ and assume $P(k)$ for every natural number $k < n$.

• If $n$ is prime, then $n$ itself is a product of one prime, so $P(n)$ holds.
• If $n$ is not prime, then, being $\ge 2$ and composite, there are natural numbers $a, b$ with $n = ab$ and $1 < a < n$, $1 < b < n$ (this is the definition of a composite number). From $1 < a$ and $a$ a natural number we get $a \ge 2$, and likewise $b \ge 2$. Also $a < n$ and $b < n$, so the induction hypothesis applies to both $a$ and $b$, and each is a product of primes. Juxtaposing the two factorizations exhibits $n = ab$ as a product of primes.

In either case $P(n)$ holds, so by Theorem 4.3 $P(n)$ is true for every $n$.

Note that ordinary induction is unavailable here. The factors $a, b$ in a decomposition $n = ab$ need not be $n-1$; they may sit anywhere between $2$ and $n-1$, unpredictably. Being able to assume the statement for all smaller numbers, rather than for the immediate predecessor, is what makes strong induction worth having.

5. When induction breaks

5.1. Forgetting the base step

Example 5.1（A false proposition whose inductive step is correct）

Let $P(n)$ be the identity

$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2} + 7 .$$

Let us check the inductive step. Assuming $P(n)$,

$$\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1) = \frac{n(n+1)}{2} + 7 + (n+1) = \frac{(n+1)(n+2)}{2} + 7$$

which is precisely $P(n+1)$. The inductive step is entirely correct; there is no error anywhere in it.

But $P(1)$ reads "$1 = 1 + 7$", which is false. By Example 3.4 the correct sum is $n(n+1)/2$, so $P(n)$ is false for every $n$.

A row of dominoes whose toppling mechanism is in perfect order but with nobody to knock over the first one — that is induction without a base step. As noted in Remark 3.3, the inductive step asserts only an implication and by itself produces nothing.

5.2. A gap in the inductive step

Example 5.2（All horses are the same colour (a false proof)）

Let $P(n)$ be the statement “any collection of $n$ horses consists of horses that are all the same colour”.

Base step. $P(1)$ is true: a collection consisting of a single horse has that horse’s own colour throughout.

The alleged inductive step. Assume $P(n)$ and take $n+1$ horses $h_1, h_2, \ldots, h_{n+1}$. The sets

$$A = \{h_1, \ldots, h_n\}, \qquad B = \{h_2, \ldots, h_{n+1}\}$$

each consist of $n$ horses, so by the induction hypothesis all horses in $A$ have one colour and all horses in $B$ have one colour. Picking a horse belonging to $A \cap B = \{h_2, \ldots, h_n\}$, its colour is both the colour of all of $A$ and the colour of all of $B$, so the two colours coincide. Since $A \cup B$ is the whole collection of $n+1$ horses, $P(n+1)$ holds.

Where is the gap? The last argument presupposes $A \cap B \ne \emptyset$. But $A \cap B = \{h_2, \ldots, h_n\}$ is non-empty only when $n \ge 2$. For $n = 1$ we have $A = \{h_1\}$ and $B = \{h_2\}$ with no horse in common, and nothing links the colour of $A$ to that of $B$.

So $P(1) \Rightarrow P(2)$ has not been established — and $P(2)$ is false (horses of different colours exist). The row of dominoes is severed between the first and the second, and nothing beyond falls.

The moral is that the inductive step must be proved for every $n$. Always inspect an argument written “for general $n$” to see whether it silently uses an extra hypothesis for small $n$. Be especially wary when the argument takes the intersection of two subsets, considers $n-1$, or splits something into two parts.

5.3. Numerical evidence is not proof

Remark 5.3（Finitely many checks are not enough）

“I checked $n = 1$ through $n = 5$, so it holds in general” is not a proof. Examples where the first counterexample lies far away are plentiful.

• The polynomial $f(n) = n^2 + n + 41$, which Euler noticed around 1772, takes prime values at all $40$ integers $n = 0, 1, \ldots, 39$. But $f(40) = 1600 + 40 + 41 = 1681 = 41^2$ is not prime.
• The Fermat numbers $F_n = 2^{2^n} + 1$ are $3, 5, 17, 257, 65537$ for $n = 0, 1, 2, 3, 4$, all prime. Fermat conjectured that they are prime for every $n$, but in 1732 Euler exhibited the factorization $F_5 = 4294967297 = 641 \times 6700417$.

The following code confirms both.

def is_prime(m):
    if m < 2:
        return False
    d = 2
    while d * d <= m:
        if m % d == 0:
            return False
        d += 1
    return True

# the smallest n >= 0 for which n^2 + n + 41 is not prime
print([n for n in range(41) if not is_prime(n * n + n + 41)])  # -> [40]

# the factorization of the Fermat number F_5
print(2**32 + 1 == 641 * 6700417)                              # -> True

Numerical experiment is useful for discovering what ought to be proved. It is not itself a proof. Only when the logic carrying $n$ to $n+1$ has been written down are infinitely many statements secured.

6. Proof by contradiction and proof by contraposition

6.1. Proof by contraposition

Proposition 6.1（Equivalence with the contrapositive）

For any propositions $P, Q$, the truth of $P \Rightarrow Q$ is equivalent to the truth of its contrapositive $\lnot Q \Rightarrow \lnot P$.

Proof（Proposition 6.1）

This can be read off from the agreement of the third and fourth columns of the truth table in §2, but let us also argue by following the meanings.

($\Rightarrow$) Suppose $P \Rightarrow Q$ is true, and assume $\lnot Q$. If $P$ were true, then $P \Rightarrow Q$ would make $Q$ true, contradicting the assumption $\lnot Q$. Hence $P$ is false, that is, $\lnot P$ is true. From $\lnot Q$ we have derived $\lnot P$, so $\lnot Q \Rightarrow \lnot P$ is true.

($\Leftarrow$) Suppose $\lnot Q \Rightarrow \lnot P$ is true, and assume $P$. If $Q$ were false, that is, $\lnot Q$ true, then the hypothesis would make $\lnot P$ true, incompatible with $P$. Hence $\lnot Q$ is false, that is, $\lnot \lnot Q$ is true. Using elimination of double negation, $\lnot\lnot Q \Rightarrow Q$, we get $Q$. From $P$ we have derived $Q$, so $P \Rightarrow Q$ is true.

∎

Note that the direction ($\Leftarrow$) used elimination of double negation. It is precisely the direction we actually use — “proving the contrapositive proves the original statement” — that depends on a rule specific to classical logic.

6.2. Proof by contradiction

Proposition 6.2（Validity of proof by contradiction）

Let $P$ be a proposition. If assuming $\lnot P$ yields both $R$ and $\lnot R$ for some proposition $R$, then $P$ is true.

Proof（Proposition 6.2）

The hypothesis says that $\lnot P \Rightarrow (R \wedge \lnot R)$ is true. Now $R \wedge \lnot R$ is false whatever the truth value of $R$ (if $R$ is true then $\lnot R$ is false; if $R$ is false then $R$ is false; either way the conjunction is false).

Suppose $\lnot P$ were true. Then the antecedent of a true implication would be true, so the consequent $R \wedge \lnot R$ would be true as well — contrary to the falsity of $R \wedge \lnot R$. Hence $\lnot P$ is false, that is, $\lnot\lnot P$ is true. By elimination of double negation (equivalently, by the law of excluded middle $P \vee \lnot P$), $P$ is true.

∎

6.3. How the two differ, and where they overlap

Starting points and destinations of the three methods of proof

In tabular form:

	Direct proof	Contraposition	Contradiction
Shape of the claim	$P \Rightarrow Q$	$P \Rightarrow Q$	$P$ (need not be an implication)
What is assumed	$P$	$\lnot Q$	$\lnot P$
Goal aimed at	$Q$	$\lnot P$	any contradiction
Is the goal fixed?	yes	yes	no
Logical rule relied on	none	double negation elimination	excluded middle (double negation elimination)

The two are not unrelated. To prove $P \Rightarrow Q$ by contradiction is to assume $P$ and $\lnot Q$ and derive a contradiction. If we choose that contradiction to be ”$\lnot P$ against $P$”, then we have derived $\lnot P$ from $\lnot Q$ — which is exactly a proof by contraposition. Proof by contraposition is a special case of proof by contradiction.

Conversely, most proofs written by contradiction can be rewritten as proofs by contraposition, and where this is possible the result reads better. A proof that ends with “contradiction” makes it hard for the reader to trace which hypothesis did the work and where. A contrapositive proof, whose goal is $\lnot P$ from the outset, makes the destination of the argument plain.

Remark 6.3（What exactly is specific to classical logic）

Assuming $P$, deriving a contradiction and concluding $\lnot P$ is the very meaning of the negation symbol, and is accepted in intuitionistic logic as well. What is specific to classical logic is the reverse: assuming $\lnot P$, deriving a contradiction and concluding $P$. The rule $\lnot\lnot P \Rightarrow P$ used there is not provable intuitionistically.

The difference surfaces when existence is asserted. A proof that goes from “it is contradictory that $x$ should fail to exist” to ”$x$ exists” does not produce a single such $x$. A proof that also supplies a concrete construction is called constructive, and the distinction is worth keeping. Cantor’s diagonal argument for comparing the sizes of infinite sets is formally a proof by contradiction, yet it is in fact constructive, since it provides a procedure for building an element missing from a given list. For details see Cardinality and infinity: infinities come in different sizes, and in particular Theorem 6.3［濃度と無限］.

Remark 6.4（Do not use contradiction where contradiction is not needed）

“There are infinitely many primes” is a statement often presented as an example of proof by contradiction. The version by contradiction runs as follows. Suppose there were only finitely many primes $p_1, \ldots, p_r$, and consider $N = p_1 p_2 \cdots p_r + 1$. Since $N \ge 2$, by Example 4.4 it has a prime factor $q$. By assumption this $q$ must equal some $p_i$. But $p_i$ divides the product $p_1 \cdots p_r$, so $N$ leaves remainder $1$ on division by $p_i$, and $p_i$ does not divide $N$. Contradiction.

Yet the argument can be written down directly, without contradiction. Given any finite collection of primes $p_1, \ldots, p_r$, a prime factor $q$ of $N = p_1 \cdots p_r + 1$ differs from every $p_i$ (for the same reason: no $p_i$ divides $N$). In other words, for any finite list we can actually produce a prime not on it. Hence there are infinitely many primes.

This second version supplies a procedure that manufactures an $(r+1)$-st prime from $r$ given primes, and is that much more informative. The argument in Euclid’s Elements, Book IX, Proposition 20, is close to this direct form. Assuming something and extracting a contradiction is powerful, but using it where it is not needed throws information away.

7. The square root of 2 is irrational

7.1. Preliminaries

Definition 7.1（Rational and irrational numbers）

A real number $x$ is rational if it can be written as $x = p/q$ with $p$ an integer and $q$ a non-zero integer. The set of rational numbers is denoted $\mathbb{Q}$. A real number that is not rational is called irrational.

Definition 7.2（Even and odd）

An integer $n$ is even if $n = 2m$ for some integer $m$, and odd if $n = 2m+1$ for some integer $m$.

Every integer is either even or odd, and never both. The first half follows from the division theorem for $2$ (the remainder is $0$ or $1$); the second from the fact that $2m = 2m'+1$ gives $2(m-m') = 1$, whose left-hand side is even while the right-hand side is not divisible by $2$.

Lemma 7.3（Existence of a representation in lowest terms）

For every rational number $x$ there exist an integer $p$ and a natural number $q$ with $x = p/q$ and $\gcd(p, q) = 1$.

Proof（Lemma 7.3）

By Definition 7.1 we can write $x = a/b$ with $a$ an integer and $b$ a non-zero integer. If $b < 0$, change the signs of numerator and denominator simultaneously to get $x = (-a)/(-b)$; so we may assume from the start that $b \ge 1$, that is, $b \in \mathbb{N}$.

Consider the set

$$T = \{\, b' \in \mathbb{N} : \text{there is an integer } a' \text{ with } x = a'/b' \,\} .$$

Since $b \in T$, we have $T \ne \emptyset$, so by the well-ordering property（Axiom 3.1） the set $T$ has a least element $q$. As $q \in T$, there is an integer $p$ with $x = p/q$.

We show that this pair $p, q$ satisfies $\gcd(p,q) = 1$. Put $d = \gcd(p, q)$ and suppose $d > 1$. Choose integers $p', q'$ with $p = d p'$ and $q = d q'$; then $q' = q/d$ is a natural number with $1 \le q' < q$ (since $d > 1$ and $q \ge 1$). Moreover

$$\frac{p'}{q'} = \frac{dp'}{dq'} = \frac{p}{q} = x$$

so $q' \in T$, contradicting the minimality of $q$ in $T$. Hence $d = 1$.

∎

The representation $p/q$ is of course not unique ($1/2 = 2/4 = 3/6 = \cdots$). For the standpoint that defines the rationals as pairs of integers modulo a suitable equivalence relation, see Relations and equivalence relations: what does “the same” mean?, in particular Proposition 6.1［関係と同値関係］. The lemma above says that each such equivalence class contains a representative with least denominator.

Lemma 7.4（If the square is even, so is the number）

For an integer $n$, if $n^2$ is even then $n$ is even.

Proof（Lemma 7.4）

We prove the contrapositive: “if $n$ is odd then $n^2$ is odd”. By Proposition 6.1 this yields the original claim.

Let $n$ be odd. By Definition 7.2 there is an integer $m$ with $n = 2m+1$, and then

$$n^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1 .$$

Since $2m^2 + 2m$ is an integer, $n^2$ is odd in the sense of Definition 7.2.

∎

A direct attempt at this lemma is painful: extracting the shape of $n$ from an equation $n^2 = 2k$ needs heavy machinery such as prime factorization. Taking the contrapositive changes what is assumed into information about shape, $n = 2m+1$, after which one only has to expand. Look at which of the hypothesis and the conclusion carries the information about shape, and move that one to the assumption side: this is the criterion for reaching for a contrapositive proof.

7.2. The proof

Theorem 7.5（Irrationality of the square root of 2）

There is no rational number $x$ with $x^2 = 2$. Consequently, if a real number $\sqrt2$ exists (a real number with $\sqrt2 > 0$ and $(\sqrt2)^2 = 2$), then it is irrational.

Proof（Theorem 7.5）

Suppose, for contradiction, that there is a rational $x$ with $x^2 = 2$.

By Lemma 7.3 we may choose an integer $p$ and a natural number $q$ with

$$x = \frac{p}{q}, \qquad \gcd(p, q) = 1 .$$

Squaring gives $p^2/q^2 = 2$, and since $q^2 \ne 0$ we may multiply by $q^2$ to obtain

$$p^2 = 2 q^2 .$$

Call this equation (A). Its right-hand side has the form $2 \times (\text{an integer})$, so by Definition 7.2 the number $p^2$ is even. By Lemma 7.4, $p$ is even, say $p = 2r$ with $r$ an integer.

Substituting into (A) gives $4r^2 = 2q^2$, and dividing by $2$,

$$q^2 = 2 r^2 .$$

Again the right-hand side has the form $2 \times (\text{an integer})$, so $q^2$ is even, and by Lemma 7.4 once more, $q$ is even.

Thus both $p$ and $q$ are divisible by $2$, so $\gcd(p, q) \ge 2$, contradicting $\gcd(p,q) = 1$.

Hence no rational number satisfies $x^2 = 2$.

∎

Let us record what was used where.

• That a rational can be taken in lowest terms is Lemma 7.3, which rests on the well-ordering property（Axiom 3.1）.
• That $p^2$ even implies $p$ even is Lemma 7.4, proved by contraposition.
• The final blow, the clash with coprimality, is the part done by contradiction.

There is a reason for stating the theorem as “no rational satisfies $x^2 = 2$” rather than ”$\sqrt2$ is irrational”. To assert the latter one must first know that the real number $\sqrt2$ exists (Theorem 5.6［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］), and that existence depends on the continuity of the reals (completeness, the least upper bound property（Axiom 5.1）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］), a fact unavailable in a world of rationals alone. What we proved here is a statement internal to the rationals, using no property of the reals whatsoever.

7.3. An alternative proof by infinite descent

Example 7.6（A proof that does not use lowest terms）

Suppose there is a pair of natural numbers $(p, q)$ with $p^2 = 2q^2$. Put

$$U = \{\, p \in \mathbb{N} : \text{there is } q \in \mathbb{N} \text{ with } p^2 = 2q^2 \,\}$$

so that $U \ne \emptyset$. By the well-ordering property（Axiom 3.1）, $U$ has a least element $p_0$. Choose a corresponding $q_0 \in \mathbb{N}$, so that $p_0^2 = 2q_0^2$.

By the same computation as in the proof of Theorem 7.5, $p_0$ is even, say $p_0 = 2r$ with $r$ an integer, and substituting gives $q_0^2 = 2r^2$. From $p_0 \ge 1$ and $p_0 = 2r$ we get $r \ge 1$, that is, $r \in \mathbb{N}$. Hence $q_0 \in U$.

On the other hand $q_0 \ge 1$ gives $p_0^2 = 2q_0^2 > q_0^2$, and since $p_0, q_0$ are both positive, $p_0 > q_0$. So $q_0 \in U$ with $q_0 < p_0$, contradicting the minimality of $p_0$ in $U$.

Therefore no pair of natural numbers satisfies $p^2 = 2q^2$, and in particular no rational satisfies $x^2 = 2$ (writing $x = p/q$ and adjusting signs produces a pair of natural numbers).

An argument of this shape is called infinite descent: if a solution exists, a smaller one can be built from it, but positive integers cannot keep getting smaller forever. Fermat was fond of the method.

Notice that the only tool used here is the well-ordering property（Axiom 3.1）, the same tool used in the proof of Theorem 3.2. Mathematical induction and infinite descent are two faces of the single fact that the natural numbers do not continue downwards without end. Induction builds up from below, descent comes down from above and collides with the absence of a floor; only the direction differs, and the root is one.

7.4. A generalization

Corollary 7.7（Square roots of non-square natural numbers）

If a natural number $n$ is not a perfect square (that is, there is no natural number $m$ with $n = m^2$), then there is no rational number $x$ with $x^2 = n$.

Proof（Corollary 7.7）

We use uniqueness of prime factorization (the fundamental theorem of arithmetic). Existence of the factorization was shown by strong induction in Example 4.4; the proof of uniqueness is not treated here, but can be found in Takagi’s Shotō Seisūron Kōgi, Chapter 1, listed in the references.

For a prime $\ell$ and a non-zero integer $a$, write $v_\ell(a)$ for the largest $e \ge 0$ such that $\ell^{e}$ divides $a$. Uniqueness of prime factorization gives, for non-zero integers $a, b$,

$$v_\ell(ab) = v_\ell(a) + v_\ell(b)$$

and in particular $v_\ell(a^2) = 2 v_\ell(a)$ is even.

Now suppose there is a rational $x$ with $x^2 = n$. Writing $x = p/q$ with $p$ an integer and $q$ a non-zero integer, we get $p^2 = n q^2$. Since $n \ge 1$ and $q \ne 0$, we have $p \ne 0$. Taking $v_\ell$ of both sides for an arbitrary prime $\ell$,

$$2 v_\ell(p) = v_\ell(n) + 2 v_\ell(q), \qquad \text{that is,} \qquad v_\ell(n) = 2\bigl(v_\ell(p) - v_\ell(q)\bigr) .$$

Hence $v_\ell(n)$ is even for every prime $\ell$. Setting $m = \prod_{\ell} \ell^{\,v_\ell(n)/2}$ (the product running over the finitely many primes with $v_\ell(n) > 0$), all exponents are integers, so $m$ is a natural number, and

$$m^2 = \prod_{\ell} \ell^{\,v_\ell(n)} = n$$

shows that $n$ is a perfect square. Taking the contrapositive gives the claim.

∎

None of $n = 2, 3, 5, 6, 7, 8, 10, \ldots$ is a perfect square, so all of their square roots are irrational. By contrast, for $n = 4$ there is the rational solution $x = 2$. If one tries to imitate the proof of §7.2 for $n = 4$, the statement corresponding to Lemma 7.4 becomes false and the argument stops (see part (3) of Exercise 8.3).

8. Exercises

Exercise 8.1Easy

Let $a, b$ be real numbers. Show that if $a + b \ge 2$ then $a \ge 1$ or $b \ge 1$.

Solution

We prove the contrapositive. The negation of ”$a \ge 1$ or $b \ge 1$” is, by De Morgan's laws（Lemma 4.3）［The Grammar of Mathematics］, ”$a < 1$ and $b < 1$”. So the contrapositive to be proved is

“if $a < 1$ and $b < 1$ then $a + b < 2$”.

Adding $b$ to both sides of $a < 1$ gives $a + b < 1 + b$, and adding $1$ to both sides of $b < 1$ gives $1 + b < 2$. By transitivity of the order, $a + b < 2$.

By Proposition 6.1, the original claim holds.

A direct attempt would require choosing, from $a + b \ge 2$, which of $a$ and $b$ is at least $1$, forcing a case distinction. Taking negations turns the “or” in the conclusion into an “and” in the hypothesis, so that information about both $a$ and $b$ becomes available at once. Whenever the conclusion has the form of an “or”, suspect that a contrapositive is wanted.

Exercise 8.2Standard

Prove by mathematical induction that

$$\sum_{k=1}^{n} \frac{1}{k^2} \le 2 - \frac{1}{n}$$

for every $n \in \mathbb{N}$. Explain also why the same method fails if one tries to prove $\sum_{k=1}^{n} 1/k^2 \le 2$ directly.

Solution

Base step. For $n = 1$ the left-hand side is $1$ and the right-hand side is $2 - 1 = 1$. Equality holds, so the claim is true.

Inductive step. Assume $\sum_{k=1}^{n} 1/k^2 \le 2 - 1/n$. Adding $1/(n+1)^2$ to both sides,

$$\sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 - \frac{1}{n} + \frac{1}{(n+1)^2} .$$

Now $(n+1)^2 = (n+1)(n+1) \ge (n+1) n$ (since $n + 1 \ge n$ and $n+1 > 0$), so

$$\frac{1}{(n+1)^2} \le \frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$$

(the last equality is checked by putting the fractions over a common denominator: $\frac{(n+1) - n}{n(n+1)} = \frac{1}{n(n+1)}$). Substituting,

$$\sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 - \frac{1}{n} + \frac{1}{n} - \frac{1}{n+1} = 2 - \frac{1}{n+1}$$

which is the claim for $n+1$. By Theorem 3.2 it holds for every $n$.

Why $\le 2$ does not go through. Let $P'(n)$ be "$\sum_{k=1}^n 1/k^2 \le 2$". Assuming $P'(n)$ yields only

$$\sum_{k=1}^{n+1} \frac{1}{k^2} \le 2 + \frac{1}{(n+1)^2}$$

whose right-hand side exceeds $2$. We cannot conclude $P'(n+1)$. The hypothesis is too weak: there is no room to absorb what has been added.

The form $2 - 1/n$ is a stronger claim than $\le 2$, but for that very reason the induction hypothesis is stronger too, and it carries a margin $1/n - 1/(n+1)$ that absorbs $1/(n+1)^2$. A stronger statement can be easier to prove by induction — this is called strengthening the induction hypothesis, and it is a basic technique in using induction.

Exercise 8.3Standard

(1) For an integer $n$, prove by contraposition that if $n^2$ is a multiple of $3$ then so is $n$. (2) Using (1), show that there is no rational number $x$ with $x^2 = 3$. (3) State where the same argument breaks down if applied to $x^2 = 4$.

Solution

(1) We prove the contrapositive: “if $n$ is not a multiple of $3$ then neither is $n^2$”. By the division theorem for $3$, an integer $n$ can be written, for some integer $m$, in exactly one of the forms $n = 3m$, $n = 3m+1$, $n = 3m+2$. The last two are the cases where $n$ is not a multiple of $3$.

If $n = 3m+1$ then

$$n^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1$$

so the remainder on division by $3$ is $1$.

If $n = 3m+2$ then

$$n^2 = 9m^2 + 12m + 4 = 3(3m^2 + 4m + 1) + 1$$

so again the remainder is $1$.

In both cases $n^2$ is not a multiple of $3$. By Proposition 6.1 the original claim follows.

(2) Suppose there is a rational $x$ with $x^2 = 3$. By Lemma 7.3 we may take an integer $p$ and a natural number $q$ with $x = p/q$ and $\gcd(p,q) = 1$. Squaring and multiplying by $q^2$ gives $p^2 = 3q^2$.

The right-hand side is a multiple of $3$, so $p^2$ is a multiple of $3$, and by (1) so is $p$, say $p = 3r$ with $r$ an integer. Substituting gives $9r^2 = 3q^2$, and dividing by $3$, $q^2 = 3r^2$. The right-hand side is a multiple of $3$, so $q^2$ is too, and by (1) again so is $q$.

Then $\gcd(p,q) \ge 3$, contradicting $\gcd(p,q) = 1$. Hence no such rational exists.

(3) The statement corresponding to (1) would be “if $n^2$ is a multiple of $4$ then so is $n$”, and this is false. A counterexample is $n = 2$: here $n^2 = 4$ is a multiple of $4$ while $n = 2$ is not. So the argument stops at the step where one would deduce from $p^2 = 4q^2$ that $p$ is a multiple of $4$.

It is only right that it should stop. Since $x = 2$ is a rational with $x^2 = 4$, the conclusion one is trying to prove is itself false. In the language of Corollary 7.7, $4 = 2^2$ is a perfect square. When a proof will not go through, the first thing to doubt is whether the conclusion is true at all.

Exercise 8.4Hard

Show that $\log_2 3$ is irrational. Here $\log_2 3$ denotes the real number $x$ with $2^x = 3$.

Solution

Put $x = \log_2 3$. Since $2^0 = 1 < 3$ and $t \mapsto 2^t$ is strictly increasing, $x > 0$.

Suppose, for contradiction, that $x$ is rational. As $x > 0$, matching the signs of numerator and denominator in the representation of Definition 7.1 lets us write $x = p/q$ with natural numbers $p, q$. Then $2^{p/q} = 3$, and raising both sides to the $q$-th power,

$$2^p = 3^q .$$

The left-hand side. Since $p \ge 1$, we have $2^p = 2 \cdot 2^{p-1}$, and $2^{p-1}$ is an integer, so $2^p$ is even.

The right-hand side. We show by induction on $q$ that $3^q$ is odd. For $q = 1$, $3^1 = 3 = 2\cdot 1 + 1$ is odd. Assuming $3^q$ odd, say $3^q = 2m+1$ with $m$ an integer,

$$3^{q+1} = 3(2m+1) = 6m + 3 = 2(3m+1) + 1$$

which is odd. By Theorem 3.2, $3^q$ is odd for every $q \in \mathbb{N}$.

Thus one and the same integer $2^p = 3^q$ is both even and odd, and as we saw in §7.1 no such integer exists. Contradiction.

Therefore $\log_2 3$ is irrational.

A feature of this proof is that it does not use uniqueness of prime factorization. Parity alone sufficed to tell the two sides of $2^p = 3^q$ apart, so no heavier tool was needed. The fewer the tools, the better; estimating how light a tool will do is itself part of the craft of proof.

References

• Matsuzaka Kazuo, Shūgō, Isō Nyūmon (Introduction to Sets and Topology), Iwanami Shoten, 1968 (in Japanese) — the construction of the natural numbers, the Peano axioms and the treatment of mathematical induction.
• Takagi Teiji, Shotō Seisūron Kōgi (Lectures on Elementary Number Theory), 2nd ed., Kyoritsu Shuppan, 1971 (in Japanese) — Chapter 1 (division of integers, primes, uniqueness of prime factorization).
• G. Pólya, How to Solve It, translated into Japanese by Kakiuchi Kenshin, Maruzen, 1954 (in Japanese) — the section on induction and mathematical induction, on how to form a conjecture before applying induction.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press — Chapter IV, “Irrational Numbers”; various proofs of the irrationality of square roots.
• Euclid, Yūkuriddo Genron (Euclid’s Elements), translated and annotated by Nakamura Kōshirō, Terasaka Hidetaka, Itō Shuntarō and Ikeda Yoshie, Kyoritsu Shuppan (in Japanese) — Book IX, Proposition 20 (the infinitude of primes).
• Maehara Shōji, Sūgaku Kisoron Nyūmon (Introduction to Mathematical Logic), Asakura Shoten, 1977 (in Japanese) — the difference between classical and intuitionistic logic, and the place of double negation elimination and excluded middle.