In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the well-ordering theorem, also known as Zermelo's theorem, states that every
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
can be
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...
ed. A set ''X'' is ''well-ordered'' by a
strict total order if every non-empty subset of ''X'' has a
least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
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
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 collectio ...
(often called AC, see also ).
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem.
One can conclude from the well-ordering theorem that every set is susceptible to
transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Induction by cases
Let P(\alpha) be a property defined for a ...
, which is considered by mathematicians to be a powerful technique.
One famous consequence of the theorem is the
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be p ...
.
History
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
considered the well-ordering theorem to be a "fundamental principle of thought". 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. In 1904,
Gyula Kőnig claimed to have proven that such a well-ordering cannot exist. A few weeks later,
Felix Hausdorff
Felix Hausdorff ( , ; November 8, 1868 – January 26, 1942) was a 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, an ...
found a mistake in the proof. It turned out, though, that in
first order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
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
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of Propositional calculus, propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-ord ...
, 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.
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?
Proof from axiom of choice
The well-ordering theorem follows from the axiom of choice as follows.
Let the set we are trying to well-order be , and let be a choice function for the family of non-empty subsets of . For every ordinal , define a set that is in by setting if this complement is nonempty, or leave undefined if it is. That is, is chosen from the set of elements of that have not yet been assigned a place in the ordering (or undefined if the entirety of has been successfully enumerated). Then is a well-order of 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,
, take the union of the sets in
and call it
. There exists a well-ordering of
; let
be such an ordering. The function that to each set
of
associates the smallest element of
, as ordered by (the restriction to
of)
, is a choice function for the collection
.
An essential point of this proof is that it involves only a single arbitrary choice, that of
; applying the well-ordering theorem to each member
of
separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each
a well-ordering would require just as many choices as simply choosing an element from each
. Particularly, if
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
External links
*
Mizar system
The Mizar system consists of a formal language for writing mathematical definitions and proofs, a proof assistant, which is able to mechanically check proofs written in this language, and a library of formalized mathematics, which can be used in ...
proof: http://mizar.org/version/current/html/wellord2.html
Axiom of choice
Theorems in the foundations of mathematics
Axioms of set theory