Equivalence of Well-Ordering Principle and Induction

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⊆N of the natural numbers which has these properties:

0∈S

n∈S⟹n+1∈S

then S=N .

iff:

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

0∈S

{0,1,…,n}⊆S⟹n+1∈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⊆N which satisfy:

(A):0∈S

(B):{0,1,…,n}⊆S⟹n+1∈S .

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

Let P(n) be the propositional function:

P(n)⟺{0,1,…,n}⊆S

We define the set S ′ as:

S ′ ={n∈N:P(n) is true}

P(0) is true by (A) , so 0∈S ′ .
Assume P(k) is true where k≥0 .
So k∈S ′ , and by hypothesis, {0,1,…,k}⊆S
So by (B) , k+1∈S .
Thus {0,1,…,k,k+1}⊆S .
That last statement means P(k+1) is true.
This means k+1∈S ′ .
Thus we have satisfied the conditions:

0∈S ′

n∈S ′ ⟹n+1∈S ′ .

That is, S ′ =N , and P(n) holds for all n∈N .
Hence, by definition, S=N .
So PFI gives that S=N .
Therefore PFI implies PCI.
□

PCI implies WOP

Let us assume that the PCI is true.
Let ∅⊂S⊆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):S has no minimal element.

Let P(n) be the propositional function:

n∉S

Suppose 0∈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∉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∉S and so P(0) holds.

Suppose P(j) for 0≤j≤k .
That is:

∀j∈[0..k]:j∉S

where [0..k] denotes the closed interval between 0 and k .
Now if k+1∈S it follows that k+1 would then be the minimal element of S .
So then k+1∉S and so P(k+1) .
Thus we have proved that:

(1):P(0) holds

(2):(∀j∈[0..k]:P(j))⟹P(k+1) .

So we see that PCI implies that P(n) holds for all n∈N .
But this means that S=∅ , 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.
□

WOP implies PFI

We assume the truth of the Well-Ordering Principle.
Let S⊆N which satisfy:

(D):0∈S

(E):n∈S⟹n+1∈S .

We want to show that S=N , that is, the PFI is true.

With a view to obtaining a contradiction, assume that:

S≠N

Consider S ′ =N∖S , where ∖ denotes set difference.
From Set Difference is Subset, S ′ ⊆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∈S .
From the definition of set difference, 0∉S ′ .
So this minimal element of S ′ has the form k+1 where k∈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∈N is the immediate successor element of k∈N .
Thus k∈S but k+1∉S .
From (E) , this contradicts the definition of S .
Thus if S ′ ≠∅ , it has no minimal element.
This contradicts the Well-Ordering Principle, and so S ′ =∅ .
So S=N .
Thus we have proved that WOP implies PFI.
□

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.