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

From ProofWiki
Jump to navigation Jump to search

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 \subset 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 $P \paren 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 $P \paren 0$ holds.


Suppose $P \paren 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 $P \paren {k + 1}$.

Thus we have proved that:

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

So we see that PCI implies that $P \paren 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.

$\blacksquare$


Sources