Residuated Boolean algebra
Encyclopedia
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 algebra
s as a finitely axiomatized generalization of the binary relation example, but there exist interesting examples of residuated Boolean algebras that are not relation algebras, such as the language example.
An equivalent signature better suited to the relation algebra
application is (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) where the unary operations x\ and x▷ are intertranslatable in the manner of De Morgan's laws via
with the residuation axioms in the residuated lattice
article reorganized accordingly (replacing z by ¬z) to read∧y = 0 ⇔ (x•y)∧z = 0 ⇔ (z◁y)∧x = 0
This De Morgan dual reformulation is motivated and 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
.
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
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 ¬f(¬y), analogous to ∀xφ(x) = ¬∃x¬φ(x). 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.
With this signature it remains the case that this axiomatization can be expressed as finitely many equations.
= x. This is impossible for the latter because x▷I retains hardly any information about x. Hence in example 2 we can substitute x for x in x▷I = x = I◁x and cancel (soundly) to give
x
= x can be proved from these two equations. Tarski
's notion of a relation algebra
can be defined as a residuated Boolean algebra having an operation x satisfying these two equations.
The cancellation step in the above is not possible for example 3, which therefore is not a relation algebra, x being uniquely determined as x▷I.
Consequences of this axiomatization of converse include x
= x, ¬(x
) = (¬x)
, (x∨y) = x∨y, and (x•y) = y•x.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a residuated Boolean algebra is a residuated lattice
Residuated lattice
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...
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 algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
s as a finitely axiomatized generalization of the binary relation example, but there exist interesting examples of residuated Boolean algebras that are not relation algebras, such as the language example.
Definition
A residuated Boolean algebra is an algebraic structure (L, ∧, ∨, ¬, 0, 1, •, I, \, /) such that- (i) (L, ∧, ∨, •, I, \, /) is a residuated latticeResiduated latticeIn 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...
, and (L, ∧, ∨, ¬, 0, 1) is a Boolean algebra.
An equivalent signature better suited to the relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
application is (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) where the unary operations x\ and x▷ are intertranslatable in the manner of De Morgan's laws via
- x\y = ¬(x▷¬y), x▷y = ¬(x\¬y), and dually /y and ◁y as
- x/y = ¬(¬x◁y), x◁y = ¬(¬x/y),
with the residuation axioms in the residuated lattice
Residuated lattice
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...
article reorganized accordingly (replacing z by ¬z) to read∧y = 0 ⇔ (x•y)∧z = 0 ⇔ (z◁y)∧x = 0
This De Morgan dual reformulation is motivated and 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
Variety (universal algebra)
In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
.
Examples
- 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.
- 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.
- 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.
Conjugacy
The De Morgan duals ▷ and ◁ of residuation arise as follows. 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 ¬f(¬y), analogous to ∀xφ(x) = ¬∃x¬φ(x). 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.
- y # x▷z ⇔ x•y # z ⇔ x # z◁y
With this signature it remains the case that this axiomatization can be expressed as finitely many equations.
Converse
In examples 2 and 3 it can be shown that x▷I = I◁x. In example 2 both sides equal the converse x of x, while in example 3 both sides are I when x contains the empty word and 0 otherwise. In the former case x = x. This is impossible for the latter because x▷I retains hardly any information about x. Hence in example 2 we can substitute x for x in x▷I = x = I◁x and cancel (soundly) to give
- x▷I = x = I◁x.
x
= x can be proved from these two equations. TarskiAlfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
's notion of a relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
can be defined as a residuated Boolean algebra having an operation x satisfying these two equations.
The cancellation step in the above is not possible for example 3, which therefore is not a relation algebra, x being uniquely determined as x▷I.
Consequences of this axiomatization of converse include x
= x, ¬(x) = (¬x), (x∨y) = x∨y, and (x•y) = y•x.