Order-embedding
Encyclopedia
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 connection
s, 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.
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.
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 number
s 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
This is in fact just the projection of the real number line to (half of) the circle with circumference 4 (see trigonometric function
s 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.
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 connection
s 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.
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 "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, an order-embedding is a special kind of monotone function, which provides a way to include one partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
into another. Like Galois connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
s, order-embeddings constitute a notion which is strictly weaker than the concept of an order isomorphism
Order isomorphism
In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
. A way to understand the different nature of both of these weakenings by exploiting some category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
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
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 domainDomain (mathematics)
In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
S and its range
Range (mathematics)
In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...
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 number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s and its interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
[−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
This is in fact just the projection of the real number line to (half of) the circle with circumference 4 (see trigonometric function
Trigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...
s 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
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, which are not present in the case of the real numbers. This shows that an isomorphism cannot exist.
Categorically speaking
The basic categoryCategory theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
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
Domain (mathematics)
In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
correspond exactly to the sections in the category of posets. Remember that a section s is just a morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
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 connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
s 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
Isomorphism of categories
In category theory, two categories C and D are isomorphic if there exist functors F : C → D and G : D → C which are mutually inverse to each other, i.e. FG = 1D and GF = 1C. This means that both the objects and the morphisms of C and D stand in a one to one correspondence to each other...
, i.e. of order-isomorphisms), while Galois connections weaken the concept of an equivalence of categories
Equivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
between poset-categories -- it just happens that both these isomorphisms and the categorical equivalences agree in our special setting.