# Equivalence of Well-Ordering Principle and Induction

## Theorem

That is:

Principle of Finite Induction: Given a subset $S \subseteq \N$ of the natural numbers which has these properties:
$0 \in S$
$n \in S \implies n + 1 \in S$
then $S = \N$.
Principle of Complete Finite Induction: Given a subset $S \subseteq \N$ of the natural numbers which has these properties:
$0 \in S$
$\set {0, 1, \ldots, n} \subseteq S \implies n + 1 \in S$
then $S = \N$.
Well-Ordering Principle: Every non-empty subset of $\N$ has a minimal element.

## Proof

To save space, we will refer to:

The Well-Ordering Principle as WOP
The Principle of Finite Induction as PFI
The Principle of Complete Finite Induction as PCI.

### PFI implies PCI

Let us assume that the PFI is true.

Let $S \subseteq \N$ which satisfy:

$(A): \quad 0 \in S$
$(B): \quad \set {0, 1, \ldots, n} \subseteq S \implies n + 1 \in S$.

We want to show that $S = \N$, that is, the PCI is true.

Let $P \paren n$ be the propositional function:

$P \paren n \iff \set {0, 1, \ldots, n} \subseteq S$

We define the set $S'$ as:

$S' = \set {n \in \N: P \paren n \text { is true} }$

$P \paren 0$ is true by $(A)$, so $0 \in S'$.

Assume $P \paren k$ is true where $k \ge 0$.

So $k \in S'$, and by hypothesis:

$\set {0, 1, \ldots, k} \subseteq S$

So by $(B)$:

$k + 1 \in S$

Thus:

$\set {0, 1, \ldots, k, k + 1} \subseteq S$.

That last statement means $P \paren {k + 1}$ is true.

This means $k + 1 \in S'$.

Thus we have satisfied the conditions:

$0 \in S'$
$n \in S' \implies n + 1 \in S'$

That is, $S' = \N$, and $P \paren n$ holds for all $n \in \N$.

Hence, by definition:

$S = \N$

So PFI gives that $S = \N$.

Therefore PFI implies PCI.

$\Box$

### PCI implies WOP

Let us assume that the PCI is true.

Let $\O \subsetneqq S \subseteq \N$.

We need to show that $S$ has a minimal element, and so demonstrate that the WOP holds.

Aiming for a contradiction, suppose that:

$(C): \quad S$ has no minimal element.

Let $\map P n$ be the propositional function:

$n \notin S$

Suppose $0 \in S$.

We have that $0$ is a lower bound for $\N$.

Hence by Lower Bound for Subset, $0$ is also a lower bound for $S$.

$0 \notin S$, otherwise $0$ would be the minimal element of $S$.

This contradicts our supposition $(C)$, namely, that $S$ does not have a minimal element.

So $0 \notin S$ and so $\map P 0$ holds.

Suppose $\map P j$ for $0 \le j \le k$.

That is:

$\forall j \in \closedint 0 k: j \notin S$

where $\closedint 0 k$ denotes the closed interval between $0$ and $k$.

Now if $k + 1 \in S$ it follows that $k + 1$ would then be the minimal element of $S$.

So then $k + 1 \notin S$ and so $\map P {k + 1}$.

Thus we have proved that:

$(1): \quad \map P 0$ holds
$(2): \quad \paren {\forall j \in \closedint 0 k: \map P j} \implies \map P {k + 1}$

So we see that PCI implies that $\map P n$ holds for all $n \in \N$.

But this means that $S = \O$, which is a contradiction of the fact that $S$ is non-empty.

So, by Proof by Contradiction, $S$ must have a minimal element.

That is, $\N$ satisfies the Well-Ordering Principle.

Thus PCI implies WOP.

$\Box$

### WOP implies PFI

We assume the truth of WOP.

Let $S \subseteq \N$ which satisfy:

$(D): \quad 0 \in S$
$(E): \quad n \in S \implies n+1 \in S$.

We want to show that $S = \N$, that is, the PFI is true.

Aiming for a contradiction, suppose that:

$S \ne \N$

Consider $S' = \N \setminus S$, where $\setminus$ denotes set difference.

From Set Difference is Subset, $S' \subseteq \N$.

So from WOP, $S'$ has a minimal element.

A lower bound of $\N$ is $0$.

By Lower Bound for Subset, $0$ is also a lower bound for $S'$.

By hypothesis, $0 \in S$.

From the definition of set difference, $0 \notin S'$.

So this minimal element of $S'$ has the form $k + 1$ where $k \in \N$.

We can consider the von Neumann construction of the natural numbers.

By definition of natural number addition, it is noted that $k + 1 \in \N$ is the immediate successor element of $k \in \N$.

Thus $k \in S$ but $k + 1 \notin S$.

From $(E)$, this contradicts the definition of $S$.

Thus if $S' \ne \O$, it has no minimal element.

This contradicts the Well-Ordering Principle, and so $S' = \O$.

So $S = N$.

Thus we have proved that WOP implies PFI.

$\Box$

### Final assembly

So, we have that:

This completes the result.

$\blacksquare$

## Sources

which demonstrates that PFI implies WOP
which demonstrates that WOP implies PCI
which demonstrates that PFI and WOP are equivalent
Students familiar with the principle of induction can gain some sense of perspective in these matters by thinking out how the well-ordering principle can be proved from the principle of mathematical induction and vice versa.