Sajun.org
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 wihtout 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 isomporphisms 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.
