Examples
- The ceiling function from R to Z (with the usual order in each case) is residuated, with residual mapping the natural embedding of Z into R.
- The embedding of Z into R is also residuated. Its residual is the floor function .
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function.
If A, B are posets, a function f: A → B is defined to be monotone if it is order-preserving: that is, if x ≤ y implies f(x) ≤ f(y). This is equivalent to the condition that the preimage under f of every down-set of B is a down-set of A. We define a principal down-set to be one of the form ↓{b} = { b' ∈ B : b' ≤ b }. In general the preimage under f of a principal down-set need not be a principal down-set. If all of them are, f is called residuated.
The notion of residuated map can be generalized to a binary operator (or any higher arity) via component-wise residuation. This approach gives rise to notions of left and right division in a partially ordered magma, additionally endowing it with a quasigroup structure. (One speaks only of residuated algebra for higher arities). A binary (or higher arity) residuated map is usually not residuated as a unary map. [1]
If A, B are posets, a function f: A → B is residuated if and only if the preimage under f of every principal down-set of B is a principal down-set of A.
If B is a poset, the set of functions A → B can be ordered by the pointwise order f ≤ g ↔ (∀x ∈ A) f(x) ≤ g(x).
It can be shown that a monotone function f is residuated if and only if there exists a (necessarily unique) monotone function f +: B → A such that f o f + ≤ idB and f + o f ≥ idA, where id is the identity function. The function f + is the residual of f. A residuated function and its residual form a Galois connection under the (more recent) monotone definition of that concept, and for every (monotone) Galois connection the lower adjoint is residuated with the residual being the upper adjoint. [2] Therefore, the notions of monotone Galois connection and residuated mapping essentially coincide.
Additionally, we have f -1(↓{b}) = ↓{f +(b)}.
If B° denotes the dual order (opposite poset) to B then f : A → B is a residuated mapping if and only if there exists an f * such that f : A → B° and f *: B° → A form a Galois connection under the original antitone definition of this notion.
If f : A → B and g : B → C are residuated mappings, then so is the function composition gf : A → C, with residual (gf) + = f +g +. The antitone Galois connections do not share this property.
The set of monotone transformations (functions) over a poset is an ordered monoid with the pointwise order, and so is the set of residuated transformations. [3]
If • : P × Q → R is a binary map and P, Q, and R are posets, then one may define residuation component-wise for the left and right translations, i.e. multiplication by a fixed element. For an element x in P define xλ(y) = x • y, and for x in Q define λx(y) = y • x. Then • is said to be residuated if and only if xλ and λx are residuated for all x (in P and respectively Q). Left (and respectively right) division are defined by taking the residuals of the left (and respectively right) translations: x\y = (xλ)+(y) and x/y = (λx)+(y)
For example, every ordered group is residuated, and the division defined by the above coincides with notion of division in a group. A less trivial example is the set Matn(B) of square matrices over a boolean algebra B, where the matrices are ordered pointwise. The pointwise order endows Matn(B) with pointwise meets, joins and complements. Matrix multiplication is defined in the usual manner with the "product" being a meet, and the "sum" a join. It can be shown [4] that X\Y = (Y tX′)′ and X/Y = (X′Y t)′, where X ′ is the complement of X, and Yt is the transposed matrix).
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.
In the mathematical field of order theory, an ultrafilter on a given partially ordered set is a certain subset of namely a maximal filter on that is, a proper filter on that cannot be enlarged to a bigger proper filter on
In mathematics, and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable. This is in direct analogy to the definition that a continuous function between topological spaces preserves the topological structure: the preimage of any open set is open. In real analysis, measurable functions are used in the definition of the Lebesgue integral. In probability theory, a measurable function on a probability space is known as a random variable.
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice that satisfies at least one of these properties is known as a conditionally complete lattice. For comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.
In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.
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.
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 the following overview articles:
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.
In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets
In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.
In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.
In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory.
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames. Although these three categories contain the same objects, they differ in their morphisms, and thus get distinct names. Only the morphisms of CHey are homomorphisms of complete Heyting algebras.
In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
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.
In mathematics, a t-norm is a kind of binary operation used in the framework of probabilistic metric spaces and in multi-valued logic, specifically in fuzzy logic. A t-norm generalizes intersection in a lattice and conjunction in logic. The name triangular norm refers to the fact that in the framework of probabilistic metric spaces t-norms are used to generalize the triangle inequality of ordinary metric spaces.
In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice x ≤ y and a monoid x•y which admits operations x\z and z/y, loosely analogous to division or implication, when x•y is viewed as multiplication or conjunction, respectively. Called respectively right and left residuals, these operations coincide when the monoid is commutative. The general concept was introduced by Morgan Ward and Robert P. Dilworth in 1939. Examples, some of which existed prior to the general concept, include Boolean algebras, Heyting algebras, residuated Boolean algebras, relation algebras, and MV-algebras. Residuated semilattices omit the meet operation ∧, for example Kleene algebras and action algebras.
In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value of some function An important class of pointwise concepts are the pointwise operations, that is, operations defined on functions by applying the operations to function values separately for each point in the domain of definition. Important relations can also be defined pointwise.
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.
