Order embedding

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).{{citation | title-link = Introduction to Lattices and Order | contribution-url = https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA23

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.{{citation

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.

References

References

1. (1996). "Discovering Modern Set Theory: The basics". American Mathematical Society.