Mathematical Induction

Mathematical induction is the fundamental proof technique for statements about natural numbers. In set theory, induction is not an axiom but a theorem derivable from the structure of $\omega$ and the axiom of foundation.

TheoremPrinciple of Mathematical Induction

Let $P(n)$ be a property defined for natural numbers. If:

Base case: $P(0)$ holds
Inductive step: For all $n \in \omega$ , if $P(n)$ holds then $P(n+1)$ holds

Then $P(n)$ holds for all $n \in \omega$ .

Proof

Suppose $P(0)$ and $\forall n(P(n) \Rightarrow P(n+1))$ . Let $S = \{n \in \omega : P(n)\}$ . We must show $S = \omega$ .

By hypothesis, $0 \in S$ (base case). Also, if $n \in S$ then $P(n)$ holds, so $P(n+1)$ holds by the inductive step, hence $n+1 \in S$ . Thus $S$ is an inductive set.

Since $\omega$ is the smallest inductive set, and $S$ is an inductive set with $S \subseteq \omega$ , we conclude $\omega \subseteq S$ . Combined with $S \subseteq \omega$ , we have $S = \omega$ .

■

ExampleSum of First n Natural Numbers

Prove that $0 + 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ for all $n \in \omega$ .

Base case: $n = 0$ . The sum is $0 = \frac{0 \cdot 1}{2}$ . ✓

Inductive step: Assume $0 + 1 + \cdots + n = \frac{n(n+1)}{2}$ . Then:

\begin{align*} 0 + 1 + \cdots + n + (n+1) &= \frac{n(n+1)}{2} + (n+1) \\ &= \frac{n(n+1) + 2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2} \end{align*}

By induction, the formula holds for all $n \in \omega$ .

DefinitionStrong Induction

An equivalent form of induction, often called strong induction or complete induction, states:

If for all $n \in \omega$ ,

[\forall m < n \, P(m)] \Rightarrow P(n)

then $P(n)$ holds for all $n \in \omega$ .

Here $m < n$ means $m \in n$ in set-theoretic terms.

Strong induction does not require a separate base case because the implication vacuously holds for $n = 0$ (there are no $m < 0$ ).

TheoremEquivalence of Induction Forms

The principle of mathematical induction and strong induction are equivalent. Each can be derived from the other.

Proof

(Strong $\Rightarrow$ Weak): Assume strong induction. To prove weak induction, suppose $P(0)$ and $\forall n(P(n) \Rightarrow P(n+1))$ . For any $n$ , if $\forall m < n \, P(m)$ , then either $n = 0$ (so $P(0)$ by hypothesis) or $n = k+1$ for some $k$ , and $P(k)$ holds (since $k < n$ ), so $P(n) = P(k+1)$ by the inductive step. By strong induction, $P(n)$ for all $n$ .

(Weak $\Rightarrow$ Strong): Assume weak induction. Define $Q(n) = \forall m \leq n \, P(m)$ . Then $Q(0) \Leftrightarrow P(0)$ . If $Q(n)$ , then all $P(m)$ for $m \leq n$ hold. By the strong induction hypothesis, $P(n+1)$ holds, so $Q(n+1)$ . By weak induction, $Q(n)$ for all $n$ , hence $P(n)$ for all $n$ .

■

DefinitionRecursion Theorem

The recursion theorem states that for any set $A$ , any element $a \in A$ , and any function $h: A \to A$ , there exists a unique function $f: \omega \to A$ such that:

\begin{align*} f(0) &= a \\ f(n+1) &= h(f(n)) \text{ for all } n \in \omega \end{align*}

This theorem justifies recursive definitions and is proved using transfinite recursion on ordinals.

ExampleFibonacci Numbers

The Fibonacci sequence can be defined by two-place recursion:

\begin{align*} F_0 &= 0, \quad F_1 = 1 \\ F_{n+2} &= F_{n+1} + F_n \text{ for } n \geq 0 \end{align*}

To formalize this, we use the recursion theorem with state space $\mathbb{N} \times \mathbb{N}$ and the transition function $h(a, b) = (b, a+b)$ . Starting from $(0, 1)$ , this generates pairs $(F_n, F_{n+1})$ .

TheoremWell-Ordering Principle

Every non-empty subset of $\omega$ has a least element under the natural ordering. This is equivalent to mathematical induction.

Proof

(WO $\Rightarrow$ Induction): Suppose induction fails for some property $P$ . Let $S = \{n \in \omega : \neg P(n)\}$ be the set of counterexamples. If $S \neq \emptyset$ , it has a least element $m$ . Since $P(0)$ , we have $m > 0$ , so $m = k+1$ for some $k$ . Since $m$ is minimal in $S$ , we have $P(k)$ . By the inductive step, $P(k+1) = P(m)$ , contradicting $m \in S$ .

(Induction $\Rightarrow$ WO): Suppose $S \subseteq \omega$ has no least element. Define $P(n) = \forall m \leq n (m \notin S)$ . Then $P(0)$ (else $0$ would be the least element). If $P(n)$ , then all $m \leq n$ satisfy $m \notin S$ . If $n+1 \in S$ , it would be minimal (since no smaller element is in $S$ ), contradiction. So $P(n+1)$ . By induction, $P(n)$ for all $n$ , so $S = \emptyset$ .

■

Remark

The equivalence of induction, strong induction, well-ordering, and recursion demonstrates that these are different perspectives on the same fundamental property of $\omega$ : its well-founded structure. This structure, ultimately derived from the axiom of foundation, is what makes natural numbers suitable for proof by induction and definition by recursion.

Mathematical induction is not merely a proof technique but a deep structural property of the natural numbers, reflecting their construction as the minimal inductive set in ZFC set theory.