Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Order type
Summary
In mathematics, especially in set theory, two ordered sets X and 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) such that both f and its inverse are monotonic (preserving orders of elements).
In the special case when X is totally ordered, monotonicity of 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 partitions the class of all ordered sets into equivalence classes.
If a set has order type denoted , the order type of the reversed order, the dual of , is denoted .
The order type of a well-ordered set X is sometimes expressed as ord(X).
The order type of the integers and rationals is usually denoted and , respectively. 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 (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 (0, 1) of rationals is order isomorphic to the rationals, since, for example, 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.
Every well-ordered set is order-equivalent to exactly one ordinal number, by definition. 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.