Course contentsShow
← Mathematics
Lesson 2519 of 3,12150. Discrete Math — Logic and ProofFree lesson

Equivalence of Induction and Well-Ordering

Understand why mathematical induction, strong induction, and well-ordering are logically equivalent.

Equivalence of Induction and Well-Ordering

What You'll Learn

You'll discover why mathematical induction, strong induction, and the well-ordering principle are actually three different faces of the same fundamental truth about natural numbers.

The Core Idea

At first glance, mathematical induction and well-ordering seem like entirely different tools. Induction says "if a property holds for a base case and passes from n to n+1, it holds for all natural numbers." Well-ordering says "every non-empty set of natural numbers has a smallest element." Surprisingly, these are logically equivalent—you can prove any one of them using any other.

Why They're the Same Thing

Think of it like having three keys to the same lock:

Induction → Well-Ordering: Suppose some non-empty set S of natural numbers has no smallest element. Then 0 ∉ S (otherwise 0 would be smallest). If 0,1,…,k all aren't in S, then k+1 can't be either (or it would be smallest). By induction, S is empty—contradiction!

Well-Ordering → Induction: Suppose P(0) holds and P(k)→P(k+1) for all k, but P doesn't hold for all n. Let S = {n : P(n) is false}. By well-ordering, S has a smallest element m. Since P(0) is true, m > 0. But then m-1 satisfies P, so P(m-1)→P(m), meaning P(m) is true—contradiction!

Strong induction fits in similarly: it's just another way to express the same underlying structure of the natural numbers.

Why This Matters

This equivalence means you can choose whichever proof technique fits your problem best—they're all drawing from the same logical foundation. Sometimes well-ordering gives the cleanest argument; other times induction feels more natural.

Key Takeaway: Mathematical induction, strong induction, and well-ordering are three logically equivalent formulations of the same fundamental property of natural numbers—you can prove any of them from any other.