en>Rklbstruna at 12:25, 3 February 2014

2014-02-03T12:25:45Z

New page

{{Distinguish2|[[Ordered type system|ordered types]]}}
In [[mathematics]], especially in [[set theory]], two [[ordered set]]s ''X,Y'' are said to have the same '''order type''' just when they are [[order isomorphic]], that is, when there exists a [[bijection]] (each element matches exactly one in the other set) ''f'': ''X'' → ''Y'' such that both ''f'' and its inverse are strictly increasing (order preserving) (the matching elements are also in the correct order). (In the special case when ''X'' is [[totally ordered]], monotonicity of ''f'' 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 <math>n\mapsto2n</math> preserves the order. But the set of integers and the set of rational numbers (with the standard ordering) are not order isomorphic, because, even though the sets are of the same [[Cardinality|size]] (they are both [[Countable set|countably infinite]]), there is no order-preserving bijective mapping between them. To these two order types we may add two more: the set of positive integers (which has a least element), and that of negative integers (which has a greatest element). The open interval (0,1) of rationals is order isomorphic to the rationals (since
:<math>y = \frac{2x - 1}{1 - \vert {2x - 1} \vert}</math>

provides a strictly increasing bijection from the former to the latter); the half-closed intervals [0,1) and (0,1], and the closed interval [0,1], 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 (mathematics)|ordinal number]]. The ordinal numbers are taken to be the [[canonical form|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 [[ω (ordinal number)|ω]].

The order type of a well-ordered set ''V'' is sometimes expressed as ord(''V'').<ref>[http://www.sjsu.edu/faculty/watkins/ordinals.htm Ordinal Numbers and Their Arithmetic]</ref>

For example, consider the set of [[even ordinal]]s less than ω·2+7, which is:

:''V'' = {0, 2, 4, 6, ...; ω, ω+2, ω+4, ...; ω·2, ω·2+2, ω·2+4, ω·2+6}.

Its order type is:

: ord(''V'') = ω·2+4 = {0, 1, 2, 3, ...; ω, ω+1, ω+2, ...; ω·2, ω·2+1, ω·2+2, ω·2+3}.

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 order|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 [[Rational number|rationals]] is usually denoted <math>\eta</math>. If a set S has order type <math>\sigma</math>, the order type of the [[Duality (order theory)|dual]] of S (the reversed order) is denoted <math>\sigma^{*}</math>.

==See also==

*[[Well-order]]

== External links ==
* {{mathworld|urlname=OrderType|title=Order Type}}

==References==
{{reflist}}

[[Category:Ordinal numbers]]

Inside–outside algorithm - Revision history

en>Rklbstruna at 12:25, 3 February 2014