wellorders

A well-order is a special kind of total order on a set in which every nonempty subset has a least element. Formally, a well-order on a set S is a relation ≤ that is a total order and satisfies: for every nonempty A ⊆ S, there exists an m ∈ A such that m ≤ a for all a ∈ A. This property is often referred to as well-foundedness.

Well-orders have the feature that there is no infinite descending sequence, and, conversely, any total order with this latter condition is a well-order. Finite total orders are always well-ordered, and the usual order on the natural numbers is the canonical example of a well-order. The concept extends to ordinals, where each ordinal is well-ordered by the membership relation, and more generally every well-ordered set is order-isomorphic to a unique ordinal.

Key consequences include the notion of order type: the order type of a well-ordered set is a transfinite ordinal, and two well-ordered sets are order-isomorphic if and only if they have the same order type. This leads to transfinite induction and transfinite recursion, methods that generalize mathematical induction to well-ordered domains.

Important theorems connect well-orders to the axiom of choice. The well-ordering theorem states that every set can be well-ordered, and it is equivalent to the axiom of choice. In practice, the theorem underpins many constructions in set theory and foundational mathematics.

Not all linear orders are well-orders; for example, the integers with their usual order are not well-ordered because subsets like the negative integers do not have a least element.