Well-ordering theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 23:00, 8 January 2022

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 $\mathbb {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.^[6] It turned out, though, that the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with the Zermelo–Fraenkel axioms is sufficient to prove the other, in first order logic (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 of equivalence to AC

The well-ordering theorem follows from Zorn's lemma. Take the set $\mathbf {A}$ of all well-orderings of subsets of X: an element of $\mathbf {A}$ is an ordered pair (a,b) where a is a subset of X and b is a well-ordering of a. $\mathbf {A}$ can be partially ordered by continuation. That means, define E ≤ F if E is an initial segment of F and the ordering of the members of E is the same as their ordering in F. If ${\mathcal {E}}$ is a chain in $\mathbf {A}$ , then the union of the sets in ${\mathcal {E}}$ can be ordered in a way that makes it a continuation of any set in ${\mathcal {E}}$ ; this ordering is a well-ordering, and therefore, an upper bound of ${\mathcal {E}}$ in $\mathbf {A}$ . We may therefore apply Zorn's Lemma to conclude that $\mathbf {A}$ has a maximal element, say (M,R). The set M must be equal to X, for if X has an element x not in M, then the set M∪{x} has a well-ordering that restricts to R on M, and for which x is larger than all elements of M. This well ordered set is a continuation of (M,R), contradicting its maximality, therefore M = X. Now R is a well-ordering of X.^[9]

Proof of AC

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 not be easier than choosing an element.^{[clarification needed]}

Notes

^ 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
^ Halmos, Paul (1960). Naive Set Theory. Litton Educational.

External links

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

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

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

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

[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.

[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

[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. (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

[9] Halmos, Paul (1960). Naive Set Theory. Litton Educational.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 8: / Line 8: @@
 [[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>; 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 the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with the [[Zermelo–Fraenkel axioms]] is sufficient to prove the other, in [[first order logic]] (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 of equivalence to AC==
+The well-ordering theorem follows from [[Zorn's lemma]]. Take the set <math>\mathbf{A}</math> of all well-orderings of subsets of ''X'': an element of <math>\mathbf{A}</math> is an ordered pair (''a'',''b'') where ''a'' is a subset of ''X'' and ''b'' is a well-ordering of ''a''. <math>\mathbf{A}</math> can be [[partially ordered]] by continuation. That means, define ''E'' ≤ ''F'' if ''E'' is an [[initial segment]] of ''F'' and the ordering of the members of ''E'' is the same as their ordering in ''F''. If <math>\mathcal{E}</math> is a [[total order|chain]] in <math>\mathbf{A}</math>, then the union of the sets in <math>\mathcal{E}</math> can be ordered in a way that makes it a continuation of any set in <math>\mathcal{E}</math>; this ordering is a well-ordering, and therefore, an upper bound of <math>\mathcal{E}</math> in <math>\mathbf{A}</math> . We may therefore apply Zorn's Lemma to conclude that <math>\mathbf{A}</math> has a maximal element, say (''M'',''R''). The set ''M'' must be equal to ''X'', for if ''X'' has an element ''x'' not in ''M'', then the set ''M''∪{''x''} has a well-ordering that restricts to ''R'' on ''M'', and for which ''x'' is larger than all elements of ''M''. This well ordered set is a continuation of (''M'',''R''), contradicting its maximality, therefore ''M''&nbsp;=&nbsp;''X''. Now ''R'' is a well-ordering of ''X''.<ref>{{cite book |authorlink=Paul Halmos |first=Paul |last=Halmos |year=1960 |title=Naive Set Theory |publisher=Litton Educational |location= |isbn= }}</ref>
 ==Proof of AC==