Residuated Boolean Algebra - Examples

Examples

1. Any Boolean algebra, with the monoid multiplication • taken to be conjunction and both residuals taken to be material implication x→y. Of the remaining 15 binary Boolean operations that might be considered in place of conjunction for the monoid multiplication, only five meet the monotonicity requirement, namely 0, 1, x, y, and x∨y. Setting y = z = 0 in the residuation axiom y ≤ x\z ⇔ x•y ≤ z, we have 0 ≤ x\0 ⇔ x•0 ≤ 0, which is falsified by taking x = 1 when x•y = 1, x, or x∨y. The dual argument for z/y rules out x•y = y. This just leaves x•y = 0 (a constant binary operation independent of x and y), which satisfies almost all the axioms when the residuals are both taken to be the constant operation x/y = x\y = 1. The axiom it fails is x•I = x = I•x, for want of a suitable value for I. Hence conjunction is the only binary Boolean operation making the monoid multiplication that of a residuated Boolean algebra.
2. The power set 2X² made a Boolean algebra as usual with ∩, ∪ and complement relative to X², and made a monoid with relational composition. The monoid unit I is the identity relation {(x,x)|x ∈ X}. The right residual R\S is defined by x(R\S)y if and only if for all z in X, zRx implies zSy. Dually the left residual S/R is defined by y(S/R)x if and only if for all z in X, xRz implies ySz.
3. The power set 2Σ* made a Boolean algebra as for example 2, but with language concatenation for the monoid. Here the set Σ is used as an alphabet while Σ* denotes the set of all finite (including empty) words over that alphabet. The concatenation LM of languages L and M consists of all words uv such that u ∈ L and v ∈ M. The monoid unit is the language {ε} consisting of just the empty word ε. 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.