# Order embedding

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Order_embedding
> Markdown URL: https://mediated.wiki/source/Order_embedding.md
> Source: https://en.wikipedia.org/wiki/Order_embedding
> Source revision: 1349771404
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of monotone function

An example of an order embedding. The left ordered set (in red) is embedded into the right ordered set.

In [order theory](/source/Order_theory), a branch of [mathematics](/source/Mathematics), an **order embedding** is a special kind of [monotone function](/source/Monotone_function), which provides a way to include one [partially ordered set](/source/Partially_ordered_set) into another. Like [Galois connections](/source/Galois_connection), order embeddings constitute a notion which is strictly weaker than the concept of an [order isomorphism](/source/Order_isomorphism). Both of these weakenings may be understood in terms of [category theory](/source/Category_theory).

## Formal definition

Formally, given two partially ordered sets (posets) ( S , ≤ ) {\displaystyle (S,\leq )} and ( T , ⪯ ) {\displaystyle (T,\preceq )} , a [function](/source/Function_(mathematics)) f : S → T {\displaystyle f:S\to T} is an *order embedding* if f {\displaystyle f} is both [order-preserving](/source/Order-preserving) and [order-reflecting](/source/Order-reflecting), i.e. for all x {\displaystyle x} and y {\displaystyle y} in S {\displaystyle S} , one has

- x ≤ y if and only if f ( x ) ⪯ f ( y ) . {\displaystyle x\leq y{\text{ if and only if }}f(x)\preceq f(y).} [1]

Such a function is necessarily [injective](/source/Injective), since f ( x ) = f ( y ) {\displaystyle f(x)=f(y)} implies x ≤ y {\displaystyle x\leq y} and y ≤ x {\displaystyle y\leq x} .[1] If an order embedding exists from a poset S {\displaystyle S} to a poset T {\displaystyle T} , one says that S {\displaystyle S} can be embedded into T {\displaystyle T} .

## Properties

Mutual order embedding of

        (
        0
        ,
        1
        )

    {\displaystyle (0,1)}

 and

        [
        0
        ,
        1
        ]

    {\displaystyle [0,1]}

, using

        f
        (
        x
        )
        =
        (
        94
        x
        +
        3
        )

          /

        100

    {\displaystyle f(x)=(94x+3)/100}

 in both directions.

The set

        S

    {\displaystyle S}

 of divisors of 6, partially ordered by *x* divides *y*. The embedding

        i
        d
        :
        {
        1
        ,
        2
        ,
        3
        }
        →
        S

    {\displaystyle id:\{1,2,3\}\to S}

 cannot be a coretraction.

An order isomorphism can be characterized as a [surjective](/source/Surjective) order embedding. As a consequence, any order embedding *f* restricts to an isomorphism between its [domain](/source/Domain_of_a_function) *S* and its [image](/source/Image_(mathematics)) *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](/source/Open_interval) ( 0 , 1 ) {\displaystyle (0,1)} of [real numbers](/source/Real_number) and the corresponding [closed interval](/source/Closed_interval) [ 0 , 1 ] {\displaystyle [0,1]} . The function f ( x ) = ( 94 x + 3 ) / 100 {\displaystyle f(x)=(94x+3)/100} maps the former to the [subset](/source/Subset) ( 0.03 , 0.97 ) {\displaystyle (0.03,0.97)} of the latter and the latter to the subset [ 0.03 , 0.97 ] {\displaystyle [0.03,0.97]} of the former, see picture. Ordering both sets in the natural way, f {\displaystyle f} is both order-preserving and order-reflecting (because it is an [affine function](/source/Linear_function)). Yet, no isomorphism between the two posets can exist, since e.g. [ 0 , 1 ] {\displaystyle [0,1]} has a [least element](/source/Least_element) while ( 0 , 1 ) {\displaystyle (0,1)} does not. For a similar example using arctan to order-embed the real numbers into an interval, and the [identity map](/source/Identity_map) for the reverse direction, see e.g. Just and Weese (1996).[2]

