The Well-Ordering Principle — Mathematics Knowledge System

Overview

The well-ordering principle states that every nonempty subset of the natural numbers has a least element. It is one of the defining properties of ℕ, is logically equivalent to the principle of mathematical induction (given the other Peano axioms), and is the engine behind proof by minimal counterexample: to show a property holds for all natural numbers, assume some counterexample exists, extract the smallest one, and derive a contradiction. The principle fails for other ordered sets such as ℤ or ℚ, which contain nonempty subsets (like ℤ itself, or the negative integers) with no least element.

Intuition

Imagine any nonempty pile of natural numbers scattered on a number line starting at 0 — because there's a definite starting point and the numbers can't sneak infinitely far to the left, you can always point to the smallest one in the pile. This is what makes proof by minimal counterexample work: if a claim were ever false, the set of 'bad' natural numbers where it fails would be nonempty, so it would have a smallest element — and showing that smallest element leads to a contradiction (usually because an even smaller bad number can be built from it) proves no bad numbers exist at all.

Formal Definition

Definition

Formally, the well-ordering principle asserts:

\forall S \subseteq \mathbb{N},\ S \neq \emptyset \implies \exists m \in S \text{ such that } \forall s \in S,\ m \le s

Well-ordering of ℕ

\text{WOP} \iff \text{Principle of Mathematical Induction (given the other Peano axioms)}

Equivalence with induction

Worked Examples

List the smallest few elements satisfying both conditions.
$S = \{12, 14, 16, \dots\}$
By the well-ordering principle S has a least element, and inspection shows it is 12.
$\min(S) = 12$

Answer: 12.

Practice Problems

Difficulty 2/10

Does the set of negative integers have a least element under the usual ordering? Explain why this does not violate well-ordering of ℕ.

Difficulty 4/10

Use the well-ordering principle to prove there is no smallest positive rational number.

Difficulty 3/10

Prove the well-ordering principle implies the principle of induction (sketch).

Quiz

Summary

Every nonempty subset of ℕ has a least element — this is the well-ordering principle.
It is logically equivalent to the principle of mathematical induction given the Peano axioms.
It underlies proof by minimal counterexample and fails for sets like ℤ or ℚ that lack a smallest element.

References

WebsiteWikipedia — Well-ordering principle