Well-Ordering Principle

Number Theory · Axiom Academy

LESSON Well-Ordering Principle A fundamental axiom of the positive integers that provides powerful proof techniques in number theory 1. The Well-Ordering Principle More formally: If S is a non-empty subset of the positive integers, then there exists an element m in S such that m ≤ s for all s in S. Why is this an axiom? While it seems intuitively obvious, we cannot prove it from more fundamental properties of numbers. It's a foundational assumption about how positive integers work. 2. Equivalence to Mathematical Induction The Well-Ordering Principle and Mathematical Induction are logically equivalent - you can prove one from the other. They are two sides of the same coin. Proof sketch (WOP implies Induction): Assume WOP holds. To prove induction, suppose P(1) is true and P(k) → P(k+1). Let S be the set of positive integers where P fails. If S is non-empty, by WOP it has a least element m. Since P(1) is true, m > 1, so m-1 is a positive integer where P holds. But then P(m-1) → P(m) by our assumption, contradiction! Thus S is empty and P holds for all positive integers. 3. Example: Proving the Division Algorithm Proof using WOP (existence of r): Consider the set S = a - bk : k ∈ ℤ and a - bk ≥ 0 . This set is non-empty (for sufficiently negative k, a - bk is positive). By WOP, S has a least element r = a - bq for some integer q.

This is the written version of the interactive lesson above. See the full Number Theory course.