A retract is a pair ( f , g ) {\displaystyle (f,g)} of order-preserving maps whose [composition](/source/Function_composition) g ∘ f {\displaystyle g\circ f} is the identity. In this case, f {\displaystyle f} 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 f : ∅ → { 1 } {\displaystyle f:\emptyset \to \{1\}} from the empty poset to a nonempty poset has no retract, because there is no order-preserving map g : { 1 } → ∅ {\displaystyle g:\{1\}\to \emptyset } . More illustratively, consider the set S {\displaystyle S} of [divisors](/source/Divisor) of 6, partially ordered by *x* [divides](/source/Divides) *y*, see picture. Consider the embedded sub-poset { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} . A retract of the embedding i d : { 1 , 2 , 3 } → S {\displaystyle id:\{1,2,3\}\to S} would need to send 6 {\displaystyle 6} to somewhere in { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} above both 2 {\displaystyle 2} and 3 {\displaystyle 3} , but there is no such place.

## Additional perspectives

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (October 2013) (Learn how and when to remove this message)

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](/source/Model_theory)) *A* poset is a set equipped with a (reflexive, antisymmetric and transitive) [binary relation](/source/Binary_relation). An order embedding *A* → *B* is an isomorphism from *A* to an [elementary substructure](/source/Elementary_substructure) of *B*.

- ([Graph theoretically](/source/Graph_theory)) *A* poset is a (transitive, acyclic, directed, reflexive) [graph](/source/Graph_(discrete_mathematics)). An order embedding *A* → *B* is a [graph isomorphism](/source/Graph_isomorphism) from *A* to an [induced subgraph](/source/Induced_subgraph) of *B*.

- ([Category theoretically](/source/Category_theory)) A poset is a (small, thin, and skeletal) [category](/source/Category_(mathematics)) such that each [homset](/source/Hom-set) has at most one element. An order embedding *A* → *B* is a full and faithful [functor](/source/Functor) from *A* to *B* which is injective on objects, or equivalently an isomorphism from *A* to a [full subcategory](/source/Full_subcategory) of *B*.

## See also

- [Dushnik–Miller theorem](/source/Dushnik%E2%80%93Miller_theorem)

- [Laver's theorem](/source/Laver's_theorem)

## References

1. ^ [***a***](#cite_ref-dp02_1-0) [***b***](#cite_ref-dp02_1-1) [***c***](#cite_ref-dp02_1-2) Davey, B. A.; Priestley, H. A. (2002), ["Maps between ordered sets"](https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA23), [*Introduction to Lattices and Order*](/source/Introduction_to_Lattices_and_Order) (2nd ed.), New York: Cambridge University Press, pp. 23–24, [ISBN](/source/ISBN_(identifier)) [0-521-78451-4](https://en.wikipedia.org/wiki/Special:BookSources/0-521-78451-4), [MR](/source/MR_(identifier)) [1902334](https://mathscinet.ams.org/mathscinet-getitem?mr=1902334).

1. **[^](#cite_ref-2)** Just, Winfried; Weese, Martin (1996), [*Discovering Modern Set Theory: The basics*](https://books.google.com/books?id=TPvHr7fcvHoC&pg=PA21), Fields Institute Monographs, vol. 8, American Mathematical Society, p. 21, [ISBN](/source/ISBN_(identifier)) [9780821872475](https://en.wikipedia.org/wiki/Special:BookSources/9780821872475)

1. **[^](#cite_ref-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](/source/ArXiv_(identifier)):[math/0612458](https://arxiv.org/abs/math/0612458), [doi](/source/Doi_(identifier)):[10.1007/s00012-008-2125-6](https://doi.org/10.1007%2Fs00012-008-2125-6), [MR](/source/MR_(identifier)) [2453498](https://mathscinet.ams.org/mathscinet-getitem?mr=2453498), [S2CID](/source/S2CID_(identifier)) [14259820](https://api.semanticscholar.org/CorpusID:14259820).

v t e Order theory Topics Glossary Category Key concepts Binary relation Boolean algebra Cyclic order Lattice Partially ordered set Preorder Total order Weak ordering Results Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma Properties & Types (list) Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Partially ordered set Chain-complete Eulerian Graded Locally finite Strict Prefix order Preorder Total Reflexive Semilattice Semiorder Symmetric Tolerance Total Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order Constructions Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure Topology & Orders Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed Related Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

---
Adapted from the Wikipedia article [Order embedding](https://en.wikipedia.org/wiki/Order_embedding) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Order_embedding?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.