Namespaces
Variants
Actions

Difference between revisions of "Order type"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (Link)
Line 9: Line 9:
 
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.
 
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 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====
 
====References====

Revision as of 16:42, 11 June 2016

of a totally ordered set

A property of the set characteristic of every totally ordered set similar to . Two sets and that are totally ordered by relations and are called similar if there exists a function that puts and into a one-to-one correspondence and is such that for all points one has . 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 to denote the order type of the set . The order types of frequently encountered sets are denoted by special letters. For example, if is the set of natural numbers ordered by the relation , then . If the set of rational numbers is ordered also by the relation , then . A totally ordered set is of type if and only if: 1) has a first element ; 2) every element of has a successor ; and 3) if and if the set contains the successor of each of its elements, then . There exists only one order type 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 (the type of the set of real numbers) if it is continuous and contains a dense subset of order type .

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

Let and be two order types, and let and be totally ordered sets such that , and . By the sum one understands the order type , where the set is ordered in such a way that all elements of precede all elements of and for both and the order is preserved. In particular, if and 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: and , where is the order type of the empty set. The commutative law does not hold, in general, e.g. .

Let and . By the product one understands the order type , where is ordered in such a way that if , are two of its elements, then the first element precedes the second if or (if the ordinates coincides) if (the principle of different last elements). The following equalities hold: , , , where is the order type of a one-element set. Multiplication, unlike addition, is not commutative. For instance, . One distributive law holds: . The product 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) and the lexicographic product of a well-ordered set of order types. Let be a family of totally ordered sets indexed by a well-ordered set (cf. Well-ordered set), and let be the Cartesian product of this family. The lexicographic product of the family is the set endowed with the following order. If and are elements of , then if and only if either , or if there exists an such that for all and (the principle of different first elements). If and is the lexicographic product of the family , then is called the product of the family of order types . Using the lexicographic product and the generalized continuum hypothesis it is possible to construct for every cardinal number a totally ordered set of cardinality such that any totally ordered set of cardinality is similar to some subset of . If is strongly inaccessible, then the generalized continuum hypothesis is not necessary for the proof of this theorem. In particular, for (aleph zero) this set may be any totally ordered set of order type .

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=11517
This article was adapted from an original article by B.A. Efimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article