Equivalence of Well-Ordering Principle and Induction

From ProofWiki
Jump to: navigation, search


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:


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

Therefore PFI 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 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:

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.