Equivalence of Well-Ordering Principle and Induction
Contents
Theorem
The Well-Ordering Principle, the Principle of Finite Induction and the Principle of Complete Induction are logically equivalent.
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$.
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 Finite Induction as PFI;
- The Principle of Complete 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 \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 PFI gives that $S = \N$.
$\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.
$\Box$
WOP implies PFI
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 PFI 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 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 have that the Natural Numbers are Elements of 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 PFI.
$\Box$
Final assembly
So, we have that:
- PFI implies PCI: The Principle of Finite Induction implies the Principle of Complete Induction
- PCI implies WOP: The Principle of Complete Induction implies the Well-Ordering Principle
- WOP implies PFI: The Well-Ordering Principle implies the Principle of Finite Induction.
This completes the result.
$\blacksquare$
Sources
- W.E. Deskins: Abstract Algebra (1964)... (previous)... (next): $\S 2.3$: Theorem $2.17$
- which demonstrates that PFI implies WOP
- W.E. Deskins: Abstract Algebra (1964)... (previous)... (next): $\S 2.3$: Theorem $2.18$
- which demonstrates that WOP implies PCI
- Robert H. Kasriel: Undergraduate Topology (1971)... (previous)... (next): $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: Theorem $17.3$
- which demonstrates that PFI and WOP are equivalent
- 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.
- P.M. Cohn: Algebra Volume 1 (2nd ed., 1982)... (previous)... (next): $\S 2.1$: The integers