Well-ordering theorem
Encyclopedia
In mathematics, the well-ordering theorem states that every 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. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice. Ernst Zermelo
introduced the Axiom of Choice as an "unobjectionable logical principle" to prove the well-ordering theorem. This is important because it makes every set susceptible to the powerful technique of transfinite induction
. The well-ordering theorem has consequences that may seem paradoxical, such as the Banach–Tarski paradox
.
considered the well-ordering theorem to be a "fundamental principle of thought." Most mathematicians however find it difficult to visualize a well-ordering of, for example, the set R of real number
s. In 1904, Gyula Kőnig claimed to have proven that such a well-ordering cannot exist. A few weeks later, though, Felix Hausdorff
found a mistake in the proof. 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.
The well ordering theorem follows easily from Zorn's Lemma. Take the set A of all well orderings of subsets of X: an element of A is an ordered pair (a,b) where a is a subset of X and b is a well ordering of a. 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 in E is the same as their ordering in F. If E is a chain
in A, then the union of the sets in E can be ordered in a way that makes it a continuation of any set in E; this ordering is a well ordering, and therefore, an upper bound of E in A. We may therefore apply Zorn's Lemma to conclude that 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.
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.
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total 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. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice. Ernst Zermelo
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...
introduced the Axiom of Choice as an "unobjectionable logical principle" to prove the well-ordering theorem. This is important because it makes every set susceptible to the powerful technique of transfinite induction
Transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
. The well-ordering theorem has consequences that may seem paradoxical, such as the Banach–Tarski paradox
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theoretic geometry which states the following: Given a solid ball in 3-dimensional space, there exists a decomposition of the ball into a finite number of non-overlapping pieces , which can then be put back together in a different way to yield two...
.
History
Georg CantorGeorg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
considered the well-ordering theorem to be a "fundamental principle of thought." Most mathematicians however find it difficult to visualize a well-ordering of, for example, the set R of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. In 1904, Gyula Kőnig claimed to have proven that such a well-ordering cannot exist. A few weeks later, though, Felix Hausdorff
Felix Hausdorff
Felix Hausdorff was a Jewish German mathematician who is considered to be one of the founders of modern topology and who contributed significantly to set theory, descriptive set theory, measure theory, function theory, and functional analysis.-Life:Hausdorff studied at the University of Leipzig,...
found a mistake in the proof. 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
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...
.) 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.
Statement and sketch of proof
For every set X, there exists a well ordering with domain X.The well ordering theorem follows easily from Zorn's Lemma. Take the set A of all well orderings of subsets of X: an element of A is an ordered pair (a,b) where a is a subset of X and b is a well ordering of a. 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 in E is the same as their ordering in F. If E is a chain
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
in A, then the union of the sets in E can be ordered in a way that makes it a continuation of any set in E; this ordering is a well ordering, and therefore, an upper bound of E in A. We may therefore apply Zorn's Lemma to conclude that 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.
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.