Well-ordering theorem

From HandWiki
Short description: Theoretic principle in mathematics stating every set can be well-ordered.


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).[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 [math]\displaystyle{ \mathbb{R} }[/math]; 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.[6] 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.[7]

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?[8]

Proof from axiom of choice

The well-ordering theorem follows from the axiom of choice as follows.[9]

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

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

An essential point of this proof is that it involves only a single arbitrary choice, that of [math]\displaystyle{ R }[/math]; applying the well-ordering theorem to each member [math]\displaystyle{ S }[/math] of [math]\displaystyle{ E }[/math] separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each [math]\displaystyle{ S }[/math] a well-ordering would require just as many choices as simply choosing an element from each [math]\displaystyle{ S }[/math]. Particularly, if [math]\displaystyle{ E }[/math] 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. ↑ Kuczma, Marek (2009). An introduction to the theory of functional equations and inequalities. Berlin: Springer. p. 14. ISBN 978-3-7643-8748-8. https://books.google.com/books?id=rqqvbKOC4c8C&pg=PA14. 
  2. ↑ Hazewinkel, Michiel (2001). Encyclopaedia of Mathematics: Supplement. Berlin: Springer. p. 458. ISBN 1-4020-0198-3. https://books.google.com/books?id=ewIaZqqm46oC&pg=PA458. 
  3. ↑ 3.0 3.1 Thierry, Vialar (1945). Handbook of Mathematics. Norderstedt: Springer. p. 23. ISBN 978-2-95-519901-5. https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA23. 
  4. ↑ Georg Cantor (1883), “Ueber unendliche, lineare Punktmannichfaltigkeiten”, Mathematische Annalen 21, pp. 545–591.
  5. ↑ Sheppard, Barnaby (2014). The Logic of Infinity. Cambridge University Press. p. 174. ISBN 978-1-1070-5831-6. https://books.google.com/books?id=RXzsAwAAQBAJ&pg=PA174. 
  6. ↑ Plotkin, J. M. (2005), "Introduction to "The Concept of Power in Set Theory"", Hausdorff on Ordered Sets, History of Mathematics, 25, American Mathematical Society, pp. 23–30, ISBN 9780821890516, https://books.google.com/books?id=M_skkA3r-QAC&pg=PA23 
  7. ↑ Shapiro, Stewart (1991). Foundations Without Foundationalism: A Case for Second-Order Logic. New York: Oxford University Press. ISBN 0-19-853391-8. 
  8. ↑ Krantz, Steven G. (2002), "The Axiom of Choice", in Krantz, Steven G. (in en), Handbook of Logic and Proof Techniques for Computer Science, Birkhäuser Boston, pp. 121–126, doi:10.1007/978-1-4612-0115-1_9, ISBN 9781461201151 
  9. ↑ Jech, Thomas (2002). Set Theory (Third Millennium Edition). Springer. pp. 48. ISBN 978-3-540-44085-7. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Well-ordering_theorem&oldid=3357494"