Order embedding

{{Short description|Type of monotone function}} 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><ref name="dp02">{{citation | last1 = Davey | first1 = B. A. | last2 = Priestley | first2 = H. A. | contribution = Maps between ordered sets | edition = 2nd | isbn = 0-521-78451-4 | location = New York | mr = 1902334 | pages = 23–24 | publisher = Cambridge University Press | title = Introduction to Lattices and Order | title-link = Introduction to Lattices and Order | contribution-url = https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA23 | year = 2002}}.</ref>

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>.<ref name="dp02"/> If an order embedding exists from a poset <math>S</math> to a poset <math>T</math>, one says that <math>S</math> can be embedded into <math>T</math>.

== Properties == [[File:Mutual embedding of open and closed real unit interval svg.svg|thumb|300px|Mutual order embedding of <math>(0,1)</math> and <math>[0,1]</math>, using <math>f(x) = (94x+3)/100</math> in both directions.]] thumb|The set <math>S</math> of divisors of 6, partially ordered by ''x'' divides ''y''. The embedding <math>id: \{ 1,2,3 \} \to S</math> 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".<ref name="dp02"/> 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 <math>(0,1)</math> of real numbers and the corresponding closed interval <math>[0,1]</math>. The function <math>f(x) = (94x+3) / 100</math> maps the former to the subset <math>(0.03,0.97)</math> of the latter and the latter to the subset <math>[0.03,0.97]</math> of the former, see picture. Ordering both sets in the natural way, <math>f</math> 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. <math>[0,1]</math> has a least element while <math>(0,1)</math> 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).<ref>{{citation|title=Discovering Modern Set Theory: The basics|volume=8|series=Fields Institute Monographs|first1=Winfried|last1=Just|first2=Martin|last2=Weese|publisher=American Mathematical Society|year=1996|isbn=9780821872475|page=21|url=https://books.google.com/books?id=TPvHr7fcvHoC&pg=PA21}}</ref>

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.<ref>{{citation | last1 = Duffus | first1 = Dwight | last2 = Laflamme | first2 = Claude | last3 = Pouzet | first3 = Maurice | arxiv = math/0612458 | doi = 10.1007/s00012-008-2125-6 | issue = 1–2 | journal = Algebra Universalis | mr = 2453498 | pages = 243–255 | title = Retracts of posets: the chain-gap property and the selection property are independent | volume = 59 | year = 2008| s2cid = 14259820 }}.</ref> 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 == {{unreferenced section|date=October 2013}} 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==

Category:Order theory