Lesson · Induction and Recursion · Foundations

The Well-Ordering Principle

Induction has to rest on something. The well-ordering principle is that something: every nonempty subset of ℕ has a smallest member. From it, induction follows in half a page.

Open the interactive lesson Practice

Every nonempty S ⊆ ℕ has a least element. FALSE for ℤ: {…, −2, −1, 0} has no least element FALSE for ℚ⁺: {x ∈ ℚ : x > 0} has no least element well-ordering ⟺ induction ⟺ strong induction

The axiom the course rests on

Core ideas

What this lesson establishes

Before proving anything by induction it is worth knowing what induction itself rests on, and that it is not obvious for every number system.

Well-ordering is a property of ℕ, not of numbers

ℤ and ℚ⁺ both fail it. The property that makes induction work is specific to the naturals, and it is why induction is about ℕ.

It is equivalent to induction

Each can be derived from the other. Which is taken as the axiom is a matter of presentation, not of mathematics.

It powers the minimal-counterexample argument

"Take the smallest n for which the claim fails" is well-ordering used directly, and it is often the shortest route to a result.

The material

The principle and what follows from it

Statement, the systems where it fails, and the derivation of induction.

Definition · Well-ordering principle

Every nonempty subset of ℕ has a least element. That is: if S ⊆ ℕ and S ≠ ∅, there is m ∈ S with m ≤ s for every s ∈ S.

The principle is not a theorem about numbers in general; it is a specific property of ℕ that fails elsewhere and has to be assumed or derived from an equivalent assumption.

In ℤ, the set of negative integers is nonempty and has no least element — every candidate has a smaller one below it.
In ℚ⁺, the set of positive rationals is nonempty and has no least element: whatever q you name, q/2 is smaller and still positive.
In ℝ, the open interval (0, 1) has no least element for the same reason.

Theorem · Well-ordering implies induction

Suppose P(0) holds and P(k) → P(k+1) for every k ∈ ℕ. Then P(n) holds for every n ∈ ℕ.

Let S = {n ∈ ℕ : P(n) is false} and suppose S ≠ ∅. By well-ordering S has a least element m.

m ≠ 0, because P(0) holds. So m ≥ 1 and m − 1 is a natural number. Since m is the least member of S, m − 1 ∉ S, so P(m − 1) is true.

But the hypothesis gives P(m − 1) → P(m), so P(m) is true — contradicting m ∈ S.

Therefore S = ∅, which is to say P(n) holds for every n.

□

That proof is the entire justification for the technique the rest of the course uses, and it is worth reading twice. The base case rules out m = 0; the inductive step rules out every other m; well-ordering is what guarantees that if any counterexample existed, a smallest one would.

Minimal counterexample as a technique

The proof above is itself a template. To show a claim holds for all n, assume it fails somewhere, take the least such n, and derive a contradiction — usually by producing a smaller counterexample. This is sometimes called infinite descent.

Theorem · Every integer greater than 1 has a prime factor

For every integer n > 1 there is a prime p with p | n.

Suppose not, and let S be the set of integers greater than 1 with no prime factor. If S ≠ ∅, well-ordering gives a least element m.

m is not prime, since a prime divides itself. So m = ab with 1 < a < m. Now a > 1 and a < m, so a ∉ S by minimality, so a has a prime factor p.

But p | a and a | m, so p | m, contradicting m ∈ S.

Hence S = ∅.

□

Notice the shape: minimality of m is what licenses the claim about a. Without well-ordering there would be no smallest counterexample to reason about, and the argument would have nothing to grip.

Interactive

Check P(n), then notice checking is not proving

Two of these statements are false

Method

Using minimal counterexample

Assume failure, take the smallest, break it.

Assume the claim fails somewhere

Let S be the set of n for which it fails, and suppose S ≠ ∅.

Take the least element of S

Well-ordering guarantees one exists. This is the step that is unavailable over ℤ or ℚ.

Derive a contradiction from minimality

Usually by exhibiting a smaller counterexample, or by showing the claim holds at m after all because it holds below m.

Conclude S is empty

Which is the claim, stated the other way round.

Well-ordering

Score 0 / 0

Choose the answer you can justify.

The division algorithm, by well-ordering

For a ∈ ℤ and d > 0 there are q, r with a = dq + r and 0 ≤ r < d.

Let S = { a − dq : q ∈ ℤ, a − dq ≥ 0 }. S is nonempty: take q very negative and a − dq is large and positive. S ⊆ ℕ by construction, so well-ordering gives a least element r = a − dq. Claim r < d. Suppose r ≥ d. Then r − d = a − d(q + 1) ≥ 0, so r − d ∈ S and r − d < r, contradicting minimality of r. So 0 ≤ r < d and a = dq + r. ∎

Number Theory and Cryptography opens with this theorem and uses it in every lesson. Here it is an example of the technique; there it is the foundation of modular arithmetic. The uniqueness of q and r needs a separate short argument.

Common mistakes

Assuming well-ordering holds for ℤ or ℚIt does not. A minimal-counterexample argument over the integers or the rationals needs a lower bound before it is legitimate.

Forgetting to show the set is nonemptyWell-ordering applies only to nonempty sets. In the division algorithm proof, exhibiting one member of S was a necessary step.

Taking the least element of a set that is not a subset of ℕThe set in the division algorithm proof was constructed to consist of non-negative integers precisely so the principle would apply.

Check your understanding

✓

Finish when you can prove induction from well-ordering unaided.

Write the argument out: assume the set of counterexamples is nonempty, take its least element, and use the base case and the step to contradict minimality. Understanding why induction is valid makes “Mathematical Induction”, “Induction with Sums and Products”, “Induction with Inequalities and Divisibility” and “Strong Induction” mechanical.

Note: Every set can be well-ordered — this is the well-ordering theorem, and it is equivalent to the axiom of choice. That is a far deeper statement than the principle here, which is only about ℕ and needs no such machinery.