Order embedding

In mathematical order theory, 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 (S, ≤) and (T, ≤), a function f: ST 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)\leq f(y).$ 

Note that such a function is necessarily injective, since f(x) = f(y) implies xy and yx. 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 range f(S), which justifies the term "embedding". On the other hand, it might well be that two (necessarily infinite) posets are mutually embeddable into each other without being isomorphic. An example is provided by the set of real numbers and its interval [−1,1]. Ordering both sets in the natural way, one clearly finds that [−1,1] can be embedded into the reals. On the other hand, one can define a function e from the real numbers to [−1,1] as

$e(x)={\frac {2}{\pi }}\arctan x$

This is the projection of the real number line to (half of) the circle with circumference 4 (see trigonometric functions for details) and embeds the reals into [−1,1]. Yet, the two posets are not isomorphic: [−1,1] has both a least and a greatest element, which are not present in the case of the real numbers. This shows that an isomorphism cannot exist.

In a retract (a pair of order-preserving maps whose composition is the identity), the first of the two maps (called a coretraction) must be an order embedding. However, not every order embedding is a coretraction. As a trivial example of this phenomenon, the unique order embedding from the empty poset to a nonempty poset P has no retract, because there is no order-preserving map from P to the empty poset. More illustratively, consider the "diamond poset" with elements {00, 01, 10, 11} with 00 < 01 < 11, 00 < 10 < 11 and 01 incomparable to 10. Consider the embedded sub-poset "V" consisting of {00, 01, 10} (with 00 < 01 and 00 < 10 and 01 incomparable to 10). A retract of the embedding V -> diamond would need to send 11 to somewhere in "V" above both 01 and 10, but there is no such place.