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.
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.
Finite Boolean Algebras
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\).
A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group. That is where the idea came from.
What is the difference between a ring and a field?
A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.