##### Theorem19.15

A lattice \(L\) is distributive if and only if \begin{equation*}a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c )\end{equation*} for all \(a, b, c \in L\).

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\). An element \(O\) is a *smallest element* of \(X\) if \(O \preceq a\) for all \(a \in X\).

Let \(A\) be in \({\mathcal P}(X)\). Recall that the complement of \(A\) is
\begin{equation*}A' = X \setminus A = \{ x : x \in X \text{ and } x \notin A \}.\end{equation*}
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 X\), there exists an \(a'\) such that \(a \vee a' = I\) and \(a \wedge a' = O\).

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

A lattice \(L\) is distributive if and only if \begin{equation*}a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c )\end{equation*} 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.

A set \(B\) is a Boolean algebra if and only if there exist binary operations \(\vee\) and \(\wedge\) on \(B\) satisfying the following axioms.

\(a \vee b = b \vee a\) and \(a \wedge b = b \wedge a\) for \(a, b \in B\).

\(a \vee ( b \vee c) = (a \vee b) \vee c\) and \(a \wedge ( b \wedge c) = (a \wedge b) \wedge c\) for \(a, b, c \in B\).

\(a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\) and \(a \vee ( b \wedge c ) = (a \vee b ) \wedge ( a \vee c )\) for \(a, b, c \in B\).

There exist elements \(I\) and \(O\) such that \(a \vee O = a\) and \(a \wedge I = a\) for all \(a \in B\).

For every \(a \in B\) there exists an \(a' \in B\) such that \(a \vee a' = I\) and \(a \wedge a' = O\).

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

Let \(B\) be a Boolean algebra. Then

\(a \vee I = I\) and \(a \wedge O = O\) for all \(a \in B\).

If \(a \vee b = a \vee c\) and \(a \wedge b = a \wedge c\) for \(a, b, c \in B\), then \(b = c\).

If \(a \vee b = I\) and \(a \wedge b = O\), then \(b = a'\).

\((a')'=a\) for all \(a \in B\).

\(I' = O\) and \(O' = I\).

\((a \vee b)' = a' \wedge b'\) and \((a \wedge b)' = a' \vee b'\) (De Morgan's Laws).

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{align*}
\phi( a \vee b ) & = \phi(a) \vee \phi(b)\\
\phi( a \wedge b ) & = \phi(a) \wedge \phi(b)
\end{align*}
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 nonzero \(b \in B\). Equivalently, \(a\) is an atom of \(B\) if there is no nonzero \(b \in B\) distinct from \(a\) such that \(O \preceq b \preceq a\).

Let \(B\) be a finite Boolean algebra. If \(b\) is a nonzero element of \(B\), then there is an atom \(a\) in \(B\) such that \(a \preceq b\).

Let \(a\) and \(b\) be atoms in a finite Boolean algebra \(B\) such that \(a \neq b\). Then \(a \wedge b = O\).

Let \(B\) be a Boolean algebra and \(a, b \in B\). The following statements are equivalent.

\(a \preceq b\).

\(a \wedge b' = O\).

\(a' \vee b = I\).

Let \(B\) be a Boolean algebra and \(b\) and \(c\) be elements in \(B\) such that \(b \not\preceq c\). Then there exists an atom \(a \in B\) such that \(a \preceq b\) and \(a \not\preceq c\).

Let \(b \in B\) and \(a_1, \ldots, a_n\) be the atoms of \(B\) such that \(a_i \preceq b\). Then \(b = a_1 \vee \cdots \vee a_n\). Furthermore, if \(a, a_1, \ldots, a_n\) are atoms of \(B\) such that \(a \preceq b\), \(a_i \preceq b\), and \(b = a \vee a_1 \vee \cdots \vee a_n\), then \(a = a_i\) for some \(i = 1, \ldots, n\).

Let \(B\) be a finite Boolean algebra. Then there exists a set \(X\) such that \(B\) is isomorphic to \({\mathcal P}(X)\).

We leave the proof of the following corollary as an exercise.

The order of any finite Boolean algebra must be \(2^n\) for some positive integer \(n\).