Namespaces
Variants
Actions

Difference between revisions of "Order type"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (Completed rendering of article in TeX.)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
''of a [[Totally ordered set|totally ordered set]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700901.png" />''
+
''of a [[Totally ordered set|totally ordered set]] $ A $
  
A property of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700902.png" /> characteristic of every totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700903.png" /> similar to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700904.png" />. Two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700905.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700906.png" /> that are totally ordered by relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700907.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700908.png" /> are called ''[[similar sets|similar]]'' if there exists a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700909.png" /> that puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009011.png" /> into a one-to-one correspondence and is such that for all points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009012.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009013.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009014.png" /> to denote the order type of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009015.png" />. The order types of frequently encountered sets are denoted by special letters. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009016.png" /> is the set of natural numbers ordered by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009017.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009018.png" />. If the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009019.png" /> of rational numbers is ordered also by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009020.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009021.png" />. A totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009022.png" /> is of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009023.png" /> if and only if: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009024.png" /> has a first element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009025.png" />; 2) every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009026.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009027.png" /> has a successor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009028.png" />; and 3) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009029.png" /> and if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009030.png" /> contains the successor of each of its elements, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009031.png" />. There exists only one order type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009032.png" /> of non-empty sets which are dense, countable and have neither a first nor a last element (Cantor's theorem). A totally ordered set is of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009033.png" /> (the type of the set of real numbers) if it is continuous and contains a dense subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009034.png" /> of order type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009035.png" />.
+
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 sets|'''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:
 +
 
 +
# $ A $ has a first element $ a_{0} $;
 +
# every element $ x $ of $ A $ has a successor $ x + 1 $; and
 +
# 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 ordered set|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.
 
One can define operations on order types which are to some extent similar to arithmetical operations.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009037.png" /> be two order types, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009039.png" /> be totally ordered sets such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009042.png" />. By the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009043.png" /> one understands the order type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009044.png" />, where the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009045.png" /> is ordered in such a way that all elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009046.png" /> precede all elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009047.png" /> and for both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009048.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009049.png" /> the order is preserved. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009051.png" /> are positive integers, then the definition of the sum of order types coincides with the definition of the sum of positive integers. The following equalities are valid: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009053.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009054.png" /> is the order type of the empty set. The commutative law does not hold, in general, e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009055.png" />.
+
* 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.
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009057.png" />. By the product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009058.png" /> one understands the order type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009060.png" /> is ordered in such a way that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009062.png" /> are two of its elements, then the first element precedes the second if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009063.png" /> or (if the ordinates coincides) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009064.png" /> (the principle of different last elements). The following equalities hold: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009067.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009068.png" /> is the order type of a one-element set. Multiplication, unlike addition, is not commutative. For instance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009069.png" />. One distributive law holds: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009070.png" />. The product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009071.png" /> represents a continuous order type of the cardinality of the continuum which does not contain a countable dense subset.
 
  
Closely related to the sum and the product of order types are the sum of an arbitrary ordered set of order types (see [[Ordered sum|Ordered sum]]) and the [[lexicographic product]] of a well-ordered set of order types. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009072.png" /> be a family of totally ordered sets indexed by a well-ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009073.png" /> (cf. [[Well-ordered set|Well-ordered set]]), and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009074.png" /> be the Cartesian product of this family. The lexicographic product of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009075.png" /> is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009076.png" /> endowed with the following order. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009077.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009078.png" /> are elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009079.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009080.png" /> if and only if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009081.png" />, or if there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009082.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009083.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009085.png" /> (the principle of different first elements). If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009087.png" /> is the lexicographic product of the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009088.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009089.png" /> is called the product of the family of order types <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009090.png" />. Using the lexicographic product and the generalized [[Continuum hypothesis|continuum hypothesis]] it is possible to construct for every [[Cardinal number|cardinal number]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009091.png" /> a totally ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009092.png" /> of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009093.png" /> such that any totally ordered set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009094.png" /> is similar to some subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009095.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009096.png" /> is strongly inaccessible, then the generalized continuum hypothesis is not necessary for the proof of this theorem. In particular, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009097.png" /> (aleph zero) this set may be any totally ordered set of order type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o07009098.png" />.
+
Closely related to the sum and the product of order types are the [[Ordered sum|'''ordered sum''']] of an arbitrary ordered set of order types and the [[lexicographic product|'''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|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|continuum hypothesis]] ($ \mathsf{GCH} $), it is possible to construct, for every [[Cardinal number|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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  T.J. Jech,  "Set theory" , Acad. Press  (1978)  (Translated from German)</TD></TR></table>
 
  
 +
<table>
 +
<TR><TD valign="top">[1]</TD><TD valign="top">
 +
T.J. Jech, “Set theory”, Acad. Press (1978). (Translated from German)</TD></TR>
 +
</table>
  
 +
====Comments====
  
====Comments====
 
 
See also the references to [[Ordinal number|Ordinal number]].
 
See also the references to [[Ordinal number|Ordinal number]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> K. Kunen,   "Set theory" , North-Holland (1980)</TD></TR></table>
+
 
 +
<table>
 +
<TR><TD valign="top">[a1]</TD><TD valign="top">
 +
K. Kunen, “Set theory”, North-Holland (1980).</TD></TR>
 +
</table>

Latest revision as of 17:31, 5 January 2017

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).
How to Cite This Entry:
Order type. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_type&oldid=39363
This article was adapted from an original article by B.A. Efimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article