Boolean Algebras

Let us investigate the example of the power set, \({\mathcal P}(X)\), of a set \(X\) more closely. The power set is a lattice that is ordered by inclusion. By the definition of the power set, the largest element in \({\mathcal P}(X)\) is \(X\) itself and the smallest element is \(\emptyset\), the empty set. For any set \(A\) in \({\mathcal P}(X)\), we know that \(A \cap X = A\) and \(A \cup \emptyset = A\). This suggests the following definition for lattices. An element \(I\) in a poset \(X\) is a largest element if \(a \preceq I\) for all \(a \in X\). \(I\) largest element in a lattice An element \(O\) is a smallest element of \(X\) if \(O \preceq a\) for all \(a \in X\). \(O\) smallest element in a lattice

Let \(A\) be in \({\mathcal P}(X)\). Recall that the complement of \(A\) is \[\begin{aligned}\end{aligned}\]. We know that \(A \cup A' = X\) and \(A \cap A' = \emptyset\). We can generalize this example for lattices. A lattice \(L\) with a largest element \(I\) and a smallest element \(O\) is complemented if for each \(a \in L\), there exists an \(a'\) such that \(a \vee a' = I\) and \(a \wedge a' = O\). \(a'\) complement of \(a\) in a lattice

In a lattice \(L\), the binary operations \(\vee\) and \(\wedge\) satisfy commutative and associative laws; however, they need not satisfy the distributive law \[\begin{aligned}\end{aligned}\] however, in \({\mathcal P}(X)\) the distributive law is satisfied since \[\begin{aligned}\end{aligned}\] for \(A, B, C \in {\mathcal P}(X)\). We will say that a lattice \(L\) is distributive if the following distributive law holds: \[\begin{aligned}\end{aligned}\] for all \(a, b, c \in L\).

A Boolean algebra is a lattice \(B\) with a greatest element \(I\) and a smallest element \(O\) such that \(B\) is both distributive and complemented. The power set of \(X\), \({\mathcal P}(X)\), is our prototype for a Boolean algebra. As it turns out, it is also one of the most important Boolean algebras. The following theorem allows us to characterize Boolean algebras in terms of the binary relations \(\vee\) and \(\wedge\) without mention of the fact that a Boolean algebra is a poset.

Many other identities hold in Boolean algebras. Some of these identities are listed in the following theorem.

A Boolean algebra is a finite Boolean algebra if it contains a finite number of elements as a set. Finite Boolean algebras are particularly nice since we can classify them up to isomorphism.

Let \(B\) and \(C\) be Boolean algebras. A bijective map \(\phi : B \rightarrow C\) is an isomorphism of Boolean algebras if \[\begin{aligned}\phi( a \vee b ) & = \phi(a) \vee \phi(b) \\ \phi( a \wedge b ) & = \phi(a) \wedge \phi(b)\end{aligned}\] for all \(a\) and \(b\) in \(B\).

We will show that any finite Boolean algebra is isomorphic to the Boolean algebra obtained by taking the power set of some finite set \(X\). We will need a few lemmas and definitions before we prove this result. Let \(B\) be a finite Boolean algebra. An element \(a \in B\) is an atom of \(B\) if \(a \neq O\) and \(a \wedge b = a\) for all \(b \in B\) with \(b \neq O\). Equivalently, \(a\) is an atom of \(B\) if there is no \(b \in B\) with \(b \neq O\) distinct from \(a\) such that \(O \preceq b \preceq a\).

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.