Order embedding

From Quire, the open reference·Type of monotone function·2 min read

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) ${\displaystyle (S,\leq )}$ and ${\displaystyle (T,\preceq )}$ , a function ${\displaystyle f:S\to T}$ is an order embedding if ${\displaystyle f}$ is both order-preserving and order-reflecting, i.e. for all ${\displaystyle x}$ and ${\displaystyle y}$ in ${\displaystyle S}$ , one has

${\displaystyle x\leq y{\text{ if and only if f(x)\preceq f(y).}$ ^[1]

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

Properties#edit

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 ${\displaystyle (0,1)}$ of real numbers and the corresponding closed interval ${\displaystyle [0,1]}$ . The function ${\displaystyle f(x)=(94x+3)/100}$ maps the former to the subset ${\displaystyle (0.03,0.97)}$ of the latter and the latter to the subset ${\displaystyle [0.03,0.97]}$ of the former, see picture. Ordering both sets in the natural way, ${\displaystyle 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. ${\displaystyle [0,1]}$ has a least element while ${\displaystyle (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).^[2]

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

(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#edit

^ 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.
^ Just, Winfried; Weese, Martin (1996), Discovering Modern Set Theory: The basics, Fields Institute Monographs, vol. 8, American Mathematical Society, p. 21, ISBN 9780821872475
^ 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.

Categories Order theory

This article is mirrored from “Order embedding” on English Wikipedia, revision 1349771404, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1349771404 · just now

Order embedding

Formal definition#edit

Properties#edit

Additional perspectives#edit

See also#edit

References#edit