A well-order is a total order on a set such that every nonempty subset has a least element. A set equipped with such an order is called a well-ordered set. The usual order on the natural numbers is the basic example: every nonempty collection of natural numbers has a smallest member. Well-orders are fundamental in set theory, where they underlie ordinal numbers, transfinite induction, and recursive constructions extending beyond finite stages.
Definition
Let be a set and a total order on . Thus is reflexive, antisymmetric, and transitive, and any two elements of are comparable. The order is a well-order if
The element is the least element of . It is unique by antisymmetry.
Equivalently, a well-order can be described using its strict relation , defined by when and . The notation or specifies both the underlying set and its order.
The empty set is well-ordered: it has no nonempty subsets for which the condition could fail. Every finite totally ordered set is also well-ordered.
The least-element requirement concerns every nonempty subset, not merely itself. Having a first element is therefore necessary for a nonempty well-order, but not sufficient.
Examples and nonexamples
Natural numbers and integers
The natural numbers
form a well-ordered set. Its order type is denoted by .
The integers with their usual order are not well-ordered: the set of all integers has no least element. Nevertheless, the same underlying set can be well-ordered by listing its elements as
Every nonempty subset has an element occurring earliest in this list. Thus well-ordering is a property of a set with a specified order, rather than a property of its elements alone.
Rational and real numbers
The rational numbers and real numbers are not well-ordered by their usual orders. For example, the positive rational numbers have no least member, since is smaller than any positive rational number .
Even the interval , which has a least element, is not well-ordered: its subset has no least element. This also illustrates that having an infimum is not the same as having a least element. The infimum of is , but does not belong to that subset.
Infinite orders with different arrangements
A well-order need not resemble an ordinary sequence indexed by natural numbers. Let
with every natural number preceding . Then
is a well-order of type . The final element has infinitely many predecessors and no immediate predecessor.
Another well-order places every even natural number before every odd natural number, retaining the usual order within each group:
Its order type is , also written . It is not order-isomorphic to the usual ordering of , despite having the same underlying set.
Structural properties
Restrictions and initial segments
Restricting a well-order to any subset produces another well-order.
For , the set
is the initial segment determined by . More generally, an initial segment is a downward-closed subset: whenever it contains , it contains every .
Every proper initial segment of a well-ordered set has the form for a unique . Indeed, is the least element outside that initial segment.
Successors and limit positions
If an element is not greatest, the nonempty set of elements greater than has a least element. This is the immediate successor of .
The corresponding claim for predecessors is false. In the order of type , the final element has no immediate predecessor. Such positions motivate the distinction between successor and limit ordinals.
Thus a well-order may have a greatest element, but need not; and an element may have predecessors without having a greatest predecessor.
Comparison and rigidity
An order isomorphism is a bijection that preserves and reflects the order. Any two well-ordered sets are comparable: either they are order-isomorphic, or one is order-isomorphic to a proper initial segment of the other.
Well-orders are also rigid. The only order isomorphism from a well-ordered set to itself is the identity. More generally, if two well-orders are order-isomorphic, their order isomorphism is unique. This follows because the least elements must correspond, then the least remaining elements must correspond, and so on through the entire order.
Ordinals and order types
An ordinal number represents the order type of a well-ordered set. In the standard von Neumann construction, an ordinal is a transitive set well-ordered by membership. Every well-ordered set is order-isomorphic to exactly one ordinal.
The finite ordinals describe finite well-orders, while
describe distinct infinite well-orders.
Order type contains more information than cardinality. The three orders above all have countably infinite underlying sets, but differ in their arrangement. For instance, has a greatest element, whereas and do not.
Ordinal arithmetic describes operations on well-orders:
- Ordinal addition places one well-order after another.
- Ordinal multiplication arranges ordered copies of one well-order in a sequence indexed by another.
These operations are generally not commutative. For example,
Putting one element before an infinite sequence does not change its order type; putting one after the entire sequence does.
Induction and recursion
Transfinite induction
Well-orders support transfinite induction, which generalizes ordinary mathematical induction. To prove a property for every , it suffices to show that
for every .
If any counterexamples existed, they would have a least member. All earlier elements would satisfy , so the induction hypothesis would force this least counterexample to satisfy as well—a contradiction.
For ordinals, proofs are often organized into a first stage, successor stages, and limit stages. These are convenient cases of the same least-counterexample principle.
Transfinite recursion
Transfinite recursion defines an object at each position using the objects already defined at earlier positions. Schematically,
where is the restriction of to positions preceding .
Under the usual set-theoretic hypotheses, a rule assigning a unique value to each possible earlier history determines a unique function along the well-order. This supports definitions of ordinal arithmetic and constructions carried out through arbitrarily long well-ordered sequences of stages.
Relation to well-founded orders
A well-founded relation is a relation for which every nonempty subset of its domain has a minimal element. A well-order is precisely a well-founded strict total order.
The distinction between least and minimal matters for a partial order. A least element lies below every element of the subset. A minimal element merely has no strictly smaller element in that subset; it may be incomparable with other elements. In a total order, these notions coincide.
Every well-order has no infinite strictly descending sequence
In standard set theory with the axiom of choice, the converse holds for total orders. Without suitable choice principles, the absence of such sequences is not generally interchangeable with the least-element definition. The definition using nonempty subsets avoids this foundational qualification.
The well-ordering theorem and choice
The well-ordering theorem states that every set admits some well-order. Over Zermelo–Fraenkel set theory, it is equivalent to the axiom of choice.
One direction is immediate: if every set can be well-ordered, then the union of any set-sized family of nonempty sets can be well-ordered, and a choice function selects the least member of each set in the family.
The reverse direction uses choice to establish that every set can be well-ordered. This is an existence theorem: it does not generally provide an explicit description of the resulting order.
In particular, the real numbers can be well-ordered assuming choice, even though their familiar numerical order is not a well-order. The theorem asserts the existence of a different relation, not a new property of the usual relation .
The theorem concerns each set individually. It does not, by itself, assert a single well-ordering of the entire universe of sets.
Historical development and uses
Georg Cantor developed well-ordered sets and transfinite ordinal numbers in the late nineteenth century. Ernst Zermelo proved the well-ordering theorem in 1904 using a choice principle, helping establish the axiom of choice as a central topic in the foundations of mathematics.
Well-orders provide a general framework for selecting least counterexamples, organizing transfinite constructions, and comparing ordinal positions. They also appear in termination arguments in computer science: if each step of a computation strictly decreases a value in a well-ordered set, an infinite sequence of steps is impossible. More general well-founded relations serve the same purpose when total comparability is unnecessary.