nLab
well-order

Contents

Idea

A well-order on a set S is a relation that allows one to interpret S as an ordinal number α and as the relation < on the ordinal numbers less than α. In particular, one can do induction on S over (although the more general well-founded relations also allow this).

The well-ordering theorem states precisely that every set may be equipped with a well-order. This theorem follows from the axiom of choice, and is equivalent to it in the presence of excluded middle.

Definition

A binary relation on a set S is a well-order if it is a well-founded linear order. Equivalently, a well-order is a transitive, extensional, well-founded relation. A set equipped with a well-order is called a well-ordered set, or (following ‘poset’) a woset. Actually, the term ‘well-ordered’ came first; ‘well-order’ is a back formation, which explains the strange grammar.

Sometimes one wants S to have a total order instead of a linear order (that is, a reflexive rather than an irreflexive one). In classical mathematics, at least, the distinction is a technicality: xy if yx, and xy if y⪯̸x. (In constructive mathematics, is not sufficient to reconstruct , and we really want .)

Using either or , we may equivalently define a well order on S to be a linear or total order such that every inhabited subset has a lowest element. That is, for all US with U there exists UU such that no uU satisfies u U (equivalently, every u satisfies Uu). This is probably the definition most often found in textbooks.

Note that in constructive mathematics, cannot necessarily be reconstructed from (which is not necessarily a total order either), and we really want . Also, not every well-ordered set satisfies the property that every inhabited subset has a least element; if it does we call it classically well-ordered. Any classically well-ordered set is a choice set, and so if any set with at least 2 elements has a classical well-order, excluded middle follows.

Examples

  • Any finite linearly ordered set {x 1<<x n} is well-ordered.

  • The set of natural numbers is well-ordered under the usual order <.

  • More generally, any set of ordinal numbers (or even the proper class of all ordinal numbers) is well-ordered under the usual order <.

  • The cardinal numbers of well-orderable sets are themselves well-ordered. So by the well-ordering theorem, the class of all cardinal numbers is well-ordered.

Interpretation as an ordinal number

Any well-ordered set S defines an ordinal number α and an order isomorphism r between S and the set of ordinal numbers less than α; as such, S may be identified (up to isomorphism of wosets) with the von Neumann ordinal α. The idea is that the minimal element of S itself (if any) is mapped to the ordinal number 0, the minimal element of S{} (if any) is mapped to 1, and so on; after which the next element of S (if any) is mapped to ω, and so on; and so on.

This may be defined immediately (and constructively) as a recursively defined function from S to the class of all ordinal numbers:

r(x)=sup txr(t) +;r(x) = \sup_{t \prec x} r(t)^+ ;

the validity of this sort of recursive definition is precisely what the well-foundedness of allows. Here, β + is the successor of the ordinal number β, and sup is the supremum operation on ordinal numbers (which is the union of von Neumann ordinals).

Since S is a set, the image of r in the class of all ordinals is also a set, and one can now prove that r is an order isomorphism between S and the set of ordinals less than the next ordinal, α.

Simulations

Given two well-ordered sets S and T, a function f:ST is a simulation of S in T if

  • f(x)f(y) whenever xy and
  • given tf(x), there exists yx with t=f(y).

Note that any simulation of S in T must be unique. Thus, well-ordered sets and simulations form a category that is in fact a (large) poset.

Successor

A well-ordered set S comes equipped with a successor map succ:SS. this sends aS to the lowest element of the subset S a:={sS,as}.

This need not exist; in particular, S a may be empty. What do we really want to say here? (We could talk about the successor of a well-ordered set.) —Toby

Mike: Yeah, or we could say that successor is a partial function. One definition of a limit ordinal is one on which successor is totally defined.