Two-element boolean algebra generates the class of boolean algebras

822 Views Asked by At

I've heard that the two-element boolean algebra is important because it "generates the class of boolean algebras". What does this mean? Where can a I read about this?

Also, is this related to the following paragraph from Wikipedia's article on Boolean algebras?

The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables).

2

There are 2 best solutions below

0
On

The two-element boolean algebra $\Bbb{B}$ generates the class of all boolean algebras $\mathsf{BA}$ in the sense that $\mathsf{BA}$ comprises all algebras (with the boolean algebra operations) that satisfy the equations that hold in $\Bbb{B}$.

In universal algebra jargon, $\mathsf{BA}$ is the variety generated by $\Bbb{B}$. See (for example) Definition 9.4 in Chapter II on p. 61 of Burris and Sankappanavar's A Course in Universal Algebra.

4
On

As explained in Rob Arthan's answer, the meaning of "the two-element Boolean algebra generates the class of Boolean algebras" is that every identity which holds in the two-element Boolean algebra holds in all Boolean algebras.

This follows from Stone's representation theorem which says that every Boolean algebra is isomorphic to a field of sets, i.e., a subalgebra of a power set. Since a power set is isomorphic to a direct product of two-element Boolean algebras, and since identities are preserved by isomorphisms and direct products and subalgebras, it follows that an identity which holds in the two-element Boolean algebra must also hold in all Boolean algebras.

More generally, every Horn sentence which holds in the two-element Boolean algebra holds in all nontrivial Boolean algebras. (A Horn sentence is a first-order sentence in prenex normal form whose quantifier-free part is a conjunction of Horn clauses; thus, an identity is a special kind of Horn sentence.)