alt=Order embedding visualized example|thumb|An example of an order embedding. The left ordered set (in red) is embedded into the right ordered set.
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.
Formal definition
Formally, given two partially ordered sets (posets) <math>(S, \leq)</math> and <math>(T, \preceq)</math>, a function <math>f: S \to T</math> is an order embedding if <math>f</math> is both order-preserving and order-reflecting, i.e. for all <math>x</math> and <math>y</math> in <math>S</math>, one has
: <math>x\leq y \text{ if and only if } f(x)\preceq f(y).</math>
Such a function is necessarily injective, since <math>f(x) = f(y)</math> implies <math>x \leq y</math> and <math>y \leq x</math>.
A retract is a pair <math>(f,g)</math> of order-preserving maps whose composition <math>g \circ f</math> is the identity. In this case, <math>f</math> is called a coretraction, and must be an order embedding. However, not every order embedding is a coretraction. As a trivial example, the unique order embedding <math>f: \emptyset \to \{1\}</math> from the empty poset to a nonempty poset has no retract, because there is no order-preserving map <math>g: \{1\} \to \emptyset</math>. More illustratively, consider the set <math>S</math> of divisors of 6, partially ordered by x divides y, see picture. Consider the embedded sub-poset <math>\{ 1,2,3 \}</math>. A retract of the embedding <math>id: \{ 1,2,3 \} \to S</math> would need to send <math>6</math> to somewhere in <math>\{ 1,2,3 \}</math> above both <math>2</math> and <math>3</math>, but there is no such place.
Additional perspectives
Posets can straightforwardly be viewed from many perspectives, and order embeddings are basic enough that they tend to be visible from everywhere. For example:
- (Model theoretically) A poset is a set equipped with a (reflexive, antisymmetric and transitive) binary relation. An order embedding A → B is an isomorphism from A to an elementary substructure of B.
- (Graph theoretically) A poset is a (transitive, acyclic, directed, reflexive) graph. An order embedding A → B is a graph isomorphism from A to an induced subgraph of B.
- (Category theoretically) A poset is a (small, thin, and skeletal) category such that each homset has at most one element. An order embedding A → B is a full and faithful functor from A to B which is injective on objects, or equivalently an isomorphism from A to a full subcategory of B.
See also
- Dushnik–Miller theorem
- Laver's theorem