Residuated Lattice - Examples

Examples

One of the original motivations for the study of residuated lattices was the lattice of 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

It is worth noting that {0}/B and B\{0} are respectively the left and right annihilators of B. This residuation is related to the conductor (or transporter) in commutative algebra written as (A:B)=A/B. One difference in usage is that B need not be an ideal of R: it may just be a subset.

Boolean algebras and Heyting algebras are commutative residuated lattices in which x•y = x∧y (whence the unit I is the top element 1 of the algebra) and both residuals x\y and y/x are the same operation, namely implication x → y. The second example is quite general since Heyting algebras include all finite distributive lattices, as well as all chains or total orders forming a complete lattice, for example the unit interval in the real line, or the integers and ±.

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 x ≤ y 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.

This can be illustrated with the binary relations < and > on {0,1} in which 0 < 1 and 1 > 0 are the only relationships that hold. Then x(>\<)y holds just when x = 1, while x()y holds just when y = 0, showing that residuation of < by > is different depending on whether we residuate on the right or the left. This difference is a consequence of the difference between <•> and >•<, where the only relationships that hold are 0(<•>)0 (since 0<1>0) and 1(>•<)1 (since 1>0<1). Had we chosen ≤ and ≥ instead of < and >, ≥\≤ and ≤/≥ would have been the same because ≤•≥ = ≥•≤, both of which always hold between all x and y (since x≤1≥y and x≥0≤y).

The Boolean algebra 2Σ* of all formal languages over an alphabet (set) Σ forms a residuated lattice whose monoid multiplication is language concatenation LM and whose monoid unit I is the language {ε} consisting of just the empty string ε. The right residual M\L consists of all words w over Σ such that Mw ⊆ L. The left residual L/M is the same with wM in place of Mw.

The residuated lattice of all binary relations on X is finite just when X is finite, and commutative just when X has at most one element. When X is empty the algebra is the degenerate Boolean algebra in which 0 = 1 = I. The residuated lattice of all languages on Σ is commutative just when Σ has at most one letter. It is finite just when Σ is empty, consisting of the two languages 0 (the empty language {}) and the monoid unit I = {ε} = 1.

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 x•y ≤ z as "bet and then win entails rich." By the axioms this is equivalent to y ≤ x→z meaning "win entails had bet then rich", and also to x ≤ z←y 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." Humans do not so readily detect that Peirce's law ((P→Q)→P)→P is a tautology, giving an interesting situation where humans exhibit more proficiency with nonclassical reasoning than classical.