Order embedding

Quality 0.50 · 2 views · Updated 2 months ago

Type of monotone function

title: "Order embedding" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["order-theory"] description: "Type of monotone function" topic_path: "general/order-theory" source: "https://en.wikipedia.org/wiki/Order_embedding" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Type of monotone function ::

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) (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 | 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 \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

::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/e5/Mutual_embedding_of_open_and_closed_real_unit_interval_svg.svg" caption="Mutual order embedding of (0,1) and [0,1], using f(x) = (94x+3)/100 in both directions."] ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/f/f8/Lattice_T(6).svg" caption="The set S of divisors of 6, partially ordered by ''x'' divides ''y''. The embedding id: { 1,2,3 } \to S 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". 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 | 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

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

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

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::