Exercise A0.V.3.05

Proposition

Mathematical induction on $\mathbb{N}$ is equivalent to the existence of a well-ordering of $\mathbb{N}.$

Proof

Suppose that $\mathbb{N}$ is well-ordered and let $S \subseteq \mathbb{N}$ such that $\left((\forall b \in \mathbb{N}): b < a \implies b \in S \right) \implies a \in S.$

Assume, for the sake of contradiction, that $H = \mathbb{N} \setminus S$ is non-empty. Then, by well-ordering, $H$ has the least element $a \in H.$ Since all elements of $\mathbb{N}$ smaller than $a$ are in $S,$ it must be that $a \in S.$ This is a contradiction.

Suppose, conversely, that the induction principle holds for $\mathbb{N}.$ Let $S$ be a subset of $\mathbb{N}$ such that $S$ has no least element.

We will prove inductively that $a \notin S$ for all $a \in \mathbb{N}.$ For the base case, if $0 \in S$ then $0$ would be the least element of $S.$ Thus $0 \notin S.$ Suppose none of natural numbers less than $n$ are in $S.$ If $n \in S$ then $n$ would be the least element, so $n \notin S.$ Thus, $S$ has no members.

A non-empty subset of $\mathbb{N},$ therefore, has to have the least element.

$\blacksquare$