Well-Ordering Principle

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

Well-Ordering Principle

Every non-empty set of positive integers has a smallest element. That obvious-sounding fact powers proof by minimum counterexample.

Well-Ordering Visualizer

Pick a preset or add your own numbers, then press Find Minimum. However you build the set, a smallest element turns up.

Visualizing the Well-Ordering Principle

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

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).

Go deeper:Well-Ordering Principle

The Well-Ordering Principle (WOP) states that every non-empty set of positive integers has a smallest element. This seemingly obvious fact is logically equivalent to mathematical induction and provides the foundation for "proof by minimum counterexample."

The technique: assume a counterexample exists, take the smallest one, then use its minimality to derive a contradiction. WOP is especially useful when induction's P(k) → P(k+1) step feels awkward.

Key insight: WOP holds for positive integers but fails for rationals and reals. The set {1/n : n ≥ 1} has no minimum -- you can always find a smaller element by choosing larger n.

Minimum Counterexample

Pick a statement and press Next Step: assume it fails, take the smallest counterexample m, and show m can’t fail after all.

Proof by Minimum Counterexample

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

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
Go deeper:Minimum Counterexample

Walk through a proof by minimum counterexample. Assume the statement fails, let m be the smallest counterexample, then show m cannot actually fail -- contradiction.

Key insight: The power of minimality is that everything below m satisfies the statement. This gives you a wealth of known-true facts to work with when analyzing m itself.

WOP vs Induction

Compare the induction and WOP proofs side by side, then try the quiz and pick which approach fits each statement.

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!

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

WOP Proof (Minimum Counterexample)

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

Induction Proof

  1. 1.Base case (n=1): LHS = 1, RHS = 1(2)/2 = 1. ✓
  2. 2.Inductive hypothesis: Assume 1+2+...+k = k(k+1)/2 for some k ≥ 1.
  3. 3.Inductive step: We must show 1+2+...+k+(k+1) = (k+1)(k+2)/2.
  4. 4.LHS = [1+2+...+k] + (k+1) = k(k+1)/2 + (k+1) (by IH)
  5. 5. = k(k+1)/2 + 2(k+1)/2 = (k+1)(k+2)/2 = RHS ✓
  6. 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!
Go deeper:WOP vs Induction

See the same theorem proved both by induction and by WOP side-by-side. The two approaches are logically equivalent -- proving one proves the other.

Key insight: WOP and induction are two sides of the same coin. WOP says "a non-empty set has a minimum"; induction says "if a set contains 1 and is closed under successor, it contains every positive integer."

Key Takeaways

  • Well-Ordering Principle -- every non-empty subset of the positive integers has a smallest element
  • Minimum counterexample -- assume failure, take the smallest failing case, derive a contradiction
  • Equivalent to induction -- WOP and induction are logically interchangeable
  • Only for well-ordered sets -- works for natural numbers, fails for rationals and reals

Spot a mistake or have an idea?

Search