HOME

TheInfoList



OR:

In the
mathematical 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 ...
field of
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, an order isomorphism is a special kind of
monotone function 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 order ...
that constitutes a suitable notion of
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
for
partially 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 (mathematics), set. A poset consists of a set toget ...
s (posets). Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that either of the orders can be obtained from the other just by renaming of elements. Two strictly weaker notions that relate to order isomorphisms are
order embedding In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is str ...
s and
Galois connection In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...
s.


Definition

Formally, given two posets (S,\le_S) and (T,\le_T), an order isomorphism from (S,\le_S) to (T,\le_T) is a
bijective function In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
f from S to T with the property that, for every x and y in S, x \le_S y if and only if f(x)\le_T f(y). That is, it is a bijective
order-embedding In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is stric ...
. It is also possible to define an order isomorphism to be a
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
order-embedding. The two assumptions that f cover all the elements of T and that it preserve orderings, are enough to ensure that f is also one-to-one, for if f(x)=f(y) then (by the assumption that f preserves the order) it would follow that x\le y and y\le x, implying by the definition of a partial order that x=y. Yet another characterization of order isomorphisms is that they are exactly the
monotone Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony. Monotone or monotonicity may also refer to: In economics *Monotone preferences, a property of a consumer's preference ordering. *Monotonic ...
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
s that have a monotone inverse. An order isomorphism from a partially ordered set to itself is called an order
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
. When an additional algebraic structure is imposed on the posets (S,\le_S) and (T,\le_T), a function from (S,\le_S) to (T,\le_T) must satisfy additional properties to be regarded as an isomorphism. For example, given two
partially ordered group In abstract algebra, a partially ordered group is a group (''G'', +) equipped with a partial order "≤" that is ''translation-invariant''; in other words, "≤" has the property that, for all ''a'', ''b'', and ''g'' in ''G'', if ''a'' ≤ ''b'' ...
s (po-groups) (G, \le_G) and (H, \le_H), an isomorphism of po-groups from (G,\leq_G) to (H,\le_H) is an order isomorphism that is also a
group isomorphism In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two grou ...
, not merely a bijection that is an
order embedding In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is str ...
.


Examples

* The
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
on any partially ordered set is always an order automorphism. *
Negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
is an order isomorphism from (\mathbb,\leq) to (\mathbb,\geq) (where \mathbb is the set of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s and \le denotes the usual numerical comparison), since −''x'' ≥ −''y'' if and only if ''x'' ≤ ''y''. * The
open interval In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
(0,1) (again, ordered numerically) does not have an order isomorphism to or from the
closed interval In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
,1/math>: the closed interval has a least element, but the open interval does not, and order isomorphisms must preserve the existence of least elements. *By
Cantor's isomorphism theorem In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. For instance, there is an isomorphism (a one-to-one order-preserving co ...
, every unbounded countable dense linear order is isomorphic to the ordering of the
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. Explicit order isomorphisms between the quadratic algebraic numbers, the rational numbers, and the dyadic rational numbers are provided by Minkowski's question-mark function.


Order types

If f is an order isomorphism, then so is its
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X\t ...
. Also, if f is an order isomorphism from (S,\le_S) to (T,\le_T) and g is an order isomorphism from (T,\le_T) to (U,\le_U), then the
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
of f and g is itself an order isomorphism, from (S,\le_S) to (U,\le_U). Two partially ordered sets are said to be order isomorphic when there exists an order isomorphism from one to the other.. Identity functions, function inverses, and compositions of functions correspond, respectively, to the three defining characteristics of 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 relation ...
: reflexivity,
symmetry Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
, and transitivity. Therefore, order isomorphism is an equivalence relation. The class of partially ordered sets can be partitioned by it 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, families of partially ordered sets that are all isomorphic to each other. These equivalence classes are called
order type In mathematics, especially in set theory, two ordered sets 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 ...
s.


See also

*
Permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
, a permutation that is order-isomorphic to a subsequence of another permutation


Notes


References

*. *. *. *. {{Order theory Morphisms Order theory