Order-embedding

In mathematical order theory, 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. A way to understand the different nature of both of these weakenings by exploiting some category theory is discussed at the end of this article.

Formal definition

Formally, given two partially ordered sets (S, ≤) and (T, <=), a function f: S → 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 ≤ y iff f(x) <= f(y)

Note that such a function is necessarily injective, since f(x) = f(y) implies x ≤ y and y ≤ x. If an order-embedding between two posets S and T exists, one says that S can be embedded into T.

Properties

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 range f(S), which justifies the term "embedding". On the other hand, it might well be that two (necessarily infinite) posets are mutually embeddable into each other without being isomorphic. An example is provided by the set of real numbers and its interval [−1,1]. Ordering both sets in the natural way, one clearly finds that [−1,1] can be embedded into the reals. On the other hand, one can define a function e from the real numbers to [−1,1] as

<math>e(x) = \frac{2}{\pi}\arctan r<math>

This is in fact just the projection of the real number line to (half of) the circle with circumference 4 (see trigonometric functions for details). Now it is easy to see that e embeds the reals into [−1,1]. Yet, the two posets are not isomorphic: [−1,1] has both a least and a greatest element, which are not present in the case of the real numbers. This shows that an isomorphism cannot exist.

Categorically speaking

The basic category for the study of partial orders is the category of posets and monotone functions. Since a categorical perspective usually has an enlightening effect in the study of mathematical subjects, one may well wonder what role order-embeddings play in this category. While the categorical significance of order-isomorphisms is quite obvious (being just isomorphisms in the categorical sense), embeddings may deserve some discussion. It turns out that the order-embeddings with non-empty domain correspond exactly to the sections in the category of posets. Remember that a section s is just a morphism that has a left-inverse r (called retraction), where r o s = id. Although all mappings from the empty poset to some other poset are order-embeddings, these can in general not be inverted (since there is no mapping from a non-empty set to the empty set). Note that in addition to injectivity (implying that a mapping is monic), one needs reflection of the order to find a monotone left-inverse. Thus order-embeddings specialize the notion of a sub-poset in the same way that sections specify monomorphisms.

This correspondence also helps to understand the difference of Galois connections and order-embeddings, which in a sense are both weakenings of the concept of an order-isomorphism. It is helpful to consider the abovementioned category as a category of categories: this can be done by noting that any poset is in fact a small-category with at most one arrow between two objects (pointing "upwards" in the order) and that functors between those categories correspond exactly to monotone mappings. As just demonstrated order-embeddings basically agree with sections in this category. On the other hand, Galois connections yield an adjunction between the related poset-categories. Hence order-embeddings (being sections) are a weaker form of isomorphisms within this category (i.e. of isomorphisms of categories, i.e. of order-isomorphisms), while Galois connections weaken the concept of an equivalence of categories between poset-categories -- it just happens that both these isomorphisms and the categorical equivalences agree in our special setting.