In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. The well-ordering theorem together with Zorn's lemma are the most important mathematical statements that are equivalent to the axiom of choice (often called AC, see also Axiom of choice § Equivalents). Ernst Zermelo introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem. One can conclude from the well-ordering theorem that every set is susceptible to transfinite induction, which is considered by mathematicians to be a powerful technique.
History Georg Cantor considered the well-ordering theorem to be a "fundamental principle of thought". However, it is considered difficult or even impossible to visualize a well-ordering of R {\displaystyle \mathbb {R} } , the set of all real numbers; such a visualization would have to incorporate the axiom of choice. In 1904, Gyula Kőnig claimed to have proven that such a well-ordering cannot exist. A few weeks later, Felix Hausdorff found a mistake in the proof. It turned out, though, that in first-order logic the well-ordering theorem is equivalent to the axiom of choice, in the sense that the Zermelo–Fraenkel axioms with the axiom of choice included are sufficient to prove the well-ordering theorem, and conversely, the Zermelo–Fraenkel axioms without the axiom of choice but with the well-ordering theorem included are sufficient to prove the axiom of choice. (The same applies to Zorn's lemma.) In second-order logic, however, the well-ordering theorem is strictly stronger than the axiom of choice: from the well-ordering theorem one may deduce the axiom of choice, but from the axiom of choice one cannot deduce the well-ordering theorem.
There is a well-known joke about the three statements, and their relative amenability to intuition:The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?
Proof from axiom of choice The well-ordering theorem follows from the axiom of choice as follows.Let the set we are trying to well-order be A {\displaystyle A} , and let f {\displaystyle f} be a choice function for the family of non-empty subsets of A {\displaystyle A} . For every ordinal α {\displaystyle \alpha } , define by transfinite recursion an element a α {\displaystyle a_{\alpha }} that is in A {\displaystyle A} by setting a α = f ( A ∖ { a ξ ∣ ξ < α } ) {\displaystyle a_{\alpha }\ =\ f(A\setminus \{a_{\xi }\mid \xi <\alpha \})} if this complement A ∖ { a ξ ∣ ξ < α } {\displaystyle A\setminus \{a_{\xi }\mid \xi <\alpha \}} is nonempty, or leaves a α {\displaystyle a_{\alpha }} undefined if the complement is empty. That is, a α {\displaystyle a_{\alpha }} is chosen from the set of elements of A {\displaystyle A} that have not yet been assigned a place in the ordering (or undefined if the entirety of A {\displaystyle A} has been successfully enumerated). Then the order < {\displaystyle <} on A {\displaystyle A} defined by a α < a β {\displaystyle a_{\alpha }<a_{\beta }} if and only if α < β {\displaystyle \alpha <\beta } (in the usual well-order of the ordinals) is a well-order of A {\displaystyle A} as desired, of order type { α ∣ a α is defined } {\displaystyle \{\alpha \mid a_{\alpha }{\text{ is defined}}\}} (in the von Neumann representation).
Proof of axiom of choice The axiom of choice can be proven from the well-ordering theorem as follows.
To make a choice function for a collection of non-empty sets, E {\displaystyle E} , take the union of the sets in E {\displaystyle E} and call it X {\displaystyle X} . There exists a well-ordering of X {\displaystyle X} ; let R {\displaystyle R} be such an ordering. The function that to each set S {\displaystyle S} of E {\displaystyle E} associates the smallest element of S {\displaystyle S} , as ordered by (the restriction to S {\displaystyle S} of) R {\displaystyle R} , is a choice function for the collection E {\displaystyle E} . An essential point of this proof is that it involves only a single arbitrary choice, that of R {\displaystyle R} ; applying the well-ordering theorem to each member S {\displaystyle S} of E {\displaystyle E} separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each S {\displaystyle S} a well-ordering would require just as many choices as simply choosing an element from each S {\displaystyle S} .
Notes
External links Mizar system proof: http://mizar.org/version/current/html/wellord2.html