Residuated lattice

In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice xy and a monoid xy which admits operations x\z and z/y, loosely analogous to division or implication, when xy 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, a residuated lattice is an algebraic structure L = (L, ≤, •, I) such that

In (iii), the "greatest y", being a function of z and x, is denoted x\z and called the right residual of z by x. Think of it as what remains of z on the right after "dividing" z on the left by x. Dually, the "greatest x" is denoted z/y and called the left residual of z by y. An equivalent, more formal statement of (iii) that uses these operations to name these greatest values is

As suggested by the notation, the residuals are a form of quotient. More precisely, for a given x in L, the unary operations x• and x\ are respectively the lower and upper adjoints of a Galois connection on L, and dually for the two functions •y and /y. By the same reasoning that applies to any Galois connection, we have yet another definition of the residuals, namely,

together with the requirement that xy be monotone in x and y. (When axiomatized using (iii) or (iii)' monotonicity becomes a theorem and hence not required in the axiomatization.) These give a sense in which the functions x• and x\ are pseudoinverses or adjoints of each other, and likewise for •x and /x.

This last definition is purely in terms of inequalities, noting that monotonicity can be axiomatized as xy ≤ (xz)•y and similarly for the other operations and their arguments. Moreover, any inequality xy can be expressed equivalently as an equation, either xy = x or xy = y. This along with the equations axiomatizing lattices and monoids then yields a purely equational definition of residuated lattices, provided the requisite operations are adjoined to the signature (L, ≤, •, I) thereby expanding it to (L, ∧, ∨, •, I, /, \). When thus organized, residuated lattices form an equational class or variety, whose homomorphisms respect the residuals as well as the lattice and monoid operations. Note that distributivity x•(yz) = (xy) ∨ (xz) and x•0 = 0 are consequences of these axioms and so do not need to be made part of the definition. This necessary distributivity of • over ∨ does not in general entail distributivity of ∧ over ∨, that is, a residuated lattice need not be a distributive lattice. However distributivity of ∧ over ∨ is entailed when • and ∧ are the same operation, a special case of residuated lattices called a Heyting algebra.

Alternative notations for xy include xy, x;y (relation algebra), and xy (linear logic). Alternatives for I include e and 1'. Alternative notations for the residuals are xy for x\y and yx for y/x, suggested by the similarity between residuation and implication in logic, with the multiplication of the monoid understood as a form of conjunction that need not be commutative. When the monoid is commutative the two residuals coincide. When not commutative, the intuitive meaning of the monoid as conjunction and the residuals as implications can be understood as having a temporal quality: xy means x and then y,   xy means had x (in the past) then y (now),   and yx means if-ever x (in the future) then y (at that time), as illustrated by the natural language example at the end of the examples.

One of the original motivations for the study of residuated lattices was the lattice of (two-sided) ideals of a ring. Given a ring R, the ideals of R, denoted Id(R), forms a complete lattice with set intersection acting as the meet operation and "ideal addition" acting as the join operation. The monoid operation • is given by "ideal multiplication", and the element R of Id(R) acts as the identity for this operation. Given two ideals A and B in Id(R), the residuals are given by

The structure (Z, min, max, +, 0, −, −) (the integers with subtraction for both residuals) is a commutative residuated lattice such that the unit of the monoid is not the greatest element (indeed there is no least or greatest integer), and the multiplication of the monoid is not the meet operation of the lattice. In this example the inequalities are equalities because − (subtraction) is not merely the adjoint or pseudoinverse of + but the true inverse. Any totally ordered group under addition such as the rationals or the reals can be substituted for the integers in this example. The nonnegative portion of any of these examples is an example provided min and max are interchanged and − is replaced by monus, defined (in this case) so that x-y = 0 when xy and otherwise is ordinary subtraction.

A more general class of examples is given by the Boolean algebra of all binary relations on a set X, namely the power set of X2, made a residuated lattice by taking the monoid multiplication • to be composition of relations and the monoid unit to be the identity relation I on X consisting of all pairs (x,x) for x in X. Given two relations R and S on X, the right residual R\S of S by R is the binary relation such that x(R\S)y holds just when for all z in X, zRx implies zSy (notice the connection with implication). The left residual is the mirror image of this: y(S/R)x holds just when for all z in X, xRz implies ySz.

The examples forming a Boolean algebra have special properties treated in the article on residuated Boolean algebras.

In natural language residuated lattices formalize the logic of "and" when used with its noncommutative meaning of "and then." Setting x = bet, y = win, z = rich, we can read xyz as "bet and then win entails rich." By the axioms this is equivalent to yxz meaning "win entails had bet then rich", and also to xzy meaning "bet entails if-ever win then rich." Humans readily detect such non-sequiturs as "bet entails had win then rich" and "win entails if-ever bet then rich" as both being equivalent to the wishful thinking "win and then bet entails rich."[citation needed] Humans do not so readily detect that Peirce's law ((PQ)→P)→P is a classical tautology, an interesting situation where humans exhibit more proficiency with non-classical reasoning than classical (for example, in relevance logic, Peirce's law is not a tautology).[relevance questioned]

A residuated semilattice is defined almost identically for residuated lattices, omitting just the meet operation ∧. Thus it is an algebraic structure L = (L, ∨, •, 1, /, \) satisfying all the residuated lattice equations as specified above except those containing an occurrence of the symbol ∧. The option of defining xy as xy = x is then not available, leaving only the other option xy = y (or any equivalent thereof).

Any residuated lattice can be made a residuated semilattice simply by omitting ∧. Residuated semilattices arise in connection with action algebras, which are residuated semilattices that are also Kleene algebras, for which ∧ is ordinarily not required.