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 and more specifically in topology, a homeomorphism, also called topological isomorphism, or bicontinuous function, is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are the mappings that preserve all the topological properties of a given space. Two spaces with a homeomorphism between them are called homeomorphic, and from a topological viewpoint they are the same.
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 partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.
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 category theory, an epimorphism is a morphism f : X → Y that is right-cancellative in the sense that, for all objects Z and all morphisms g1, g2: Y → Z,
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.
Freiling's axiom of symmetry is a set-theoretic axiom proposed by Chris Freiling. It is based on intuition of Stuart Davidson but the mathematics behind it goes back to Wacław Sierpiński.
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 topology, a branch of mathematics, two continuous functions from one topological space to another are called homotopic if one can be "continuously deformed" into the other, such a deformation being called a homotopy between the two functions. A notable use of homotopy is the definition of homotopy groups and cohomotopy groups, important invariants in algebraic topology.
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. In other cases the dual of the dual – the double dual or bidual – is not necessarily identical to the original. 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 combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.
In mathematics, a path in a topological space is a continuous function from a closed interval into
In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets.
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 .
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.
