Well-ordering theorem explained

Well-ordering theorem should not be confused with Well-ordering principle.

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).^{[1] [2]} Ernst Zermelo introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem.^[3] 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.^[3] One famous consequence of the theorem is the Banach–Tarski paradox.

History

Georg Cantor considered the well-ordering theorem to be a "fundamental principle of thought".^[4] However, it is considered difficult or even impossible to visualize a well-ordering of

R ; such a visualization would have to incorporate the axiom of choice.^[5] 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.^[6] 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.^[7]

Let the set we are trying to well-order be

A , and let f be a choice function for the family of non-empty subsets of A . For every ordinal \alpha , define an element a _{\alpha} that is in A by setting a _{\alpha = f(A\smallsetminus\{a} _{\xi\mid\xi<\alpha\})} if this complement A\smallsetminus\{a _{\xi\mid\xi<\alpha\}} is nonempty, or leave a _{\alpha} undefined if it is. That is, a _{\alpha} is chosen from the set of elements of A that have not yet been assigned a place in the ordering (or undefined if the entirety of A has been successfully enumerated). Then the order < on A defined by a _{\alpha} < a _{\beta} if and only if \alpha<\beta (in the usual well-order of the ordinals) is a well-order of A as desired, of order type \sup\{\alpha \mid a _{\alphaisdefined\}} .

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 , take the union of the sets in E and call it X . There exists a well-ordering of X ; let R be such an ordering. The function that to each set S of E associates the smallest element of S , as ordered by (the restriction to S of) R , is a choice function for the collection E .

An essential point of this proof is that it involves only a single arbitrary choice, that of

R ; applying the well-ordering theorem to each member S of E separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each S a well-ordering would require just as many choices as simply choosing an element from each S . Particularly, if E contains uncountably many sets, making all uncountably many choices is not allowed under the axioms of Zermelo-Fraenkel set theory without the axiom of choice.

Notes

1. Book: Kuczma, Marek . Marek Kuczma

   . An introduction to the theory of functional equations and inequalities . 14 . Berlin . Springer . 978-3-7643-8748-8 . 2009 . Marek Kuczma.

2. Book: Hazewinkel, Michiel . Michiel Hazewinkel

   . Encyclopaedia of Mathematics: Supplement . 2001 . Michiel Hazewinkel . 458 . Berlin . Springer . 1-4020-0198-3 .

3. Book: Thierry, Vialar . Handbook of Mathematics . 1945 . 23 . Norderstedt . Springer . 978-2-95-519901-5 .
4. Georg Cantor (1883), “Ueber unendliche, lineare Punktmannichfaltigkeiten”, Mathematische Annalen 21, pp. 545–591.
5. Book: Sheppard, Barnaby . The Logic of Infinity . 174 . Cambridge University Press . 978-1-1070-5831-6 . 2014 .
6. Book: Shapiro, Stewart . Stewart Shapiro

   . Stewart Shapiro . 1991 . Foundations Without Foundationalism: A Case for Second-Order Logic . New York . Oxford University Press . 0-19-853391-8 .

7. Book: Jech, Thomas . Set Theory (Third Millennium Edition) . . 2002 . 978-3-540-44085-7 . 48.

External links

• Mizar system proof: http://mizar.org/version/current/html/wellord2.html