View source for Order type

''of a [[Totally ordered set|totally ordered set]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070090/o0700901.png" />''

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 ordered set|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" />.

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 <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" />.

====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>



====Comments====
See also the references to [[Ordinal number|Ordinal number]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Kunen,   "Set theory" , North-Holland  (1980)</TD></TR></table>