Order-embedding

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.

Contents

Formal definition

Formally, given two partially ordered sets (S, ≤) and (T, ≤), a function f: ST 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)\leq f(y).

Note that such a function is necessarily injective, since f(x) = f(y) implies xy and yx. 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

e(x) = \frac{2}{\pi}\arctan x

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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Order theory — For a topical guide to this subject, see Outline of order theory. Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as… …   Wikipedia

  • Embedding — In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.When some object X is said to be embedded in another object Y , the embedding is… …   Wikipedia

  • embedding — n. (in microscopy) the fixing of a specimen within a mass of firm material in order to facilitate the cutting of thin sections for microscopical study. The embedding medium, e.g. paraffin wax for light microscopy or Araldite for electron… …   Medical dictionary

  • List of order theory topics — Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is less than or precedes another. An alphabetical list of many… …   Wikipedia

  • Order (ring theory) — In mathematics, an order in the sense of ring theory is a subring of a ring R that satisfies the conditions R is a ring which is a finite dimensional algebra over the rational number field spans R over , so that …   Wikipedia

  • embedding — Tissue is embedded in wax or plastic in order to prepare sections for microscopical examination. The embedding medium provides mechanical support …   Dictionary of molecular biology

  • embedding — n. (in microscopy) the fixing of a specimen within a mass of firm material in order to facilitate the cutting of thin sections for microscopical study. The embedding medium, e.g. paraffin wax for light microscopy or Araldite for electron… …   The new mediacal dictionary

  • Glossary of order theory — This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be …   Wikipedia

  • List of order topics — This is a list of order topics, by Wikipedia page.An alphabetical list of many notions of order theory can be found in the order theory glossary. See also inequality, extreme value, optimization (mathematics), domain theory.Basic… …   Wikipedia

  • Cyclic order — In mathematics, a cyclic order is a way to arrange a set of objects in a circle.[nb] Unlike most structures in order theory, a cyclic order cannot be modeled as a binary relation a < b . One does not say that east is more clockwise than west.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”