Order embedding

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.

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. Such a function is necessarily injective, since f(x) = f(y) implies x \leq y and y \leq x . If an order embedding exists from a poset S to a poset T , one says that S can be embedded into T . [[File:Mutual embedding of open and closed real unit interval svg.svg|thumb|300px|Mutual order embedding of (0,1) and [0,1] , using f(x) = (94x+3)/100 in both directions.]] 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. However, not every order embedding is a coretraction. As a trivial example, the unique order embedding f: \emptyset \to \{1\} from the empty poset to a nonempty poset has no retract, because there is no order-preserving map g: \{1\} \to \emptyset . More illustratively, consider the set S of divisors of 6, partially ordered by x divides y, see picture. Consider the embedded sub-poset \{ 1,2,3 \} . A retract of the embedding id: \{ 1,2,3 \} \to S would need to send 6 to somewhere in \{ 1,2,3 \} above both 2 and 3 , but there is no such place. ==See also== Dushnik–Miller theorem Laver's theorem ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1349771404 under CC BY-SA 4.0; modifications have been made.