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

edit

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

 [1]

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  .

Properties

edit
 
Mutual order embedding of   and  , using   in both directions.
 
The set   of divisors of 6, partially ordered by x divides y. The embedding   cannot be a coretraction.

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.

Additional perspectives

edit

Posets can straightforwardly be viewed from many perspectives, and order embeddings are basic enough that they tend to be visible from everywhere. For example:

See also

edit

References

edit
  1. ^ a b c Davey, B. A.; Priestley, H. A. (2002), "Maps between ordered sets", Introduction to Lattices and Order (2nd ed.), New York: Cambridge University Press, pp. 23–24, ISBN 0-521-78451-4, MR 1902334.
  2. ^ Just, Winfried; Weese, Martin (1996), Discovering Modern Set Theory: The basics, Fields Institute Monographs, vol. 8, American Mathematical Society, p. 21, ISBN 9780821872475
  3. ^ Duffus, Dwight; Laflamme, Claude; Pouzet, Maurice (2008), "Retracts of posets: the chain-gap property and the selection property are independent", Algebra Universalis, 59 (1–2): 243–255, arXiv:math/0612458, doi:10.1007/s00012-008-2125-6, MR 2453498, S2CID 14259820.