In
mathematics, especially in
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, two
ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
s and 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 and its
inverse are
monotonic
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
(preserving orders of elements). In the special case when is
totally ordered, monotonicity of implies monotonicity of its inverse.
For example, the
set of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s 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 number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s (with the standard ordering) do not have the same order type, because even though the sets are of the same
size
Size in general is the magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to linear dimensions ( length, width, height, diameter, perimeter), area, or volume. Size can also be m ...
(they are both
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 of rationals is order isomorphic to the rationals (since, for example,
is a strictly increasing bijection from the former to the latter); the rationals contained in the half-closed intervals
,1) and (0,1 and the closed interval
,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
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-ord ...
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. For example, the order type of the set of natural numbers is .
The order type of a well-ordered set is sometimes expressed as .
For example, consider the set of
even ordinal In mathematics, even and odd ordinals extend the concept of parity from the natural numbers to the ordinal numbers. They are useful in some transfinite induction proofs.
The literature contains a few equivalent definitions of the parity of an ordin ...
s less than :
:
Its order type is:
:
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
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rationa ...
is usually denoted
. If a set S has order type
, the order type of the
dual of S (the reversed order) is denoted
.
See also
*
Well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
External links
*
References
{{Order theory
Ordinal numbers