Editing Well-ordering theorem

{{short description|Theoretic principle in mathematics stating every set can be well-ordered.}}
{{redirect|Zermelo's theorem|Zermelo's theorem in game theory|Zermelo's theorem (game theory)}}
{{distinguish|Well-ordering principle}}

In [[mathematics]], the '''well-ordering theorem''', also known as '''Zermelo's theorem''', states that every [[Set (mathematics)|set]] can be [[well-order]]ed. 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 {{section link|Axiom of choice|Equivalents}}).<ref>{{cite book |url=https://books.google.com/books?id=rqqvbKOC4c8C&pg=PA14 |title=An introduction to the theory of functional equations and inequalities |page=14 |location=Berlin |publisher=Springer |isbn=978-3-7643-8748-8 |first=Marek |last=Kuczma |year=2009 |authorlink=Marek Kuczma}}</ref><ref>{{cite book |url=https://books.google.com/books?id=ewIaZqqm46oC&pg=PA458 |title=Encyclopaedia of Mathematics: Supplement |first=Michiel |last=Hazewinkel |year=2001 |authorlink=Michiel Hazewinkel |page=458 |location=Berlin |publisher=Springer |isbn=1-4020-0198-3 }}</ref> [[Ernst Zermelo]] introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem.<ref name = "zer">{{cite book |url=https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA23 |title=Handbook of Mathematics |first=Vialar |last=Thierry |year=1945 |page=23 |location=Norderstedt |publisher=Springer |isbn=978-2-95-519901-5 }}</ref> 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.<ref name = "zer"/> 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".<ref>Georg Cantor (1883), “Ueber unendliche, lineare Punktmannichfaltigkeiten”, ''Mathematische Annalen'' 21, pp. 545–591.</ref>  However, it is considered difficult or even impossible to visualize a well-ordering of <math>\mathbb{R}</math>, the set of all [[real number]]s; such a visualization would have to incorporate the axiom of choice.<ref>{{cite book |url=https://books.google.com/books?id=RXzsAwAAQBAJ&pg=PA174 |title=The Logic of Infinity |page=174 |publisher=Cambridge University Press |isbn=978-1-1070-5831-6 |first=Barnaby |last=Sheppard |year=2014 }}</ref> 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.<ref>{{citation|title=Hausdorff on Ordered Sets|volume=25|series=History of Mathematics|first=J. M.|last=Plotkin|publisher=American Mathematical Society|isbn=9780821890516|year=2005|contribution=Introduction to "The Concept of Power in Set Theory"|pages=23–30|url=https://books.google.com/books?id=M_skkA3r-QAC&pg=PA23}}</ref>  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.<ref>{{cite book |authorlink=Stewart Shapiro |first=Stewart |last=Shapiro |year=1991 |title=Foundations Without Foundationalism: A Case for Second-Order Logic |location=New York |publisher=Oxford University Press |isbn=0-19-853391-8 }}</ref>
There is a well-known joke about the three statements, and their relative amenability to intuition:<blockquote>The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about [[Zorn's lemma]]?<ref>{{Citation|last=Krantz|first=Steven G.|chapter=The Axiom of Choice|date=2002|pages=121–126|editor-last=Krantz|editor-first=Steven G.|publisher=Birkhäuser Boston|language=en|doi=10.1007/978-1-4612-0115-1_9|isbn=9781461201151|title=Handbook of Logic and Proof Techniques for Computer Science}}</ref></blockquote>

==Proof from axiom of choice ==

The well-ordering theorem follows from the axiom of choice as follows.<ref>{{Cite book |last=Jech |first=Thomas |title=Set Theory |publisher=[[Springer Publishing|Springer]] |year=2002 |isbn=978-3-540-44085-7 |pages=48|edition=Third Millennium }}</ref><blockquote>Let the set we are trying to well-order be <math>A</math>, and let <math>f</math> be a choice function for the family of non-empty subsets of <math>A</math>. For every [[ordinal number|ordinal]] <math>\alpha</math>, define an element <math>a_\alpha</math> that is in <math>A</math> by setting <math>a_\alpha\ =\ f(A\smallsetminus\{a_\xi\mid\xi<\alpha\})</math> if this complement <math>A\smallsetminus\{a_\xi\mid\xi<\alpha\}</math> is nonempty, or leaves <math>a_\alpha</math> undefined if it is. That is, <math>a_\alpha</math> is chosen from the set of elements of <math>A</math> that have not yet been assigned a place in the ordering (or undefined if the entirety of <math>A</math> has been successfully enumerated). Then the order <math><</math> on <math>A</math> defined by <math>a_\alpha < a_\beta</math> if and only if <math>\alpha<\beta</math> (in the usual well-order of the ordinals) is a well-order of <math>A</math> as desired, of order type <math>\sup\{\alpha \mid a_\alpha\text{ is defined}\}+1</math>.</blockquote>

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

An essential point of this proof is that it involves only a single arbitrary choice, that of <math>R</math>; applying the well-ordering theorem to each member <math>S</math> of <math>E</math> separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each <math>S</math> a well-ordering would require just as many choices as simply choosing an element from each <math>S</math>. Particularly, if <math>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==
<references/>

==External links==
* [[Mizar system]] proof: http://mizar.org/version/current/html/wellord2.html

[[Category:Axiom of choice]]
[[Category:Theorems in the foundations of mathematics]]
[[Category:Axioms of set theory]]