Well-Ordering

Definition

A well-ordering on a set $A$ is a total order $\le :A\to A\to \mathrm{Prop}$ such that every non-empty subset of $A$ has a least element: $\forall S\subseteq A.S\ne \varnothing \to \exists m\in S.\forall x\in S.m\le x.$

A set equipped with a well-ordering is called a well-ordered set. The least element of a non-empty subset $S$ is unique, by anti-symmetry.

Relationship to Well-Founded Relations

A total order is a well-ordering iff its strict part $<$ (defined by $x<y⟺x\le y\wedge x\ne y$) is a well-founded relation. That is, there is no infinite strictly descending sequence $\cdots <x_2<x_1<x_0.$

The well-foundedness formulation is often more convenient in type theory, where it is expressed via the accessibility predicate rather than by quantifying over subsets.

Transfinite Induction

Every well-ordering supports transfinite induction: to prove a property $P$ holds for all $x\in A$, it suffices to show that for every $x\in A$, if $P(y)$ holds for all $y<x$, then $P(x)$ holds: $\left(\forall x\in A.(\forall y<x.P(y))\to P(x)\right)\to \forall x\in A.P(x).$

For finite ordinals this recovers ordinary mathematical induction; for $\omega +\omega$ and beyond it requires reasoning about limit stages as well as successor stages.

Transfinite Recursion

Dually, well-orderings support transfinite recursion: a function $f:A\to B$ can be defined by specifying $f(x)$ in terms of $f(y)$ for all $y<x$. This is the well-ordered analogue of well-founded recursion.

Examples

• $(\mathbb{N},\le )$ with the standard ordering is the smallest infinite well-ordering.
• Any finite totally ordered set is well-ordered.
• The ordinals under $\le$ form a well-ordering (in fact they are the canonical well-ordered sets).
• $(\mathbb{Z},\le )$ is not well-ordered: the subset $\mathbb{Z}$ itself has no least element.
• $(\mathbb{Q}\cap [0,1],\le )$ is not well-ordered: the open interval $(0,1)\cap \mathbb{Q}$ has no least element.

Relationship to Ordinals

Every well-ordered set is order-isomorphic to a unique ordinal. This is the order type of the well-ordered set. Consequently, the theory of well-orderings is equivalent to the theory of ordinals.

Given two well-ordered sets, exactly one of the following holds (trichotomy for ordinals):

• they are isomorphic,
• one is isomorphic to an initial segment of the other.

An initial segment of $(A,\le )$ determined by $a\in A$ is the set $\{x\in A\mid x<a\}$.

Well-Ordering Theorem

The well-ordering theorem states that every set can be well-ordered. This is equivalent to the Axiom of Choice over ZF. Other equivalents include Zorn’s lemma and the Hausdorff maximal principle.

Related Concepts

• Total Ordering
• Partial Order
• Well-founded Relation
• Ordinal
• Axiom of Choice
• Transitive Relation
• Reflexive Relation
• Set Theory
• Hausdorff Maximal Principle

References

• munkres2000-topology