maths.free › Abstract Algebra › 19. Lattices and Boolean Algebras › Boolean Algebras

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.

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.

Theorem

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\).

Proof

Let \(B\) be a set satisfying (1)(5) in the theorem. One of the idempotent laws is satisfied since \[\begin{aligned}a & = a \vee O \\ & = a \vee (a \wedge a') \\ & = (a \vee a) \wedge (a \vee a') \\ & = (a \vee a ) \wedge I \\ & = a \vee a\end{aligned}\]. Observe that \[\begin{aligned}\end{aligned}\]. Consequently, the first of the two absorption laws holds, since \[\begin{aligned}a \vee (a \wedge b) & = (a \wedge I) \vee (a \wedge b) \\ & = a \wedge (I \vee b) \\ & = a \wedge I \\ & = a\end{aligned}\]. The other idempotent and absorption laws are proven similarly. Since \(B\) also satisfies (1)(3), the conditions of are met; therefore, \(B\) must be a lattice. Condition (4) tells us that \(B\) is a distributive lattice.

For \(a \in B\), \(O \vee a = a\); hence, \(O \preceq a\) and \(O\) is the smallest element in \(B\). To show that \(I\) is the largest element in \(B\), we will first show that \(a \vee b = b\) is equivalent to \(a \wedge b = a\). Since \(a \vee I = a\) for all \(a \in B\), using the absorption laws we can determine that \[\begin{aligned}\end{aligned}\] or \(a \preceq I\) for all \(a\) in \(B\). Finally, since we know that \(B\) is complemented by (5), \(B\) must be a Boolean algebra.

Conversely, suppose that \(B\) is a Boolean algebra. Let \(I\) and \(O\) be the greatest and least elements in \(B\), respectively. If we define \(a \vee b\) and \(a \wedge b\) as least upper and greatest lower bounds of \(\{ a, b\}\), then \(B\) is a Boolean algebra by , , and our hypothesis.

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

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).

Proof

We will prove only (2). The rest of the identities are left as exercises. For \(a \vee b = a \vee c\) and \(a \wedge b = a \wedge c\), we have \[\begin{aligned}b & = b \vee (b \wedge a) \\ & = b \vee (a \wedge b) \\ & = b \vee (a \wedge c) \\ & = ( b \vee a) \wedge ( b \vee c) \\ & = ( a \vee b) \wedge ( b \vee c) \\ & = ( a \vee c) \wedge ( b \vee c) \\ & = ( c \vee a ) \wedge ( c\vee b ) \\ & = c \vee (a \wedge b) \\ & = c \vee ( a \wedge c ) \\ & = c \vee ( c \wedge a ) \\ & = c\end{aligned}\].

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\).

Lemma

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

Proof

If \(b\) is an atom, let \(a =b\). Otherwise, choose an element \(b_1\), not equal to \(O\) or \(b\), such that \(b_1 \preceq b\). We are guaranteed that this is possible since \(b\) is not an atom. If \(b_1\) is an atom, then we are done. If not, choose \(b_2\), not equal to \(O\) or \(b_1\), such that \(b_2 \preceq b_1\). Again, if \(b_2\) is an atom, let \(a = b_2\). Continuing this process, we can obtain a chain \[\begin{aligned}\end{aligned}\]. Since \(B\) is a finite Boolean algebra, this chain must be finite. That is, for some \(k\), \(b_k\) is an atom. Let \(a = b_k\).

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

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\neq

not equal
The two sides are different.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

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.

Özüňi synla

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

_Ýaşa Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula