In mathematics, especially in set theory, two ordered sets 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 i.e. 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.
Contents
For example, the set of integers and the set of even integers have the same order type, because the mapping
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. 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 V is sometimes expressed as ord(V).
For example, consider the set of even ordinals 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 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