Equivalence of Well-Ordering Principle and Induction

Theorem

The Well-Ordering Principle, the Principle of Mathematical Induction and the Principle of Complete Induction are logically equivalent.

That is:

Principle of Mathematical 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$.

iff:

Principle of Complete Induction: Given a subset $S \subseteq \N$ of the natural numbers which has these properties:

$0 \in S$

$\left\{{0, 1, \ldots, n}\right\} \subseteq S \implies n+1 \in S$

then $S = \N$.

iff:

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 Mathematical Induction as PMI;
• The Principle of Complete Induction as PCI.

PMI implies PCI

Let us assume that the PMI is true.

Let $S \subseteq \N$ which satisfy:

$(A): \quad 0 \in S$

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

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

Let $P \left({n}\right)$ be the propositional function:

$P \left({n}\right) \iff \left\{{0, 1, \ldots, n}\right\} \subseteq S$

We define the set $S\,'$ as:

$S\,' = \left\{{n \in \N: P \left({n}\right) \text { is true}}\right\}$

$P \left({0}\right)$ is true by $(A)$, so $0 \in S\,'$.

Assume $P \left({k}\right)$ is true where $k \geq 0$.

So $k \in S\,'$, and by hypothesis, $\left\{{0, 1, \ldots, k}\right\} \subseteq S$

So by $(B)$, $k + 1 \in S$.

Thus $\left\{{0, 1, \ldots, k, k + 1}\right\} \subseteq S$.

That last statement means $P \left({k + 1}\right)$ 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 \left({n}\right)$ holds for all $n \in \N$.

Hence, by definition, $S = \N$.

So PMI gives that $S = \N$.

Therefore PMI implies PCI.

$\Box$

PCI implies WOP

Let us assume that the PCI is true.

Let $\varnothing \subset S \subseteq \N$.

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

With a view to obtaining a contradiction, assume that:

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

Let $P \left({n}\right)$ 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 $P \left({0}\right)$ holds.

Suppose $P \left({j}\right)$ for $0 \le j \le k$.

That is:

$\forall j \in \left[{0 .. k}\right]: j \notin S$

where $\left[{0 .. k}\right]$ 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 $P \left({k+1}\right)$.

Thus we have proved that:

$(1): \quad P \left({0}\right)$ holds

$(2): \quad \left({\forall j \in \left[{0 .. k}\right]: P \left({j}\right)}\right) \implies P \left({k+1}\right)$.

So we see that PCI implies that $P \left({n}\right)$ holds for all $n \in \N$.

But this means that $S = \varnothing$, 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 PMI

We assume the truth of the Well-Ordering Principle.

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 PMI is true.

With a view to obtaining a contradiction, assume that:

$S \ne \N$

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

From Set Difference Subset, $S\,' \subseteq \N$ and 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 have that the Natural Numbers are Elements of the Minimal Infinite Successor Set.

From Peano's Axioms Uniquely Define Natural Numbers 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 \varnothing$, it has no minimal element.

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

So $S = N$.

Thus we have proved that WOP implies PMI.

$\Box$

Final assembly

So, we have that:

• PMI implies PCI: The Principle of Mathematical Induction implies the Principle of Complete Induction
• PCI implies WOP: The Principle of Complete Induction implies the Well-Ordering Principle
• WOP implies PMI: The Well-Ordering Principle implies the Principle of Mathematical Induction.

This completes the result.

$\blacksquare$

Sources

• W.E. Deskins: Abstract Algebra (1964): $\S 2.3$: Theorem $2.17$

which demonstrates that PMI implies WOP

• W.E. Deskins: Abstract Algebra (1964): $\S 2.3$: Theorem $2.18$

which demonstrates that WOP implies PCI

• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 10$:

"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."

• University of Western Ontario: Mathematics 310a: The Principle of Mathematical Induction and the Well Ordering Principle