# Equivalence of Well-Ordering Principle and Induction/Proof/PCI implies WOP

## Theorem

The Principle of Complete Induction implies the Well-Ordering Principle.

That is:

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

implies:

- Well-Ordering Principle: Every nonempty subset of $\N$ has a minimal element.

## Proof

To save space, we will refer to:

- The Principle of Complete Induction as
**PCI** - The Well-Ordering Principle as
**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.

$\blacksquare$

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts*... (previous) ... (next): Introduction $\S 4$: The natural numbers - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $2$: Integers and natural numbers: $\S 2.1$: The integers - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 4$: The Integers and the Real Numbers