                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

1 Boolean algebra

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

calculus of classes Boolean algebra
0  0
1  1
′  ′
∪  ∨
∩  ∧

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.^{1} 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:

1Certainly Boole only worked with equations, as mentioned before.

propositional logic  calculus of classes  Boolean algebra
1.  φ ∨ φ ∼ φ  X ∪ X ≈ X  x ∨ x ≈ x
2.  φ ∧ φ ∼ φ  X ∩ X ≈ X  x ∧ x ≈ x
3.  φ ∨ ψ ∼ ψ ∨ φ  X ∪ Y ≈ Y ∪ X  x ∨ y ≈ y ∨ x
4.  φ ∧ ψ ∼ ψ ∧ φ  X ∩ Y ≈ Y ∩ X  x ∧ y ≈ y ∧ x
5.  φ ∨ (ψ ∨ χ) ∼ (φ ∨ ψ) ∨ χ  X ∪ (Y ∪ Z) ≈ (X ∪ Y) ∪ Z  x ∨ (y ∨ z) ≈ (x ∨ y) ∨ z
6.  φ ∧ (ψ ∧ χ) ∼ (φ ∧ ψ) ∧ χ  X ∩ (Y ∩ Z) ≈ (X ∩ Y) ∩ Z  x ∧ (y ∧ z) ≈ (x ∧ y) ∧ z
7.  φ ∨ (φ ∧ ψ) ∼ φ  X ∪ (X ∩ Y) ≈ X  x ∨ (x ∧ y) ≈ x
8.  φ ∧ (φ ∨ ψ) ∼ φ  X ∩ (X ∪ Y) ≈ X  x ∧ (x ∨ y) ≈ x
9.  φ ∨ (ψ ∧ χ) ∼ (φ ∨ ψ) ∧ (φ ∨ χ) X ∪ (Y ∩ Z) ≈ (X ∪ Y) ∩ (X ∪ Z) x ∨ (y ∧ z) ≈ (x ∨ y) ∧ (x ∨ z)
10. φ ∧ (ψ ∨ χ) ∼ (φ ∧ ψ) ∨ (φ ∧ χ) X ∩ (Y ∪ Z) ≈ (X ∩ Y) ∪ (X ∩ Z) x ∧ (y ∧ z) ≈ (x ∧ y) ∨ (x ∧ z)
11. φ ∨ ¬φ ∼ 1  X ∪ X′ ≈ 1  x ∨ x′ ≈ 1
12. φ ∧ ¬φ ∼ 0  X ∩ X′ ≈ 0  x ∧ x′ ≈ 0
13. ¬¬φ ∼ φ  X′′ ≈ X  x′′ ≈ x
14. φ ∨ 1 ∼ 1  X ∪ 1 ≈ 1  x ∨ 1 ≈ 1
15. φ ∧ 0 ∼ 0  X ∩ Ø ≈ Ø  x ∧ 0 ≈ 0
16. ¬(φ ∨ ψ) ∼ ¬φ ∧ ¬ψ  (X ∪ Y)′ ≈ X′ ∩ Y′  (x ∨ y)′ ≈ x′ ∧ y′
17. ¬(φ ∧ ψ) ∼ ¬φ ∨ ¬ψ  (X ∩ Y)′ ≈ X′ ∪ Y′  (x ∧ y)′ ≈ x′ ∨ y′

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:

• x ∨ y ≈ y ∨ x

• x ∨ (y ∨ z) ≈ (x ∨ y) ∨ z

• ((x ∨ y)′ ∨ (x ∨ y′)′)′ ≈ x.

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 Murskiĭ [4].

Exercises Problem 1 [Stone] One of the important occurrences of Boolean algebras in traditional mathematical structures concerns rings.

(a) If B, ∨, ∧,′ , 0, 1 is a Boolean algebra, define x + y as (x ∧ y′) ∨ (x′ ∧ y) (the symmetric difference) x × y as x ∧ y. Show that B, +, ×, 0, 1 is a Boolean ring (i.e., a ring satisfying x^{2} ≈ x).

(b) If R, +, ×, 0, 1 is a Boolean ring, define x ∨ y as x + y + xy x ∧ y as xy x′ as 1 − x. Show that R, ∨, ∧,′ , 0, 1 is a Boolean algebra.

(c) Show that the two transformations above are inverses.

Problem 2 [Boolean algebra of central idempotents] If R, +, ×, 0, 1 is a ring, let E be the subset of central idempotents (i.e., a ∈ E iff a^{2} ≈ a and ax ≈ xa for x ∈ R). Define new operations on E by x ∨ y is x + y − xy x ∧ y is xy x′ is 1 − x.

(a) Show that E, ∨, ∧,′ , 0, 1 is a Boolean algebra.

(b) Consider the Boolean ring associated with this Boolean algebra. Are the operations the same as those of R, restricted to E?

Problem 3 [Proof translation] Show that you can efficiently translate a proof in Frege/Łukasiewicz calculus into an equational proof in Boolean algebra, where a propositional formula φ is to be translated as φ ≈ 1.

Problem 4 ⋆ [Boolean Prime Ideal Theorem] This is the famous result (part (a)) which leads to the structure theorem for Boolean rings and Boolean algebras. Let R be a Boolean ring.

(a) Show that if a ≠ 0 then there is a prime ideal I such that a ∉ I.

(b) If I is a prime ideal of R show that R/I is a two-element ring.

(c) Show that if R is nontrivial then it can be embedded in a product of copies of GF(2).

(d) Show that every nontrivial Boolean algebra can be embedded in a product of two-element Boolean algebras, and hence is isomorphic to a Boolean algebra of sets with the natural operations ∪, ∩,′ , Ø, U. Such a Boolean algebra is called a field of sets.

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. Murskiĭ, 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