Order type

In mathematics, especially in set theory and order theory, two ordered sets Template:Mvar and Template:Mvar are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) $f:X\to Y$ such that both Template:Mvar and its inverse are monotonic (preserving orders of elements).

In the special case when Template:Mvar is totally ordered, monotonicity of Template:Mvar already implies monotonicity of its inverse.

One and the same set may be equipped with different orders. Since order-equivalence is an equivalence relation, it partitions the class of all ordered sets into equivalence classes.

Notation

If a set $X$ has order type denoted $\sigma$, the order type of the reversed order, the dual of $X$, is denoted ${\sigma }^{\ast }$.

The order type of a well-ordered set Template:Mvar is sometimes expressed as Template:Math.

Examples of ordering

The order type of the integers and rationals is usually denoted $\pi$ and $\eta$, respectively. The set of integers and the set of even integers have the same order type, because the mapping $n\mapsto 2n$ is a bijection that preserves the order. But the set of integers and the set of rational numbers (with the standard ordering) do not have the same order type, because even though the sets are of the same size (they are both countably infinite), there is no order-preserving bijective mapping between them. The open interval Template:Math of rationals is order isomorphic to the rationals, since, for example, $f(x)=\frac{2x-1}{1-|2x-1|}$ is a strictly increasing bijection from the former to the latter. Relevant theorems of this sort are expanded upon below.

More examples can be given now: The set of positive integers (which has a least element), and that of negative integers (which has a greatest element). The natural numbers have order type denoted by ω, as explained below.

The rationals contained in the half-closed intervals [0,1) and (0,1], and the closed interval [0,1], are three additional order type examples.

Order type of well-orderings

Three well-orderings on the set of natural numbers with distinct order types (top to bottom): $\omega$, $\omega +5$, and $\omega +\omega$.

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. Order types thus often take the form of arithmetic expressions of ordinals.

Examples of well-ordering

Firstly, the order type of the set of natural numbers is Template:Mvar. Any other model of Peano arithmetic, that is any non-standard model, starts with a segment isomorphic to ω but then adds extra numbers. For example, any countable such model has order type Template:Nowrap.

Secondly, consider the set Template:Mvar of even ordinals less than Template:Math:

$V=\{0,2,4,\dots ;\omega ,\omega +2,\omega +4,\dots ;\omega \cdot 2,\omega \cdot 2+2,\omega \cdot 2+4,\omega \cdot 2+6\}.$

As this comprises two separate counting sequences followed by four elements at the end, the order type is

$\mathrm{ord}(V)=\omega \cdot 2+4=\{0,1,2,\dots ;\omega ,\omega +1,\omega +2,\dots ;\omega \cdot 2,\omega \cdot 2+1,\omega \cdot 2+2,\omega \cdot 2+3\},$

Rational numbers

With respect to their standard ordering as numbers, the set of rationals is not well-ordered. Neither is the completed set of reals, for that matter.

Any countable toset can be mapped injectively into the rational numbers in an order-preserving way. Moreover, when the order is dense and has no highest nor lowest element, there even exists an order-preserving bijection into $\mathbb{Q}$ — which, since the order is total, is then necessarily an order isomorphism. Hence, the order type of any such toset is precisely that of the rationals.

See also

• Well-order

External links

• Template:Mathworld