Boolean algebra

If we take the equations that are true in the the calculus of classes and replace the symbols using the following table

then we have the equations of Boolean algebra. Before 1900 Boolean algebra really meant the juggling of equations (and neg-equations) to reflect valid arguments. In 1904 E.V. Huntington wrote a paper [1] in which he viewed Boolean algebras as algebraic structures satisfying the equations obtained from the calculus of classes. This viewpoint became dominant in the 1920's under the influence of M.H. Stone and A. Tarski. Stone was initially interested in Boolean algebras in order to gain insight into the structure of rings of functions which were being investigated in functional analysis. He wrote two massive papers, one on the equivalence of Boolean algebras and Boolean rings, and the other on the duality between Boolean algebras and Boolean spaces [= totally disconnected compact Hausdorff spaces]. Tarski studied Boolean algebras while working on the abstract notion of `closure under deductive consequence'. In the 1930's Stone proved that every Boolean algebra is isomorphic to a field of sets, and that the equations true of the two-element Boolean algebra are the same as the equations true of all Boolean algebras; and these equations were consequences of a small initial set of defining equations.

What has the modern subject of Boolean algebra got to do with propositional logic? Not very much. Boolean algebra became a deep and fascinating subject in its own right, with much more to offer than a convenient notation to analyze simple chains of reasoning. Nonetheless on the level of equivalence and equations the subjects of propositional logic, calculus of classes, and Boolean algebras are essentially the same, as illustrated by the following table:

In the second half of the 1800's these identities were considered pretty exciting, and most of them were named after prominent logicians -- now only the two attributed to DeMorgan still have such a name attached.

One can take the identities in the third column as a set of axioms for Boolean algebra, but this set of axioms is somewhat redundant. Huntington was quite fascinated with the problem of finding sets of axioms for the Calculus of Classes. There is a variation of a set of axioms that he proposed (see [2]), due to Herbert Robbins in 1933, that only recently has been proved to also define Boolean algebras (see III.16 of LMCS), namely:

• 
• 
• 

Since this problem was so difficult one can pose the fundamental question:

Given a finite set of identities in the language of Boolean algebras, is there an algorithm to determine if defines precisely the class of Boolean algebras?

Certainly one can determine if an identity is true in all Boolean algebras -- just check it out on the two-element Boolean algebra. So this reduces the question to:

Given a finite set of identities which are true of Boolean algebras, is there an algorithm to determine if defines precisely the class of Boolean algebras?

As mentioned in II.14.10 of LMCS, a similar question for propositional logic had been proved to be undecidable. The above question was answered in the negative by McNulty [3] and Murskii [4].

EXERCISES

References

1

E.V. Huntington, Sets of independent postulates for the algebra of logic. Trans. AMS 5 (1904), 288-309.

2

E.V. Huntington, New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia Mathematica. Trans. AMS 35 (1933), 274-304.

3

G. McNulty, The decision problem for equational bases of algebras. Annals Math. Logic 11 (1976), 193-259.

4

V.L. Murskii, Non-discernible properties of finite systems of identity relations. Soviet Math. Doklady 12 (1971), 183-186. Annals Math. Logic 11 (1976), 193-259.

5

M.H. Stone, The theory of representation for Boolean algebras. Trans. AMS 40, 27-111.

6

M.H. Stone, Application of the theory of Boolean rings to general topology. Trans. AMS 41, 375-481.

7

A. Tarski, Fundamentale Begriffe der methodologie der deduktiven Wissenschafter. I. Monatsh. Math. Phys. 37, 360-404