Order embedding
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 category theory.
Formal definition
Formally, given two partially ordered sets (posets)
Such a function is necessarily injective, since
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 image f(S), which justifies the term "embedding".[1] 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
A retract is a pair
Additional Perspectives
Posets can straightforwardly be viewed from many perspectives, and order embeddings are basic enough that they tend to be visible from everywhere. For example:
- (Model theoretically) A poset is a set equipped with a (reflexive, antisymmetric and transitive) binary relation. An order embedding A → B is an isomorphism from A to an elementary substructure of B.
- (Graph theoretically) A poset is a (transitive, acyclic, directed, reflexive) graph. An order embedding A → B is a graph isomorphism from A to an induced subgraph of B.
- (Category theoretically) A poset is a (small, thin, and skeletal) category such that each homset has at most one element. An order embedding A → B is a full and faithful functor from A to B which is injective on objects, or equivalently an isomorphism from A to a full subcategory of B.
See also
References
- ↑ Jump up to: 1.0 1.1 1.2 Davey, B. A.; Priestley, H. A. (2002), "Maps between ordered sets", Introduction to Lattices and Order (2nd ed.), New York: Cambridge University Press, pp. 23–24, ISBN 0-521-78451-4, https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA23.
- ↑ Just, Winfried; Weese, Martin (1996), Discovering Modern Set Theory: The basics, Fields Institute Monographs, 8, American Mathematical Society, p. 21, ISBN 9780821872475, https://books.google.com/books?id=TPvHr7fcvHoC&pg=PA21
- ↑ Duffus, Dwight; Laflamme, Claude; Pouzet, Maurice (2008), "Retracts of posets: the chain-gap property and the selection property are independent", Algebra Universalis 59 (1–2): 243–255, doi:10.1007/s00012-008-2125-6.
![]() | Original source: https://en.wikipedia.org/wiki/Order embedding.
Read more |