Well-Orders

Set Theory · Axiom Academy

Every non-empty subset has a least element: the foundation of mathematical induction A total order ≤ on a set A is a well order if it satisfies: Well-ordering property: Every non-empty subset S ⊆ A has a least element. That is, for every S ≠ ∅, there exists m ∈ S such that m ≤ x for all x ∈ S. This means we can always find a "first" element in any subset, no matter how it's selected. A well order is always a total order (all elements comparable), but adds this crucial "least element" guarantee. 2. Examples: What is Well-Ordered? Natural numbers (ℕ) with ≤: This is the prototypical well order! Every subset has a least element Example: 5, 12, 3, 100 has least element 3 Even infinite subsets work: the even numbers have least element 2 Non-example: Integers (ℤ) with ≤ ℤ itself has no least element (goes to -∞) The negative integers ..., -3, -2, -1 have no least element Therefore ℤ is NOT well-ordered 3. The Well-Ordering Principle The Well-Ordering Principle states: Every non-empty subset of ℕ has a least element. This is often taken as an axiom for the natural numbers. It's equivalent to the principle of mathematical induction! Guarantees we can find a "smallest" counterexample in proof by contradiction Allows us to define sequences by recursion Forms the basis for induction: if S ⊆ ℕ is non-empty, its least element gives us a starting point 4. Connection to Mathematical Induction The well-ordering principle and mathematical induction are equivalent! Here's why:

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