order embedding

Formally, given two partially ordered sets (posets) $(S,\; \backslash leq)$ and $(T,\; \backslash preceq)$, a function $f:\; S\; \backslash 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\backslash leq\; y\; \backslash text\{\; if\; and\; only\; if\; \}\; f(x)\backslash preceq\; f(y).${{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}}.

Such a function is necessarily injective, since $f(x)\; =\; f(y)$ implies $x\; \backslash leq\; y$ and $y\; \backslash leq\; x$. If an order embedding between two posets $S$ and $T$ exists, one says that $S$ can be embedded into $T$.

File:Mutual embedding of open and closed real unit interval svg.svg

File:Lattice T(6).svg

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).{{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}}

A retract is a pair $(f,g)$ of order-preserving maps whose composition $g\; \backslash circ\; f$ is the identity. In this case, $f$ is called a coretraction, and must be an order embedding.{{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

}}. However, not every order embedding is a coretraction. As a trivial example, the unique order embedding $f:\; \backslash emptyset\; \backslash to\; \backslash \{1\backslash \}$ from the empty poset to a nonempty poset has no retract, because there is no order-preserving map $g:\; \backslash \{1\backslash \}\; \backslash to\; \backslash emptyset$. More illustratively, consider the set $S$ of divisors of 6, partially ordered by x divides y, see picture. Consider the embedded sub-poset $\backslash \{\; 1,2,3\; \backslash \}$. A retract of the embedding $id:\; \backslash \{\; 1,2,3\; \backslash \}\; \backslash to\; S$ would need to send $6$ to somewhere in $\backslash \{\; 1,2,3\; \backslash \}$ above both $2$ and $3$, but there is no such place.

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

• Dushnik–Miller theorem
• Laver's theorem

{{reflist}}

{{Order theory}}

Category:Order theory