Order type


In mathematics, especially in set theory, two ordered sets and are said to have the same order type if they are order isomorphic, that is, if there exists a bijection such that both and its inverse are monotonic. In the special case when is totally ordered, monotonicity of implies monotonicity of its inverse.
For example, the set of integers and the set of even integers have the same order type, because the mapping is a bijection that preserves the order. But the set of integers and the set of rational numbers do not have the same order type, because even though the sets are of the same size, there is no order-preserving bijective mapping between them. To these two order types we may add two more: the set of positive integers, and that of negative integers. The open interval of rationals is order isomorphic to the rationals and (0,1], and the closed interval , are three additional order type examples.
Since order-equivalence is an equivalence relation, it partitions the class of all ordered sets into equivalence classes.

Order type of well-orderings

Every well-ordered set is order-equivalent to exactly one ordinal number. The ordinal numbers are taken to be the canonical representatives of their classes, and so the order type of a well-ordered set is usually identified with the corresponding ordinal. For example, the order type of the natural numbers is ω |.
The order type of a well-ordered set is sometimes expressed as.
For example, consider the set of even ordinals less than :
Its order type is:
because there are 2 separate lists of counting and 4 in sequence at the end.

Rational numbers

Any countable totally ordered set can be mapped injectively into the rational numbers in an order-preserving way.
Any dense countable totally ordered set with no highest and no lowest element can be mapped bijectively onto the rational numbers in an order-preserving way.

Notation

The order type of the rationals is usually denoted. If a set S has order type, the order type of the dual of S is denoted.