Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

13.4: Atoms of a Boolean Algebra

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 2n elements for some n with precisely n generators, called atoms.

Consider the Boolean algebra [B;,,¯], whose ordering diagram is depicted in Figure 13.4.1

clipboard_e987d942738e8ca3623c6b968f2b06fc8.pngFigure 13.4.1: Illustration of the atom concept

We note that 1=a1a2a3, b1=a1a2, b2=a1a3, and b3=a2a3; that is, each of the elements above level one can be described completely and uniquely in terms of the elements on level one. The ai's have uniquely generated the non-least elements of B much like a basis in linear algebra generates the elements in a vector space. We also note that the ai'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 [P(A);,,c] (over ), the singleton sets are the generators, or atoms, of the algebraic structure since each element P(A) can be described completely and uniquely as the join, or union, of singleton sets.

Definition 13.4.1: Atom

A non-least element a in a Boolean algebra [B;,,¯] is called an atom if for every xB, xa=a or xa=0.

The condition that xa=a tells us that x is a successor of a; that is, ax, as depicted in Figure 13.4.2(a)

The condition xa=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, as depicted in Figure 13.4.2(b).

clipboard_e52d7452fa86a7f237dd1c88af0d206c1.pngFigure 13.4.2: Conditions for an atom

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

Definition 13.4.2: The Covering Relation

Given a Boolean algebra [B;,,¯], let x,zB. We say that z covers x iff xz and there does not exist yB with xyz.

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 [D30;,,¯] is M={2,3,5}. To see that a=2 is an atom, let x be any non-least element of D30 and note that one of the two conditions x2=2 or x2=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 is greatest common divisor, and the poset relation is “divides.” So if x=10, we have 102=2 (or 210), so Condition 1 holds. If x=15, the first condition is not true. (Why?) However, Condition 2, 152=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 D30. For example, 235=30 and 25=10. We state this concept formally in the following theorem, which we give without proof.

Theorem 13.4.1

Let B=[B;,,¯] be any finite Boolean algebra. Let A={a1,a2,,an} be the set of all atoms of B. Then every element in B can be expressed uniquely as the join of a subset of A.

The least element in relation to this theorem bears noting. If we consider the empty set of atoms, we would consider the join of elements in the empty set to be the least element. This makes the statement of the theorem above a bit more tidy since we don't need to qualify what elements can be generated from atoms.

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 [D30;,,¯] and [P(A);,,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=23.

In these examples of a Boolean algebra of order 8, we note that each had 3 atoms and 23=8 number of elements, and all were isomorphic to [P(A);,,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.

Theorem 13.4.2

Let B=[B;,,] be any finite Boolean algebra, and let A be the set of all atoms of B. Then [P(A);,,c] is isomorphic to [B;,,]

Proof

An isomorphism that serves to prove this theorem is T:P(A)B defined by T(S)=aSa, where T() is interpreted as the zero of B. We leave it to the reader to prove that this is indeed an isomorphism.

Corollary 13.4.1

Every finite Boolean algebra B=[B;,,¯] has 2n elements for some positive integer n.

Proof

Let A be the set of all atoms of B and let |A|=n. Then there are exactly 2n elements (subsets) in P(A),and by Theorem 13.4.2, [B;,,¯] is isomorphic to [P(A);,c] and must also have 2n elements.

Corollary 13.4.2

All Boolean algebras of order 2n are isomorphic to one another.

Proof
clipboard_ed69fe7ac87c3d1a3349ef90da6e9660d.pngFigure 13.4.1: Isomorphisms to be combined

Every Boolean algebra of order 2n is isomorphic to [P(A);,,c] when |A|=n. Hence, if B1 and B2 each have 2n elements, they each have n atoms. Suppose their sets of atoms are A1 and A2, respectively. We know there are isomorphisms T1 and T2, where Ti:BiP(Ai), i=1,2. In addition we have an isomorphism, N from P(A1) into P(A2), which we ask you to prove in Exercise 13.4.9. We can combine these isomorphisms to produce the isomorphism T12NT1:B1B2, which proves the corollary.

The above theorem and corollaries tell us that we can only have finite Boolean algebras of orders 21,22,23,..,2n, 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.

Exercises

Exercise 13.4.1

  1. Show that a=2 is an atom of the Boolean algebra [D30;,,].
  2. Repeat part a for the elements 3 and 5 of D30.
  3. Verify Theorem 13.4.1 for the Boolean algebra [D30;,,].
Answer
  1. For a=3 we must show that for each xD30 one of the following is true: x3=3 or x3=1. We do this through the following table:
    x verification1235610153013=123=133=353=163=3203=1153=3303=3
    For a=5, a similar verification can be performed.
  2. 6=23, 10=25, 15=35, and 30=235.

Exercise 13.4.2

Let A={a,b,c}.

  1. Rewrite the definition of atom for [P(A);,,c]. What does ax mean in this example?
  2. Find all atoms of [P(A);,,c].
  3. Verify Theorem 13.4.1 for [P(A);c,,].

Exercise 13.4.3

Verify Theorem 13.4.2 and its corollaries for the Boolean algebras in Exercises 13.4.1 and 13.4.2 of this section.

Answer

If B=D30  30 then A={2,3,5} and D30 is isomorphic to P(A), where
1 5{5}2{2} 10{2,5}3{3} 15{3,5}6{2,3} 30{2,3,5} and  Join Union Meet Intersection Complement Set Complement

Exercise 13.4.4

Give an example of a Boolean algebra of order 16 whose elements are certain subsets of the set {1,2,3,4,5,6,7}

Exercise 13.4.5

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

Hint

Assume that [B;,,] is a Boolean algebra of order 3 where B={0,x,1} and show that this cannot happen by investigating the possibilities for its operation tables.

Answer

Assume that x0 or 1 is the third element of a Boolean algebra. Then there is only one possible set of tables for join and meet, all following from required properties of the Boolean algebra.

0x10x10x1xx11110x10x10000xx0x1

Next, to find the complement of x we want y such that xy=0 and xy=1. No element satisfies both conditions; hence the lattice is not complemented and cannot be a Boolean algebra. The lack of a complement can also be seen from the ordering diagram from which and must be derived.

Exercise 13.4.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, P(A), under . Describe a second that is described from Dn, for some nP, 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};,,].

Exercise 13.4.7

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

Answer

Let X be any countably infinite set, such as the integers. A subset of X is cofinite if it is finite or its complement is finite. The set of all cofinite subsets of X is:

  1. Countably infinite - this might not be obvious, but here is a hint. Assume X={x0,x1,x2,}. For each finite subset A of X, map that set to the integer i=0χA(xi)2i You can do a similar thing to sets that have a finite complement, but map them to negative integers. Only one minor adjustment needs to be made to accommodate both the empty set and X.
  2. Closed under union
  3. Closed under intersection, and
  4. Closed under complementation.

Therefore, if B={AX:A is cofinite}, then B is a countable Boolean algebra under the usual set operations.

Exercise 13.4.8

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

Hint

“Copy” the corresponding proof for groups in Section 11.6.

Exercise 13.4.9

Prove if two finite sets A1 and A2 both have n elements then [P(A1);,,c] is isomorphic to [P(A2);,,c]

Exercise 13.4.10

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


This page titled 13.4: Atoms of a Boolean Algebra is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?