Inmathematics, thewell-ordering theorem, also known asZermelo's theorem, states that everyset can bewell-ordered. A setX iswell-ordered by astrict total order if every non-empty subset ofX has aleast element under the ordering. The well-ordering theorem together withZorn's lemma are the most important mathematical statements that are equivalent to theaxiom of choice (often called AC, see alsoAxiom 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 totransfinite induction, which is considered by mathematicians to be a powerful technique.^[3] One famous consequence of the theorem is theBanach–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${\displaystyle \mathbb{R}}$, the set of allreal numbers; 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 infirst-order logic the well-ordering theorem is equivalent to the axiom of choice, in the sense that theZermelo–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 toZorn's lemma.) Insecond-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 aboutZorn's lemma?^[8]

The well-ordering theorem follows from the axiom of choice as follows.^[9]

Let the set we are trying to well-order be${\displaystyle A}$, and let${\displaystyle f}$ be a choice function for the family of non-empty subsets of${\displaystyle A}$. For everyordinal${\displaystyle \alpha }$, define an element${\displaystyle a_{\alpha }}$ that is in${\displaystyle A}$ by setting if this complement is nonempty, or leaves${\displaystyle a_{\alpha }}$ undefined if it is. That is,${\displaystyle a_{\alpha }}$ is chosen from the set of elements of${\displaystyle A}$ that have not yet been assigned a place in the ordering (or undefined if the entirety of${\displaystyle A}$ has been successfully enumerated). Then the order on${\displaystyle A}$ defined by if and only if (in the usual well-order of the ordinals) is a well-order of${\displaystyle A}$ as desired, of order type${\displaystyle \{\alpha \mid a_{\alpha }\text{ is defined}\}}$ (in thevon Neumann representation).

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,${\displaystyle E}$, take the union of the sets in${\displaystyle E}$ and call it${\displaystyle X}$. There exists a well-ordering of${\displaystyle X}$; let${\displaystyle R}$ be such an ordering. The function that to each set${\displaystyle S}$ of${\displaystyle E}$ associates the smallest element of${\displaystyle S}$, as ordered by (the restriction to${\displaystyle S}$ of)${\displaystyle R}$, is a choice function for the collection${\displaystyle E}$.

An essential point of this proof is that it involves only a single arbitrary choice, that of${\displaystyle R}$; applying the well-ordering theorem to each member${\displaystyle S}$ of${\displaystyle E}$ separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each${\displaystyle S}$ a well-ordering would require just as many choices as simply choosing an element from each${\displaystyle S}$.

• Mizar system proof:http://mizar.org/version/current/html/wellord2.html

• Axiom of choice
• Theorems in the foundations of mathematics
• Axioms of set theory

• CS1 errors: ISBN date
• Articles with short description
• Short description is different from Wikidata