Well-ordering theorem

From Wikipedia, the free encyclopedia
"Zermelo's theorem" redirects here. For Zermelo's theorem in game theory, see Zermelo's theorem (game theory).
Not to 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 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 ; 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 of equivalence to axiom of choice[]

The well-ordering theorem follows from Zorn's lemma. Take the set of all well-orderings of subsets of X: an element of is an ordered pair (a,b) where a is a subset of X and b is a well-ordering of 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 is a chain in , then the union of the sets in can be ordered in a way that makes it a continuation of any set in ; this ordering is a well-ordering, and therefore, an upper bound of in . We may therefore apply Zorn's lemma to conclude that 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 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. ^ 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.
  3. ^ a b 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.

External links[]

Retrieved from ""