Well-Ordering Principle

Intro to Proofs · Axiom Academy

LESSON The Well-Ordering Principle A proof technique equivalent to induction: leverage the existence of a least element to settle results about every natural number. 1. The Well-Ordering Principle Every non-empty subset of has a smallest element More formally: if and , then there exists with for all . The Well-Ordering Principle and Mathematical Induction are equivalent — each can be used to prove the other. This gives two complementary tools for proving statements about the natural numbers. Inductive step: show that if P(k) is true, then P(k+1) is true. 3. Proof by Smallest Counterexample The standard WOP proof technique uses contradiction: Assume (for contradiction) that P(n) fails for some . Let , the set of counterexamples. By WOP, S has a smallest element m . Derive a contradiction by showing either: P(m) must actually be true, or there exists a smaller counterexample than m . 4. Choosing the Right Ordering Sometimes the "obvious" ordering doesn't work. The key is to find an ordering where you can relate the minimal element to smaller elements in a useful way. Use the usual when the problem naturally involves sequential reasoning. Order pairs (a,b) by a + b , or order numbers by absolute value when sums or distances matter. For pairs (a,b) , order lexicographically: first by a , then by b when the a 's are equal. Sometimes you need a custom ordering that captures what "smaller" means in your specific context. 5. Example: Every Has a Prime Factor

This is the written version of the interactive lesson above. See the full Intro to Proofs course.