Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Order embedding
Résumé
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 .
Formally, given two partially ordered sets (posets) and , a function is an order embedding if is both order-preserving and order-reflecting, i.e. for all and in , one has
Such a function is necessarily injective, since implies and . If an order embedding between two posets and exists, one says that can be embedded into .
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 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 of real numbers and the corresponding closed interval . The function maps the former to the subset of the latter and the latter to the subset of the former, see picture. Ordering both sets in the natural way, 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. has a least element while 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 of order-preserving maps whose composition is the identity. In this case, 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 from the empty poset to a nonempty poset has no retract, because there is no order-preserving map .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.