Well-Ordering Principle

Every non-empty set of positive integers has a smallest element

Welcome to the Well-Ordering Principle!

The Well-Ordering Principle (WOP) states that every non-empty set of positive integers has a smallest element. This seemingly simple fact is incredibly powerful—it's logically equivalent to mathematical induction and provides the foundation for "proof by minimum counterexample," one of the most elegant proof techniques in mathematics.

What You'll Learn

The Well-Ordering Principle

Understand why every non-empty set of positive integers has a minimum

Minimum Counterexample Proofs

Master the powerful "assume a counterexample exists, take the smallest" technique

WOP ≡ Induction

See how these two principles are logically equivalent

Classic WOP Proofs

Work through proofs of the Division Algorithm and Fundamental Theorem of Arithmetic

Visualizing the Well-Ordering Principle

Every non-empty set of positive integers has a smallest element. Watch as we find it!

Choose a preset set:

Speed:

S = { }

Empty set - add some positive integers!

Important: Non-Empty Sets Only!

The Well-Ordering Principle only applies to non-empty sets. An empty set has no elements, so it cannot have a smallest element.

Key Insight

This principle seems obvious for finite sets, but it's actually quite powerful. It applies to ANY non-empty subset of positive integers, even infinite ones like "all prime numbers" (minimum = 2) or "all perfect squares" (minimum = 1).

The Well-Ordering Principle

Every non-empty subset of the positive integers ℕ⁺ has a smallest element.

Formally: If S ⊆ ℕ⁺ and S ≠ ∅, then ∃m ∈ S such that m ≤ s for all s ∈ S.

Proof Structure (Minimum Counterexample)

Assume failure: Suppose the statement P(n) is false for some n ∈ ℕ⁺

Form the set: Let S = {n ∈ ℕ⁺ : P(n) is false} — this is non-empty by assumption

Apply WOP: By well-ordering, S has a smallest element m

Derive contradiction: Use that m is minimal to show P(m) must actually be true

Conclude: S must be empty, so P(n) is true for all n

Proof by Minimum Counterexample

The classic WOP proof technique: assume a counterexample exists, take the smallest one, and derive a contradiction.

Choose a proof:

Statement to prove:

Every integer n ≥ 2 can be written as a product of prime numbers

Step 1 of 8State the Goal

Setup

State the Goal

We want to prove that every integer n ≥ 2 can be expressed as a product of primes.

P(n): n can be written as p₁ × p₂ × ... × pₖ where each pᵢ is prime

Setup

Assumption

Construction

Contradiction

Conclusion

WOP vs Induction

The Well-Ordering Principle and Mathematical Induction are logically equivalent. See the same proof done both ways!

Well-Ordering

Principle

Mathematical

Induction

Each principle can be used to prove the other!

Choose a statement:

Statement:

For all positive integers n: 1 + 2 + 3 + ... + n = n(n+1)/2

WOP Proof (Minimum Counterexample)

1.Suppose the statement fails for some n. Let S = {n : statement fails}.
2.By WOP, S has a smallest element m. So the statement fails at m but succeeds for all k < m.
3.If m = 1: LHS = 1, RHS = 1(2)/2 = 1. They match! Contradiction.
4.If m > 1: Since m-1 works, we have 1+...+(m-1) = (m-1)m/2.
5.Adding m to both sides: 1+...+m = (m-1)m/2 + m = (m-1)m/2 + 2m/2 = m(m+1)/2.
6.So the statement holds for m. Contradiction! Therefore S = ∅. ∎

Induction Proof

1.Base case (n=1): LHS = 1, RHS = 1(2)/2 = 1. ✓
2.Inductive hypothesis: Assume 1+2+...+k = k(k+1)/2 for some k ≥ 1.
3.Inductive step: We must show 1+2+...+k+(k+1) = (k+1)(k+2)/2.
4.LHS = [1+2+...+k] + (k+1) = k(k+1)/2 + (k+1) (by IH)
5. = k(k+1)/2 + 2(k+1)/2 = (k+1)(k+2)/2 = RHS ✓
6.By induction, the statement holds for all n ≥ 1. ∎

When to Use Which?

Induction: When P(k) → P(k+1) is easy to show directly
WOP: When proving P(k) → P(k+1) is awkward, or when "smallest counterexample" gives a cleaner contradiction
Either: They're logically equivalent, so use whichever feels more natural!

Common Mistakes to Avoid

✗

Forgetting to verify the set is non-empty

WOP only applies to non-empty sets. You must explicitly assume or show that the set of counterexamples is non-empty before applying WOP.

✗

Not using the minimality

The key step is using that m is the smallest counterexample. If your argument works for any counterexample, you're not actually using WOP!

✗

Confusing with regular contradiction

WOP gives you a structured contradiction via minimality. Regular contradiction proofs don't need to find a "smallest" failing case.

✗

Applying WOP to non-integers

WOP fails for rationals and reals! For example, {1/n : n ∈ ℕ⁺} has no minimum (you can always find a smaller 1/n by choosing larger n).

Key Takeaways

1.The Well-Ordering Principle states: every non-empty subset of ℕ⁺ has a smallest element.
2.WOP and Mathematical Induction are logically equivalent—proving one proves the other.
3."Proof by minimum counterexample" assumes failure, takes the smallest failing case, and derives a contradiction.
4.WOP is especially useful when induction's "P(k) → P(k+1)" step is awkward.
5.WOP only applies to well-ordered sets (like ℕ), not to ℚ or ℝ.