Namespaces
Variants
Actions

Order type

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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