Residuated Boolean algebra

In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary relations on a given set X under relational composition, and more generally the power set of any equivalence relation, again under relational composition. The original application was to relation algebras as a finitely axiomatized generalization of the binary relation example.

Definition

A residuated Boolean algebra is an algebraic structure (L, ∧, ∨, ¬, 0, 1, •, I, \, /) such that (L, ∧, ∨, •, I, \, /) is a residuated lattice and (L, ∧, ∨, ¬, 0, 1) is a Boolean algebra. An equivalent signature is (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) where \ and ▷ are intertranslatable via x\y = ¬(x▷¬y), x▷y = ¬(x\¬y), and dually x/y = ¬(¬x◁y), x◁y = ¬(¬x/y), discussed in more detail in the section below on conjugacy.

Since residuated lattices and Boolean algebras are each definable with finitely many equations, so are residuated Boolean algebras, whence they form a finitely axiomatizable variety.

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 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 the axioms when the residuals are both taken to be the constant operation x/y = x\y = 1.

2. The power set 2^X² 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. 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.

Conjugacy

Among residuated lattices, Boolean algebras are special by virtue of having a complementation operation ¬. This permits an alternative expression of the three inequalities

y ≤ x\z   ⇔   x•y ≤ z   ⇔   x ≤ z/y

in the axiomatization of the two residuals in terms of disjointness, via the equivalence x ≤ y ⇔ x∧¬y = 0. Abbreviating x∧y = 0 to x # y as the expression of their disjointness, and substituting ¬z for z in the axioms, they become with a little Boolean manipulation

¬(x\¬z) # y   ⇔   x•y # z   ⇔   ¬(¬z/y) # x

Now ¬(x\¬z) is reminiscent of De Morgan duality, suggesting that x\ be thought of as a unary operation f, defined by f(y) = x\y, that has a De Morgan dual. Denoting this dual operation as x▷, we define x▷z as ¬(x\¬z). Similarly we define another operation z◁y as ¬(¬z/y). By analogy with x\ as the residual operation associated with the operation x•, we refer to x▷ as the conjugate operation, or simply conjugate, of x•. Likewise ◁y is the conjugate of •y. Unlike residuals, conjugacy is an equivalence relation between operations: if f is the conjugate of g then g is also the conjugate of f, i.e. the conjugate of the conjugate of f is f. Another advantage of conjugacy is that it becomes unnecessary to speak of right and left conjugates, that distinction now being inherited from the difference between x• and •x, which have as their respective conjugates x▷ and ◁x. (But this advantage accrues also to residuals when x\ is taken to be the residual operation to x•.)

All this yields (along with the Boolean algebra and monoid axioms) the following equivalent axiomatization of a residuated Boolean algebra.

x▷z # y   ⇔   x•y # z   ⇔   z◁y # x

Converse

In examples 2 and 3 it can be shown that x▷I = I◁x. In example 2 both sides equal the converse x^{${\breve {}}$} of x, while in example 3 both sides are I when x contains the empty word and 0 otherwise. In the former case x^{${\breve {\ }}{\breve {\ }}$} = x, clearly false for the latter. Hence we can substitute x^{${\breve {}}$} for x in x▷I = x^{${\breve {}}$} = I◁x and cancel to give

x^{${\breve {}}$}▷I = x = I◁x^{${\breve {}}$}

as holding in example 2 but not 3. x^{${\breve {\ }}{\breve {\ }}$} = x can be proved from these. Tarski's notion of a relation algebra is defined as a residuated Boolean algebra having an operation x^{${\breve {}}$} satisfying the above two equations.

The residuals can be treated not as operations in the signature but merely as abbreviations, namely y\x for ¬(ў•¬x) and x/y for ¬(¬x•ў). The signature of relation algebras can then be taken to be that of residuated Boolean algebras with the binary residual operations replaced (since they are now just shorthand) by the unary converse operation, namely (L, ∧, ∨, ¬, 0, 1, •, I, ${\breve {}}$).

Consequences of this axiomatization of converse include x^{${\breve {\ }}{\breve {\ }}$} = x, (x∨y)^{${\breve {}}$} = x^{${\breve {}}$}∨y^{${\breve {}}$}, and (x•y)^{${\breve {}}$} = y^{${\breve {}}$}•x^{${\breve {}}$}.

In the case of the residuated Boolean algebra of all languages over the alphabet Σ, we can define the converse of a language L by analogy with the above. However the result is either I = {ε} or the empty language 0 = ∅ depending on whether or not L contains the empty word. Since this result retains almost no information about L it cannot satisfy L^{${\breve {\ }}{\breve {\ }}$} = L, whence this residuated Boolean algebra is not a relation algebra.

References

• Morgan Ward and R.P. Dilworth, Residuated lattices, Trans. Amer. Math. Soc., 45 (1939) 335-354.
• Petr Hájek, Metamathematics of Fuzzy Logic. Kluwer, Dordrecht, 1998.
• Bjarni Jónsson and Constantine Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis, 30 (1993) 469-478.