Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section13.4Atoms of a Boolean Algebra

In this section we will look more closely at something we've hinted at, which is that every finite Boolean algebra is isomorphic to an algebra of sets. We will show that every finite Boolean algebra has \(2^n\) elements for some \(n\) with precisely \(n\) generators, called atoms.

Consider the Boolean algebra \([B; \lor , \land, \bar{\hspace{5 mm}}]\), whose ordering diagram is depicted in Figure 13.4.1

Illustration of the atom concept
Figure13.4.1Illustration of the atom concept

We note that \(1 = a_1 \lor a_2 \lor a_3\), \(b_1 = a_1 \lor a_2\), \(b_2 = a_1 \lor a_3\), and \(b_3 = a_2 \lor a_3\); that is, each of the elements above level one can be described completely and uniquely in terms of the elements on level one. The \(a_i\)'s have uniquely generated the nonzero elements of \(B\) much like a basis in linear algebra generates the elements in a vector space. We also note that the \(a_i\)'s are the immediate successors of the minimum element, 0. In any Boolean algebra, the immediate successors of the minimum element are called atoms. For example, let \(A\) be any nonempty set. In the Boolean algebra \([\mathcal{P}(A); \cup , \cap, \hspace{1 mm}^c]\) (over \(\subseteq\)), the singleton sets are the generators, or atoms, of the algebraic structure since each element \(\mathcal{P}(A)\) can be described completely and uniquely as the join, or union, of singleton sets.

Definition13.4.2Atom

A nonzero element \(a\) in a Boolean algebra \([B; \lor , \land, \bar]\) is called an atom if for every \(x \in B\), \(x \land a = a\) or \(x \land a = 0\).

The condition that \(x \land a = a\) tells us that \(x\) is a successor of \(a\text{;}\) that is, \(a \preceq x\), as depicted in Figure 13.4.3(a)

The condition \(x \land a = 0\) is true only when \(x\) and \(a\) are “not connected.” This occurs when \(x\) is another atom or if \(x\) is a successor of atoms different from \(a\text{,}\) as depicted in Figure 13.4.3(b).

Conditions for an atom
Figure13.4.3Conditions for an atom

An alternate definition of an atom is based on the concept of “covering.”

Definition13.4.4The Covering Relation

Given a boolean algebra \([B; \lor , \land, \bar]\), let \(x, z \in B\text{.}\) We say that \(z\) covers \(x\) iff \(x \prec z\) and there does not exist \(y \in B\) with \(x \prec y \prec z\text{.}\)

It can be proven that the atoms of Boolean algebra are precisely those elements that cover the zero element.

The set of atoms of the Boolean algebra \(\left[D_{30}; \lor , \land, \bar{\hspace{5 mm}}\right]\) is \(M = \{2, 3, 5\}\). To see that \(a = 2\) is an atom, let \(x\) be any nonzero element of \(D_{30}\) and note that one of the two conditions \(x \land 2 = 2\) or \(x \land 2 = 1\) holds. Of course, to apply the definition to this Boolean algebra, we must remind ourselves that in this case the 0-element is 1, the operation \(\land\) is greatest common divisor, and the poset relation is “divides.” So if \(x = 10\), we have \(10 \land 2 = 2\) (or \(2 \mid 10\)), so Condition 1 holds. If \(x = 15\), the first condition is not true. (Why?) However, Condition 2, \(15 \land 2 = 1\), is true. The reader is encouraged to show that 3 and 5 also satisfy the definition of an atom. Next, if we should compute the join (the least common multiple in this case) of all possible combinations of the atoms 2, 3, and 5 to generate all nonzero (non-1 in this case) elements of \(D_{30}\). For example, \(2 \lor 3 \lor 5 = 30\) and \(2 \lor 5 = 10\). We state this concept formally in the following theorem, which we give without proof.

