Well-ordering theorem

Last updated

In mathematics, the well-ordering theorem, also known as Zermelo's theorem or well-ordering principle, 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.



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

See also


  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. 1 2 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, 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

Related Research Articles

Axiom of choice Axiom of set theory

In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets there exists an indexed family of elements such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.

In mathematics, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,

In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914. It states that in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset.

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.

Zorns lemma mathematical proposition equivalent to the axiom of choice

Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max Zorn and Kazimierz Kuratowski, is a proposition of set theory that states that a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element.

In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov, who proved it first in 1930 for powers of the closed unit interval and in 1935 stated the full theorem along with the remark that its proof was the same as for the special case. The earliest known published proof is contained in a 1937 paper of Eduard Čech.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

KÅ‘nigs lemma lemma

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contains an axiomatic system and all its derived theorems. An axiomatic system that is completely described is a special kind of formal system. A formal theory is an axiomatic system that describes a set of sentences that is closed under logical implication. A formal proof is a complete rendition of a mathematical proof within a formal system.

In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings and prime ideals, or distributive lattices and maximal ideals. This article focuses on prime ideal theorems from order theory.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if X is a non-empty chain complete poset, and

In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has become a thoroughly standard fixture of classical set theory, it has been criticized in several areas by mathematicians and philosophers.

Jerry L. Bona American mathematician

Jerry Lloyd Bona is an American mathematician, known for his work in fluid mechanics, partial differential equations, and computational mathematics, and active in some other branches of pure and applied mathematics.

In mathematics, the Teichmüller–Tukey lemma, named after John Tukey and Oswald Teichmüller, is a lemma that states that every nonempty collection of finite character has a maximal element with respect to inclusion. Over Zermelo–Fraenkel set theory, the Teichmüller–Tukey lemma is equivalent to the axiom of choice, and therefore to the well-ordering theorem, Zorn's lemma, and the Hausdorff maximal principle.

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions f : AB and g : BA between the sets A and B, then there exists a bijective function h : AB.

Equivalents of the Axiom of Choice is a book in mathematics, collecting statements in mathematics that are true if and only if the axiom of choice holds. It was written by Herman Rubin and Jean E. Rubin, and published in 1963 by North-Holland as volume 34 of their Studies in Logic and the Foundations of Mathematics series. An updated edition, Equivalents of the Axiom of Choice, II, was published as volume 116 of the same series in 1985.