Difference between revisions of "Order type"
(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) |
Order type. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Order_type&oldid=38962