Order type

of a totally ordered set $ A $

A property of the set $ A $ characteristic of every totally ordered set $ B $ similar to $ A $. Two sets $ A $ and $ B $ that are totally ordered by relations $ R $ and $ S $ are called similar if and only if there exists a bijective function $ f: A \to B $ such that for all points $ x,y \in A $, one has $ (x,y) \in R \iff (f(x),f(y)) \in S $. G. Cantor defined the order type as that property of totally ordered sets that remains when the set is considered, not with respect to the properties of its elements, but with respect to their order. To underline the fact that only this abstraction step takes place, Cantor introduced the symbol $ \overline{A} $ to denote the order type of the set $ A $. The order types of frequently encountered sets are denoted by special letters. For example, if $ \mathbf{Z}^{+} $ denotes the set of natural numbers ordered by the relation $ \leq $, then $ \omega \stackrel{\text{df}}{=} \overline{\mathbf{Z}^{+}} $. If the set $ \mathbf{Q} $ of rational numbers is ordered also by the relation $ \leq $, then $ \eta \stackrel{\text{df}}{=} \overline{\mathbf{Q}} $. A totally ordered set $ A $ is of type $ \omega $ if and only if:

1. $ A $ has a first element $ a_{0} $;
2. every element $ x $ of $ A $ has a successor $ x + 1 $; and
3. if $ a_{0} \in X \subseteq A $ and if the set $ X $ contains the successor of each of its elements, then $ X = A $.

There exists only one order type $ \eta $ of non-empty sets that are dense, countable and have neither a first nor a last element (this is Cantor’s theorem). A totally ordered set is of type $ \lambda $ (the type of the set of real numbers $ \mathbf{R} $ ordered by $ \leq $) if and only if it is continuous and contains a dense subset $ A $ of order type $ \eta $.

One can define operations on order types which are to some extent similar to arithmetical operations.

• Let $ \alpha $ and $ \beta $ be two order types, and let $ A $ and $ B $ be totally ordered sets such that $ \alpha = \overline{A} $, $ \beta = \overline{B} $ and $ A \cap B = \varnothing $. By the sum $ \alpha + \beta $, one understands the order type $ \alpha + \beta \stackrel{\text{df}}{=} \overline{A \cup B} $, where the set $ A \cup B $ is ordered in such a way that all elements of $ A $ precede all elements of $ B $, and for both $ A $ and $ B $ themselves, the order is preserved. In particular, if $ \alpha $ and $ \beta $ are positive integers, then the definition of the sum of these order types coincides with the definition of the sum of positive integers. The following identities are valid: $$ (\alpha + \beta) + \gamma = \alpha + (\beta + \gamma) \qquad \text{and} \qquad \alpha + 0 = \alpha = 0 + \alpha, $$ where $ 0 $ is the order type of the empty set $ \varnothing $. The commutative law does not hold in general, e.g., $ \omega + 1 \neq 1 + \omega $.
• Let $ \alpha = \overline{A} $ and $ \beta = \overline{B} $. By the product $ \alpha \cdot \beta $, one understands the order type $ \alpha \cdot \beta \stackrel{\text{df}}{=} \overline{A \times B} $, where $ A \times B $ is ordered in such a way that if $ (x_{1},y_{1}) $ and $ (x_{2},y_{2}) $ are two of its elements, then the first element precedes the second if and only if either $ y_{1} < y_{2} $, or, when these coordinates coincide, $ x_{1} < x_{2} $ (the principle of different last elements). The following identities hold: $$ (\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma), \qquad \alpha \cdot 1 = \alpha = 1 \cdot \alpha \qquad \text{and} \qquad \alpha \cdot 0 = 0 = 0 \cdot \alpha, $$ where $ 1 $ is the order type of a singleton (i.e., one-element) set. Multiplication, like addition, is not commutative. For instance, $ \omega \cdot 2 \neq 2 \cdot \omega $. One distributive law does hold: $$ \alpha \cdot (\beta + \gamma) = \alpha \cdot \beta + \alpha \cdot \gamma. $$ The product $ (1 + \lambda + 1) \cdot \lambda $ represents a continuous order type of the cardinality of the continuum that does not contain a countable dense subset.

Closely related to the sum and the product of order types are the ordered sum of an arbitrary ordered set of order types and the lexicographic product of a well-ordered set of order types. Let $ (A_{m})_{m \in M} $ be a family of totally ordered sets indexed by a well-ordered set $ M $, and let $ \displaystyle A \stackrel{\text{df}}{=} \prod_{m \in M} A_{m} $ be the Cartesian product of this family. The lexicographic product of the family $ (A_{m})_{m \in M} $ is the set $ A $ endowed with the following order: If $ (a_{m})_{m \in M} $ and $ (b_{m})_{m \in M} $ are elements of $ A $, then $ (a_{m})_{m \in M} < (b_{m})_{m \in M} $ if and only if either $ a_{1} < b_{1} $, or there exists an $ m_{0} \in M $ such that $ a_{m} = b_{m} $ for all $ m < m_{0} $ and $ a_{m_{0}} < b_{m_{0}} $ (the principle of different first elements). If $ \alpha_{m} \stackrel{\text{df}}{=} \overline{A_{m}} $ and $ A $ is the lexicographic product of the family $ (A_{m})_{m \in M} $, then $ \displaystyle \alpha \stackrel{\text{df}}{=} \prod_{m \in M} \alpha_{m} = \overline{A} $ is called the product of the family $ (\alpha_{m})_{m \in M} $ of order types. Using the lexicographic product and the generalized continuum hypothesis ($ \mathsf{GCH} $), it is possible to construct, for every cardinal number $ \tau $, a totally ordered set $ \eta_{\tau} $ of cardinality $ \tau $ such that any totally ordered set of cardinality $ \leq \tau $ is similar to some subset of $ \eta_{\tau} $. If $ \tau $ is strongly inaccessible, then $ \mathsf{GCH} $ is not necessary for the proof of this theorem. In particular, for $ \tau = \aleph_{0} $, this set may be any totally ordered set of order type $ \eta $.

References

[1]	T.J. Jech, “Set theory”, Acad. Press (1978). (Translated from German)

Comments

See also the references to Ordinal number.

References

[a1]	K. Kunen, “Set theory”, North-Holland (1980).