Well-ordering theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 02:12, 26 August 2022

Proof of equivalence to axiom of choice

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

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 α, define a set $a_{\alpha }$ that's in A by setting $a_{\alpha }\ =\ f(A\setminus \{a_{\xi }\mid \xi <\alpha \})$ if this complement $A\setminus \{a_{\xi }\mid \xi <\alpha \}$ is nonempty, or leave $a_{\alpha }$ undefined if it is. That is, $a_{\alpha }$ is some set chosen from A that has not yet been assigned a place in the ordering, or undefined if the entirety of A has been successfully enumerated. Then $\langle a_{\alpha }\mid a_{\alpha }{\text{ is defined}}\rangle$ is a well-order of A as desired.

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).^[2]^[3] Ernst Zermelo introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem.^[4] 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.^[4] 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".^[5] However, it is considered difficult or even impossible to visualize a well-ordering of $\mathbb {R}$ ; such a visualization would have to incorporate the axiom of choice.^[6] 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.^[7] 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.^[8]

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?^[9]

Proof of equivalence to axiom of choice

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

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 α, define a set $a_{\alpha }$ that's in A by setting $a_{\alpha }\ =\ f(A\setminus \{a_{\xi }\mid \xi <\alpha \})$ if this complement $A\setminus \{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 $\langle a_{\alpha }\mid a_{\alpha }{\text{ is defined}}\rangle$ is a well-order of A as desired.

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

^ Jech, Thomas (2002). Set Theory (Third Millennium Edition). Springer. p. 48. ISBN 978-3-540-44085-7.
^ Kuczma, Marek (2009). An introduction to the theory of functional equations and inequalities. Berlin: Springer. p. 14. ISBN 978-3-7643-8748-8.
^ Hazewinkel, Michiel (2001). Encyclopaedia of Mathematics: Supplement. Berlin: Springer. p. 458. ISBN 1-4020-0198-3.
^ ^a ^b Thierry, Vialar (1945). Handbook of Mathematics. Norderstedt: Springer. p. 23. ISBN 978-2-95-519901-5.
^ Georg Cantor (1883), “Ueber unendliche, lineare Punktmannichfaltigkeiten”, Mathematische Annalen 21, pp. 545–591.
^ Sheppard, Barnaby (2014). The Logic of Infinity. Cambridge University Press. p. 174. ISBN 978-1-1070-5831-6.
^ Plotkin, J. M. (2005), "Introduction to "The Concept of Power in Set Theory"", Hausdorff on Ordered Sets, History of Mathematics, vol. 25, American Mathematical Society, pp. 23–30, ISBN 9780821890516
^ Shapiro, Stewart (1991). Foundations Without Foundationalism: A Case for Second-Order Logic. New York: Oxford University Press. ISBN 0-19-853391-8.
^ Krantz, Steven G. (2002), "The Axiom of Choice", in Krantz, Steven G. (ed.), 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
^ Jech, Thomas (2002). Set Theory (Third Millennium Edition). Springer. p. 48. ISBN 978-3-540-44085-7.

External links

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

[1] Jech, Thomas (2002). Set Theory (Third Millennium Edition). Springer. p. 48. ISBN 978-3-540-44085-7.

[2] Kuczma, Marek (2009). An introduction to the theory of functional equations and inequalities. Berlin: Springer. p. 14. ISBN 978-3-7643-8748-8.

[3] Hazewinkel, Michiel (2001). Encyclopaedia of Mathematics: Supplement. Berlin: Springer. p. 458. ISBN 1-4020-0198-3.

[zer-4] Thierry, Vialar (1945). Handbook of Mathematics. Norderstedt: Springer. p. 23. ISBN 978-2-95-519901-5.

[5] Georg Cantor (1883), “Ueber unendliche, lineare Punktmannichfaltigkeiten”, Mathematische Annalen 21, pp. 545–591.

[6] Sheppard, Barnaby (2014). The Logic of Infinity. Cambridge University Press. p. 174. ISBN 978-1-1070-5831-6.

[7] Plotkin, J. M. (2005), "Introduction to "The Concept of Power in Set Theory"", Hausdorff on Ordered Sets, History of Mathematics, vol. 25, American Mathematical Society, pp. 23–30, ISBN 9780821890516

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

[9] Krantz, Steven G. (2002), "The Axiom of Choice", in Krantz, Steven G. (ed.), 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

[10] Jech, Thomas (2002). Set Theory (Third Millennium Edition). Springer. p. 48. ISBN 978-3-540-44085-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 2: / Line 2: @@
 {{redirect|Zermelo's theorem|Zermelo's theorem in game theory|Zermelo's theorem (game theory)}}
 {{distinguish|Well-ordering principle}}
+==Proof of equivalence to 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 (Third Millennium Edition) |publisher=[[Springer Publishing|Springer]] |year=2002 |isbn=978-3-540-44085-7 |pages=48}}</ref><blockquote>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 α, define a set <math>a_\alpha</math> that's in ''A'' by setting <math>a_\alpha\ =\ f(A\setminus\{a_\xi\mid\xi<\alpha\})</math> if this complement <math>A\setminus\{a_\xi\mid\xi<\alpha\}</math> is nonempty, or leave <math>a_\alpha</math> undefined if it is. That is, <math>a_\alpha</math> is some set chosen from A that has not yet been assigned a place in the ordering, or undefined if the entirety of ''A'' has been successfully enumerated. Then <math>\langle a_\alpha\mid a_\alpha\text{ is defined}\rangle</math> is a well-order of ''A'' as desired.</blockquote>
 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]].