Eight Faces of Induction: Equivalent Principles on the Natural Numbers

Let ℕ = {0,1,2,…}. (If you start at 1, shift base cases accordingly.) This post proves that eight standard principles are all equivalent—different faces of the well-foundedness of (ℕ, ≤).

Table of Contents (click to expand)

1. Eight equivalent principles
   1. (1) Ordinary Induction (PMI)
   2. (2) Complete (Strong) Induction (CMI)
   3. (3) Least Number Principle (LNP) / Well-Ordering
   4. (4) Principle of Finite Descent (PFD)
   5. (5) Well-Founded Induction on (&Nopf;, <)
   6. (6) No Infinite Decreasing Sequence
   7. (7) Course-of-Values Recursion / Iteration
   8. (8) Well-Ordering Theorem for ℕ
2. Implication roadmap
3. Proofs
   1. (1) ⇒ (2) and (2) ⇒ (1)
   2. (1) ⇒ (3) and (3) ⇒ (1)
   3. (3) ⇔ (4) ⇔ (6)
   4. (2) ⇔ (5)
   5. (3) ⇒ (7)
   6. (7) ⇒ (2)
4. Conclusion

Eight equivalent principles

(1) Ordinary Induction (PMI)

If S ⊆ ℕ has 0 ∈ S and ∀n (n ∈ S ⇒ n+1 ∈ S), then S = ℕ.

(2) Complete (Strong) Induction (CMI)

If S ⊆ ℕ has 0 ∈ S and ∀n (({0,…,n} ⊆ S) ⇒ n+1 ∈ S), then S = ℕ.

(3) Least Number Principle (LNP) / Well-Ordering

Every nonempty A ⊆ ℕ has a least element.

(4) Principle of Finite Descent (PFD)

No infinite strictly decreasing sequence exists in ℕ.

(5) Well-Founded Induction on (ℕ,<)

If S ⊆ ℕ satisfies (∀m<n, m ∈ S) ⇒ n ∈ S, then S = ℕ.

(6) No Infinite Decreasing Sequence

Same as (4), stated explicitly for sequences.

(7) Course-of-Values Recursion / Iteration

Given X, a ∈ X, and an operator Φ, there is a unique f:ℕ→X with f(0)=a and f(n+1)=Φ(n, f restricted to {0,…,n}).

(8) Well-Ordering Theorem for ℕ

Every nonempty subset of ℕ has a minimum (essentially (3)).

Implication roadmap

(1) ⇔ (2), (1) ⇔ (3), (3) ⇔ (4) ⇔ (6), (2) ⇔ (5), (3) ⇒ (7), (7) ⇒ (2), and (8) ≡ (3).

Proofs

(1) ⇒ (2) and (2) ⇒ (1)

(1) implies (2) by defining T = {n : {0,…,n} ⊆ S} and applying induction. Conversely, if S satisfies PMI, then from {0,…,n} ⊆ S we know n ∈ S, hence n+1 ∈ S, so CMI applies.

(1) ⇒ (3) and (3) ⇒ (1)

(1) ⇒ (3): Assume A ⊆ ℕ nonempty. Let S = {n : no element of A ≤ n}. If 0 ∉ S, then 0 is least. Otherwise, inductively either a least element appears or S = ℕ, contradicting A ≠ ∅.

(3) ⇒ (1): Suppose S ⊆ ℕ with 0 ∈ S and successor-closed. If S ≠ ℕ, then T = ℕ\S is nonempty; by LNP it has a least element t. Minimality forces t ∈ S, contradiction. Thus S = ℕ.

(3) ⇔ (4) ⇔ (6)

(3) ⇒ (4): If an infinite descent exists, its set has no least element. (4) ⇒ (3): If A has no least, we can build an infinite descent. (4) and (6) are two forms of the same principle.

(2) ⇔ (5)

Well-founded induction on (ℕ,<) is exactly strong induction. Each implies the other directly.

(3) ⇒ (7)

Using the least bad index argument: if recursion fails at some n, take least such n, contradiction. So recursion exists and is unique.

(7) ⇒ (2)

Define f:ℕ→{0,1} via recursion to encode “{0,…,n} ⊆ S”. From uniqueness we deduce f(n)=1 always, hence S = ℕ. So recursion yields complete induction.

Conclusion

All eight principles are equivalent. They are different but interchangeable ways of saying that (ℕ, ≤) is well-founded: no infinite descent, every subset has a least element, induction works, and recursion is legitimate. Each tradition (number theory, logic, computer science) prefers one formulation, but logically they all belong to the same equivalence class.

---