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 strictly weaker than the concept of an order isomorphism. Both of these weakenings may be understood in terms of category theory.
Formally, given two partially ordered sets (posets) and , a function is an order embedding if is both order-preserving and order-reflecting, i.e. for all and in , one has
Such a function is necessarily injective, since implies and . [1] If an order embedding between two posets and exists, one says that can be embedded into .
![Mutual order embedding of
(
0
,
1
)
{\displaystyle (0,1)}
and
[
0
,
1
]
{\displaystyle [0,1]}
, using
f
(
x
)
=
(
94
x
+
3
)
/
100
{\displaystyle f(x)=(94x+3)/100}
in both directions. Mutual embedding of open and closed real unit interval svg.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e5/Mutual_embedding_of_open_and_closed_real_unit_interval_svg.svg/300px-Mutual_embedding_of_open_and_closed_real_unit_interval_svg.svg.png)
An order isomorphism can be characterized as a surjective order embedding. As a consequence, any order embedding f restricts to an isomorphism between its domain S and its image f(S), which justifies the term "embedding". [1] On the other hand, it might well be that two (necessarily infinite) posets are mutually order-embeddable into each other without being order-isomorphic.
An example is provided by the open interval of real numbers and the corresponding closed interval . The function maps the former to the subset of the latter and the latter to the subset of the former, see picture. Ordering both sets in the natural way, is both order-preserving and order-reflecting (because it is an affine function ). Yet, no isomorphism between the two posets can exist, since e.g. has a least element while does not. For a similar example using arctan to order-embed the real numbers into an interval, and the identity map for the reverse direction, see e.g. Just and Weese (1996). [2]
A retract is a pair of order-preserving maps whose composition is the identity. In this case, is called a coretraction, and must be an order embedding. [3] However, not every order embedding is a coretraction. As a trivial example, the unique order embedding from the empty poset to a nonempty poset has no retract, because there is no order-preserving map . More illustratively, consider the set of divisors of 6, partially ordered by x divides y, see picture. Consider the embedded sub-poset . A retract of the embedding would need to send to somewhere in above both and , but there is no such place.
 |
Posets can straightforwardly be viewed from many perspectives, and order embeddings are basic enough that they tend to be visible from everywhere. For example:
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 isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".
In mathematics, especially order theory, a partially ordered set 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 relation indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order."
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 on some set , which satisfies the following for all and in :
In mathematics, a monotonic 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 theory.
In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.
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 fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.
In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.
In mathematics, especially in order theory, a maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some preordered set is defined dually as an element of S that is not greater than any other element in S.
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 introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included. Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts.
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. Dushnik & Miller (1941) first studied order dimension; for a more detailed treatment of this subject than provided here, see Trotter (1992).
In mathematics, especially order theory, the interval order for a collection of intervals on the real line is the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2. More formally, a countable poset is an interval order if and only if there exists a bijection from to a set of real intervals, so , such that for any we have in exactly when . Such posets may be equivalently characterized as those with no induced subposet isomorphic to the pair of two-element chains, in other words as the -free posets .
In probability theory and statistics, a stochastic order quantifies the concept of one random variable being "bigger" than another. These are usually partial orders, so that one random variable may be neither stochastically greater than, less than nor equal to another random variable . Many different orders exist, which have different applications.
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 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 embeddings and Galois connections.
The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length . These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.
In mathematics, in particular in category theory, the lifting property is a property of a pair of morphisms in a category. It is used in homotopy theory within algebraic topology to define properties of morphisms starting from an explicitly given class of morphisms. It appears in a prominent way in the theory of model categories, an axiomatic framework for homotopy theory introduced by Daniel Quillen. It is also used in the definition of a factorization system, and of a weak factorization system, notions related to but less restrictive than the notion of a model category. Several elementary notions may also be expressed using the lifting property starting from a list of (counter)examples.
In mathematics, particularly in algebraic topology, taut pair is a topological pair whose direct limit of cohomology module of open neighborhood of that pair which is directed downward by inclusion is isomorphic to the cohomology module of original pair.
