View source for Order type

{{short description|Isomorphism type of ordered sets}}
{{distinguish|text=[[Ordered type system|ordered types]]}}
{{for|different types of financial orders|Order (exchange)}}
{{more footnotes|date=February 2023}}
{{one source |date=March 2024}}
In [[mathematics]], especially in [[set theory]], two [[ordered set]]s {{mvar|X}} and {{mvar|Y}} 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) <math>f\colon X \to Y</math> such that both {{mvar|f}} and its [[Inverse function|inverse]] are [[Monotonic#Monotonicity in order theory|monotonic]] (preserving orders of elements).

In the special case when {{mvar|X}} is [[totally ordered]], monotonicity of {{mvar|f}} 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 [[Partition of a set|partition]]s the [[Class (set theory)|class]] of all ordered sets into [[equivalence class]]es.

==Notation==
If a set <math>X</math> has order type denoted <math>\sigma</math>, the order type of the reversed order, the [[Duality (order theory)|dual]] of <math>X</math>, is denoted <math>\sigma^{*}</math>.

The order type of a well-ordered set {{mvar|X}} is sometimes expressed as {{math|ord(''X'')}}.<ref>{{Cite web |url=http://www.sjsu.edu/faculty/watkins/ordinals.htm |title=Ordinal Numbers and Their Arithmetic<!-- Bot generated title --> |access-date=2007-06-13 |archive-date=2009-10-27 |archive-url=https://web.archive.org/web/20091027100631/http://www.sjsu.edu/faculty/watkins/ordinals.htm |url-status=dead }}</ref>

==Examples==
The order type of the [[Integer number|integers]] and [[Rational number|rationals]] is usually denoted <math>\pi</math> and <math>\eta</math>, respectively. The [[Set (mathematics)|set]] of integers and the set of [[Parity (mathematics)|even]] integers have the same order type, because the mapping <math>n\mapsto 2n</math> 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 [[Cardinality|size]] (they are both [[Countable set|countably infinite]]), there is no order-preserving bijective mapping between them. The open interval {{math|(0, 1)}} of rationals is order isomorphic to the rationals, since, for example, <math>f(x) = \tfrac{2x - 1}{1 - \vert {2x - 1} \vert}</math> 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==
[[File:OrderTypeExamples svg.svg|thumb|400px|Three well-orderings on the set of natural numbers with distinct order types (''top to bottom''): <math>\omega</math>, <math>\omega+5</math>, and <math>\omega+\omega</math>.]]
Every [[well-ordered set]] is order-equivalent to exactly one [[ordinal number (mathematics)|ordinal number]], by definition. 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. Order types thus often take the form of arithmetic expressions of ordinals.

===Examples===
Firstly, the order type of the set of natural numbers is {{mvar|[[ω (ordinal number)|ω]]}}. Any other model of [[Peano arithmetic]], that is any [[Non-standard_model_of_arithmetic#Structure of countable non-standard models|non-standard model]], starts with a segment isomorphic to ω but then adds extra numbers. For example, any countable such model has order type {{nowrap|ω + (ω* + ω) &sdot; η}}.

Secondly, consider the set {{mvar|V}} of [[even ordinal]]s less than {{math|''ω'' &sdot; 2 + 7}}:
:<math>V = \{0,2,4,\ldots;\omega,\omega + 2,\omega + 4,\ldots;\omega\cdot 2,\omega\cdot 2 + 2, \omega\cdot 2 + 4, \omega\cdot 2 + 6\}.</math>
As this comprises two separate counting sequences followed by four elements at the end, the order type is
:<math>\operatorname{ord}(V) = \omega\cdot 2 + 4 = \{0, 1, 2, \ldots; \omega, \omega+1, \omega+2, \ldots; \omega\cdot 2, \omega\cdot 2 + 1, \omega\cdot 2 + 2, \omega\cdot 2 + 3\},</math>

==Rational numbers==
With respect to their standard ordering as numbers, the set of rationals is not well-ordered. Neither is the [[Completeness of the real numbers|completed]] set of reals, for that matter.

Any countable totally ordered set can be mapped injectively into the rational numbers in an order-preserving way. When the order is moreover [[dense order|dense]] and has no highest nor lowest element, there even exist a bijective such mapping.

==See also==

*[[Well-order]]

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

==References==

{{reflist}}

{{Order theory}}

[[Category:Ordinal numbers]]