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 . 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 .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (3)

Related people (1)

Related concepts (4)

Related lectures (6)

Beating the I/O Bottleneck: A Case for Log-Structured Virtual Disks

Vojtech Aschenbrenner

With the increasing dominance of SSDs for local storage, today's network mounted virtual disks can no longer offer competitive performance. We propose a Log-Structured Virtual Disk (LSVD) that couples log-structured approaches at both the cache and storage ...

ASSOC COMPUTING MACHINERY2022

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...

EPFL2012

Hanani-Tutte and Monotone Drawings

Radoslav Fulek

A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Toth showed that if a graph has an x-monotone drawing in which every pair of edges crosses an even nu ...

Springer-Verlag Berlin2011

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 (posets). Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that either of the orders can be obtained from the other just by renaming of elements. Two strictly weaker notions that relate to order isomorphisms are order embeddings and Galois connections.

Monotonic function

In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory. In calculus, a function defined on a subset of the real numbers with real values is called monotonic if and only if it is either entirely non-increasing, or entirely non-decreasing. That is, as per Fig. 1, a function that increases monotonically does not exclusively have to increase, it simply must not decrease.

Order theory

Order theory is a branch of mathematics that investigates the 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 provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.

Quasi-Categories: Active Learning Session MATH-436: Homotopical algebra

Covers fibrant objects, lift of horns, and the adjunction between quasi-categories and Kan complexes, as well as the generalization of categories and Kan complexes.

Structural Mechanics Principles: Equilibrium and Stability

Explores the principles of structural mechanics, including internal loads, equilibrium stability, and the superposition principle.

Laser Systems: Rate Equations MICRO-426: Laser fundamentals and applications for engineers

Explores rate equations in laser systems, semiconductor lasers, beam quality, and applications.