Template:Short description Template:Redirect Template:Distinguish
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 Template:Section link).<ref>Template:Cite book</ref><ref>Template:Cite book</ref> Ernst Zermelo introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem.<ref name = "zer">Template:Cite book</ref> 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.<ref name = "zer"/> One famous consequence of the theorem is the Banach–Tarski paradox.
HistoryEdit
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>, the set of all real numbers; such a visualization would have to incorporate the axiom of choice.<ref>Template:Cite book</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>Template:Citation</ref> 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.<ref>Template:Cite book</ref>
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?<ref>Template:Citation</ref>
Proof from axiom of choiceEdit
The well-ordering theorem follows from the axiom of choice as follows.<ref>Template:Cite book</ref>
Let the set we are trying to well-order be <math>A</math>, and let <math>f</math> be a choice function for the family of non-empty subsets of <math>A</math>. For every ordinal <math>\alpha</math>, define an element <math>a_\alpha</math> that is in <math>A</math> by setting <math>a_\alpha\ =\ f(A\smallsetminus\{a_\xi\mid\xi<\alpha\})</math> if this complement <math>A\smallsetminus\{a_\xi\mid\xi<\alpha\}</math> is nonempty, or leaves <math>a_\alpha</math> undefined if it is. That is, <math>a_\alpha</math> is chosen from the set of elements of <math>A</math> that have not yet been assigned a place in the ordering (or undefined if the entirety of <math>A</math> has been successfully enumerated). Then the order <math><</math> on <math>A</math> defined by <math>a_\alpha < a_\beta</math> if and only if <math>\alpha<\beta</math> (in the usual well-order of the ordinals) is a well-order of <math>A</math> as desired, of order type <math>\sup\{\alpha \mid a_\alpha\text{ is defined}\}+1</math>.
Proof of axiom of choiceEdit
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, <math>E</math>, take the union of the sets in <math>E</math> and call it <math>X</math>. There exists a well-ordering of <math>X</math>; let <math>R</math> be such an ordering. The function that to each set <math>S</math> of <math>E</math> associates the smallest element of <math>S</math>, as ordered by (the restriction to <math>S</math> of) <math>R</math>, is a choice function for the collection <math>E</math>.
An essential point of this proof is that it involves only a single arbitrary choice, that of <math>R</math>; applying the well-ordering theorem to each member <math>S</math> of <math>E</math> separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each <math>S</math> a well-ordering would require just as many choices as simply choosing an element from each <math>S</math>. Particularly, if <math>E</math> 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.
NotesEdit
<references/>