We now ask ourselves if we can be more definitive about the structure of different Boolean algebras of a given order. Certainly, the Boolean algebras \(\left[D_{30}; \lor , \land, \land\bar{\hspace{5 mm}} \right]\) and \([\mathcal{P}(A); \cup , \cap, \hspace{1 mm}^c]\) have the same graph (that of Figure 13.4.1), the same number of atoms, and, in all respects, look the same except for the names of the elements and the operations. In fact, when we apply corresponding operations to corresponding elements, we obtain corresponding results. We know from Chapter 11 that this means that the two structures are isomorphic as Boolean algebras. Furthermore, the graphs of these examples are exactly the same as that of Figure 13.4.1, which is an arbitrary Boolean algebra of order \(8 = 2^3\).

In these examples of a Boolean algebra of order 8, we note that each had 3 atoms and \(2^3 = 8\) number of elements, and all were isomorphic to \([\mathcal{P}(A ); \cup , \cap, \hspace{1 mm}^c]\), where \(A = \{a, b, c\}\). This leads us to the following questions:

  • Are there any different (nonisomorphic) Boolean algebras of order 8?

  • What is the relationship, if any, between finite Boolean algebras and their atoms?

  • How many different (nonisomorphic) Boolean algebras are there of order 2? Order 3? Order 4? etc.

The answers to these questions are given in the following theorem and corollaries.

Proof

The above theorem and corollaries tell us that we can only have finite Boolean algebras of orders \(2^1, 2^2, 2^3,. . , 2^n\), and that all finite Boolean algebras of any given order are isomorphic. These are powerful tools in determining the structure of finite Boolean algebras. In the next section, we will discuss one of the easiest ways of describing a Boolean algebra of any given order.

Subsection13.4.1Exercises for Section 13.4

1

  1. Show that \(a = 2\) is an atom of the Boolean algebra \(\left[D_{30}; \lor , \land, - \right]\).

  2. Repeat part a for the elements 3 and 5 of \(D_{30}\).

  3. Verify Theorem Theorem 13.4.5 for the Boolean algebra \(\left[D_{30}; \lor , \land, - \right]\).

Answer
2

Let \(A = \{a, b, c\}\).

  1. Rewrite the definition of atom for \([\mathcal{P}(A); \cup , \cap, c ]\). What does \(a \leq x\) mean in this example?

  2. Find all atoms of \([\mathcal{P}(A); \cup , \cap, c ]\).

  3. Verify Theorem 13.4.5 for \([\mathcal{P}(A); c, \cup , \cap ]\).

3

Verify Theorem 13.4.6 and its corollaries for the Boolean algebras in Exercises 1 and 2 of this section.

Answer
4

Give a description of all Boolean algebras of order 16. Note that the graph of this Boolean algebra.

5

Corollary 13.4.7 implies that there do not exist Boolean algebras of orders 3, 5, 6, 7, 9, etc. (orders different from \(2^n\)). Without this corollary, directly show that we cannot have a Boolean algebra of order 3.

Hint Answer
6

  1. There are many different, yet isomorphic, Boolean algebras with two elements. Describe one such Boolean algebra that is derived from a power set, \(\mathcal{P}(A)\), under \(\subseteq\). Describe a second that is described from \(D_n\), for some \(n \in P\), under “divides.”

  2. Since the elements of a two-element Boolean algebra must be the greatest and least elements, 1 and 0, the tables for the operations on \(\{0, 1\}\) are determined by the Boolean algebra laws. Write out the operation tables for \([\{0, 1\}; \lor , \land, -]\).

7

Find a Boolean algebra with a countably infinite number of elements.

Answer
8

Prove that the direct product of two Boolean algebras is a Boolean algebra.

Hint
9

Prove if two finite sets \(A_1\) and \(A_2\) both have \(n\) elements then \([\mathcal{P}(A_1); \cup , \cap, \hspace{1 mm}^c]\) is isomorphic to \([\mathcal{P}(A_2); \cup , \cap, \hspace{1 mm}^c]\)

10

Prove an element of a Boolean algebra is an atom if and only if it covers the zero element.