The well-ordering theorem states that every set can be equipped with an order in which every nonempty subset has a least element. It is a fundamental result of set theory, linking the ordering of arbitrary sets to the theory of ordinal and cardinal numbers. Over Zermelo–Fraenkel set theory without choice, usually abbreviated ZF, it is equivalent to the axiom of choice. The theorem asserts the existence of a suitable order; it does not claim that a set’s familiar order is already a well-order or provide a canonical way to choose one.
Statement and definitions
A well-order on a set is a strict total order such that every nonempty subset has a least element. A strict total order is irreflexive and transitive, and any two distinct elements are comparable. The additional least-element requirement is
The well-ordering theorem can therefore be written as
The order relation is part of what must be supplied. The statement does not require that it agree with any order, algebraic structure, or topology already associated with .
The empty set is well-ordered vacuously. Every finite set can be well-ordered, and its well-orderability is provable in ZF without the axiom of choice. The strength of the theorem lies in its assertion about arbitrary infinite sets.
The name “well-ordering principle” is also sometimes used for the much narrower statement that every nonempty subset of the natural numbers has a least element. That arithmetic principle should be distinguished from the assertion that every set can be well-ordered.
Examples and nonexamples
The usual order on the natural numbers
is a well-order. By contrast, the usual order on the integers is not: the set of all integers has no least element. Nevertheless, the integers can be well-ordered by arranging them as
Every integer has a finite position in this arrangement, so every nonempty subset has an element occurring first.
Likewise, the usual order on the rational numbers is not a well-order, but an enumeration of the rationals gives them one. More generally, any set equipped with an injection into the natural numbers inherits a well-order from that injection. Thus the well-orderability of an individual countable set does not require the full axiom of choice.
The real numbers present a more substantial example. Their usual order is not a well-order: the interval , for instance, has no least element. The theorem asserts that some other order well-orders the reals. Such an order need not have any useful relationship to their usual order or topology.
Well-orderability also does not imply countability. A well-order can have elements that occur after infinitely many predecessors, and its positions need not be indexed by natural numbers.
Equivalence with the axiom of choice
The axiom of choice states that for every indexed family of nonempty sets , there exists a function satisfying
Over ZF, this assertion and the well-ordering theorem imply one another.
From well-ordering to choice
Let be a family of nonempty sets. By the well-ordering theorem, the union
has a well-order . Define
Each is nonempty, so the least element exists and is unique. The resulting function chooses one member of every set in the family.
This implication explains a central use of well-orders: once a set is well-ordered, selecting an element from any of its nonempty subsets becomes unambiguous.
From choice to well-ordering
Assume the axiom of choice and fix a set . There is then a choice function on the collection of all nonempty subsets of , with
The intended construction repeatedly chooses an element not selected earlier. Ordinary recursion through the natural numbers may not exhaust , so the construction uses transfinite recursion, proceeding through ordinal stages.
A rigorous stopping bound comes from Hartogs’s theorem, which is provable in ZF: for every set , there is an ordinal that does not inject into .
At each stage , provided unused elements remain, set
If this process selected a new element at every stage below , then would be an injection from into , contradicting its definition. The process must therefore exhaust at some ordinal stage .
The assignment is then a bijection from onto . Transporting the ordinal order along this bijection gives a well-order of .
The stopping argument is essential: the informal instruction “keep choosing unused elements until none remain” does not by itself justify a transfinite construction or establish that it terminates.
Ordinals and cardinality
Every well-ordered set is order-isomorphic to a unique ordinal number. This fact is provable in ZF and does not require every set to be well-orderable. The well-ordering theorem adds the assertion that every set can be placed within this ordinal framework.
Consequently, every set has the same cardinality as some ordinal. Among the ordinals in bijection with a given well-orderable set, there is a least one, called its initial ordinal. In ZFC—ZF together with the axiom of choice—initial ordinals provide standard representatives for all cardinalities.
The uniqueness here concerns an order type or a least ordinal of a given size, not a unique ordering of the original set. A single infinite set can admit well-orders of different order types. For example, the natural numbers can be ordered with type , their usual order type, or with type , by placing the positive integers first in their usual order and placing last.
The theorem also yields comparability of arbitrary set sizes: for any sets and , either injects into or injects into . After well-ordering both sets, this follows from comparison of their ordinal order types. Over ZF, this general comparability principle is itself equivalent to the axiom of choice.
Uses in mathematical proofs
Well-ordering allows constructions that proceed one element at a time even when no countable enumeration is available.
Transfinite induction and recursion
A well-order supports transfinite induction: to prove a property at every position, it suffices to show that it holds at a position whenever it holds at all earlier positions. This extends the pattern of mathematical induction beyond the natural numbers.
Transfinite recursion similarly allows an object at each position to be defined using the objects constructed earlier. The recursion theorem itself is available in ZF; the well-ordering theorem makes it possible to apply that method along an arbitrary set after choosing a well-order.
Algebraic existence arguments
For a vector space, one can well-order its vectors and process them in that order. A vector is retained precisely when it is not in the linear span of those already retained. At limit stages, all previously retained vectors are collected.
The resulting family is linearly independent and spans the space, so it is a basis. The construction may establish existence without producing a computationally usable description of that basis.
Many arguments of this kind are instead presented using Zorn’s lemma, which is also equivalent to the axiom of choice over ZF. Well-ordering organizes a construction into successive stages; Zorn’s lemma establishes the existence of a maximal object in a suitable partially ordered set.
History and foundational status
Georg Cantor treated the well-orderability of arbitrary sets as a fundamental principle in developing transfinite set theory. Ernst Zermelo published a proof in 1904 that explicitly used a choice principle, and in 1908 published another proof. Discussion of these arguments helped bring the axiom of choice and the axiomatic foundations of set theory into focus.
The theorem’s status depends on the background axioms:
- In ZFC, it is a theorem, because the axiom of choice is included.
- In ZF alone, it is equivalent to adding the axiom of choice.
- Assuming ZF is consistent, neither the theorem nor its negation is provable in ZF.
The independence results for choice were established through work by Kurt Gödel and Paul Cohen. They concern formal provability relative to a specified axiom system, rather than an ambiguity in the definition of a well-order.
Limits and common misconceptions
Existence is not a canonical specification. The theorem does not identify a preferred well-order for a given set. A particular model of set theory may have a definable well-order of the reals, but ZFC does not guarantee a parameter-free definable well-order of the reals in every model.
Well-ordering is not a countable listing. An uncountable set can be indexed by an ordinal without being enumerable by the natural numbers.
Least does not mean merely minimal. A least element is below every other element. A minimal element in a partial order merely has no strictly smaller element. Well-ordering requires a total order and a least element in every nonempty subset.
The theorem applies to sets, not automatically to the entire universe at once. It states that each set has some well-order. In class theories, a single class relation well-ordering the universe is a global-choice assertion; it should not be identified with the ordinary set-level theorem.
Well-ordering the reals does not establish the continuum hypothesis. The continuum hypothesis specifies the cardinality of the reals among the infinite cardinals. Well-orderability places their cardinality within the ordinal framework but does not determine which uncountable cardinal it is.