Well-ordered set

A well-ordered set is a set \(X\) endowed with a relation \(\leq\) on \(X^2\), called a well-order, so that \(\leq\) has the following properties

• Transitivity: If \(a \leq b\) and \(b \leq c\) then \(a \leq c\).
• Antisymmetry: If \(a \leq b\) and \(b \leq a\), then \(a = b\).
• Totality: For all \(a, b\), either \(a \leq b\) or \(b \leq a\).
• Well-foundedness: For any \(S \subseteq X\), there is \(s \in S\) so that, for all \(t \in S\), \(s \leq t\).
• Reflexivity: For all \(a\), \(a \leq a\).

These properties were intended to idealize and generalize the properties of the ordering on the natural numbers. Note that, under their usual ordering, the natural numbers are well-ordered, but the integers, nonnegative rationals, and any real number interval are not. The axiom of choice implies, however, that any set can be well-ordered, just the prior examples aren't well-ordered with respect to their natural ordering. As mentioned just now, the axiom of choice implies there is a well-order of the reals, but it is not definable, while the axiom of determinacy implies that there is no well-order on the reals whatsoever.

Well-ordered sets are part of the motivation of ordinals, and are used to define their equivalence class definition. In particular, for any well-ordered set \(X\), there is an ordinal \(\alpha\) and a map \(\pi: X \to \alpha\) so that \(x \leq y\) implies \(\pi(x) \leq \pi(y)\): the unique such ordinal is called its order-type. The order-type of the natural numbers is \(\omega\), where the map \(\pi\) is just the identity function, and any ordinal is its own order-type. Also, any countable set has a countable order-type, and any finite set has a finite order-type (which is necessarily equal to its cardinality, unlike the case with infinite sets).