# 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 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) $(S,\leq )$ and $(T,\preceq )$, a function $f:S\to T$ is an order embedding if $f$ is both order-preserving and order-reflecting, i.e. for all $x$ and $y$ in $S$, one has
    $x\leq y{\text{ if and only if }}f(x)\preceq f(y).$
Such a function is necessarily injective, since $f(x)=f(y)$ implies $x\leq y$ and $y\leq x$. If an order embedding between two posets $S$ and $T$ exists, one says that $S$ can be embedded into $T$.

## Properties

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". 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 $(0,1)$ of real numbers and the corresponding closed interval $[0,1]$. The function $f(x)=(94x+3)/100$ maps the former to the subset $(0.03,0.97)$ of the latter and the latter to the subset $[0.03,0.97]$ of the former, see picture. Ordering both sets in the natural way, $f$ 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. $[0,1]$ has a least element while $(0,1)$ 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).
A retract is a pair $(f,g)$ of order-preserving maps whose composition $g\circ f$ is the identity. In this case, $f$ 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 $f:\emptyset \to \{1\}$ from the empty poset to a nonempty poset has no retract, because there is no order-preserving map $g:\{1\}\to \emptyset$. More illustratively, consider the set $S$ of divisors of 6, partially ordered by x divides y, see picture. Consider the embedded sub-poset $\{1,2,3\}$. A retract of the embedding $id:\{1,2,3\}\to S$ would need to send $6$ to somewhere in $\{1,2,3\}$ above both $2$ and $3$, 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.