HOME

TheInfoList



Click Here for Items Related To - order type
OR:
order type on:   [Wikipedia]   [Google]   [Amazon]

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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) f\colon X \to Y 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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
, monotonicity of implies monotonicity of its inverse. For example, the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East ** Even language, a language spoken by the Evens * Odd and Even, a solitaire game w ...
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 ration ...
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, it
partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
s the
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
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 a ...
es.


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 In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least n ...
, 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 : :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 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 \eta. If a set S has order type \sigma, the order type of the dual of S (the reversed order) is denoted \sigma^.


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