Well-ordering theorem

Lore & Background

The well-ordering theorem states that every set can be well-ordered by a strict total order such that every non-empty subset has a least element. Ernst Zermelo introduced the axiom of choice as an 'unobjectionable logical principle' to prove the theorem. Georg Cantor considered the well-ordering theorem a 'fundamental principle of thought.' In 1904, Gyula Kőnig claimed to have proven that a well-ordering of the real numbers cannot exist, but Felix Hausdorff found a mistake in the proof a few weeks later. The theorem is considered difficult to visualize for the set of real numbers, as such a visualization would require the axiom of choice.

Reader's Guide

The well-ordering theorem is significant because it establishes that every set can be arranged in a sequence where every non-empty subset has a least element, enabling transfinite induction—a powerful mathematical technique. Within first-order logic, the theorem is equivalent to the axiom of choice: the Zermelo–Fraenkel axioms with the axiom of choice prove the well-ordering theorem, and conversely, the Zermelo–Fraenkel axioms with the well-ordering theorem prove the axiom of choice. In second-order logic, however, the well-ordering theorem is strictly stronger than the axiom of choice. A well-known joke reflects the intuitive difficulty: 'The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?' The theorem's proof from the axiom of choice uses transfinite recursion and a choice function to enumerate a set. Conversely, the axiom of choice can be proven from the well-ordering theorem by taking a well-ordering of the union of a collection of non-empty sets and selecting the least element of each set.

Did You Know?

• The well-ordering theorem is also known as Zermelo's theorem.
• Georg Cantor considered the well-ordering theorem a 'fundamental principle of thought.'
• In 1904, Gyula Kőnig claimed to have proven that a well-ordering of the real numbers cannot exist, but Felix Hausdorff found a mistake in the proof.
• In second-order logic, the well-ordering theorem is strictly stronger than the axiom of choice.