Well-Ordering Theorem

Set Theory · Axiom Academy

LESSON The Well-Ordering Theorem Every set can be well-ordered - a shocking consequence of the Axiom of Choice 1. Statement of the Well-Ordering Theorem Examples of well-ordered sets: The natural numbers with their usual ordering Any finite set with any total ordering Ordinal numbers (which we'll see are connected to this theorem) The animation below shows how a well-ordering guarantees a least element in every subset. 2. Proof Outline Using the Axiom of Choice Key Idea: Use AC to recursively "choose" elements to build up the well-ordering. The proof uses transfinite recursion: Use AC to pick an element from X (this will be our first element) Remove that element, getting a smaller set Repeat: at each ordinal stage, use AC to pick from what remains The animation demonstrates this recursive selection process. 3. The Real Numbers Can Be Well-Ordered! The Well-Ordering Theorem tells us something astonishing: there exists a well-ordering on the real numbers ℝ. The proof uses AC non-constructively We have no "formula" or "rule" for this well-ordering We know it exists, but we can't write it down Any definable well-ordering would give us non-constructive knowledge about ℝ 4. Connection to Ordinals and Cardinals The Well-Ordering Theorem has deep connections to ordinal and cardinal numbers: Every cardinal is an ordinal (under AC) We can compare sizes of any two sets via their order types Transfinite induction works on any well-ordered set

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