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 nonempty \(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, and such a function \(\pi\) is called an order-isomorphism. 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).

You can see that, assuming the axiom of choice, the well-foundedness criterion is equivalent to there not being an infinite descending chain. Assume \(S \subseteq X\), and there is no infinite descending chain. Assume towards contradiction that \(S\) has no minimal element. Use AC to define a choice function \(f\) for \(\{X: X \subseteq S\}\). Let \(s_0 = f(S) \in S\), and then \(s_{n+1} = f(\{x \in S: x \leq s_n \land x \neq s_n\})\). \(\{x \in S: x \leq s_n \land x \neq s_n\}\) is always nonempty, because else \(s_n\) would be a minimal element of \(S\). Then \(s\) forms an infinitely descending chain. Contradiction! For the converse, assume that every nonempty subset has a minimal element, and assume \((s_i)_{i = 0}^\infty\) is an infinite sequence with \(s_i \leq s_j\) for \(j < i\). Let \(S = \{s_i: i \in \mathbb{N}\}\). Therefore \(s\) is eventually constant, and so can't be infinitely strictly decreasing.