HOME

TheInfoList



OR:

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 concer ...
, two ordered sets and are said to have the same order type if they are
order isomorphic In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...
, that is, if there exists a bijection (each element pairs with exactly one in the other set) f\colon X \to Y such that both and its
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when ad ...
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 language ...
s and the set of even integers have the same order type, because the mapping n\mapsto 2n 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 ra ...
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 (mathematics), 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 ...
(they are both
countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
), 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, f(x) = \tfrac 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 In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
, it partitions the class of all ordered sets into
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
es.


Order type of well-orderings

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. 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 ordinals less than : :V = \. Its order type is: :\operatorname(V) = \omega\cdot 2 + 4 = \, 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 \eta. If a set S has order type \sigma, the order type of the
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
of S (the reversed order) is denoted \sigma^.


See also

* Well-order


External links

*


References

{{Order theory Ordinal numbers