Exercise 1.4.8 (Cardinality of the generated Boolean algebra)

Suppose that $F=\{E_1,\dots ,E_n\}$ is a finite collection of subsets of a set $X$, and let $B$ be an arbitrary Boolean algebra containing $F$. By the properties of the intersection we have $\#{⟨F⟩}_{\mathit{bool}}\le \#B$. In the following we induct on $n\in \mathbb{N}$.

• (induction base) Let $n=1$, i.e., $F=\{E_1\}$ for some set $E_1\subseteq X$. It is easy to verify that the set

  $$B:=\{\varnothing ,X,E_1,X∕E_1\}$$

  is a Boolean algebra on $X$, and it contains $F$. Thus, $\#{⟨F⟩}_{\mathit{bool}}\le \#B=4=2^{2^1}$.

• (induction step) Now let $F=\{E_1,\dots ,E_{n-1},E_n\}$ (obviously all elements assumed to be distinct), and suppose inductively that we have proven this statement for some $n-1\in \mathbb{N}$. By induction hypothesis we can find a Boolean algebra $B_{n-1}$ for the set $F_{n-1}=\{E_1,\dots ,E_{n-1}\}$ of the cardinality $2^{2^{n-1}}$, and we can find a Boolean algebra $B_{n-1}^{\prime }$ for the set $F_{n-1}^{\prime }=\{E_2,\dots ,E_n\}$ also of the cardinality $2^{2^{n-1}}$. The crucial step here is to employ Exercise 1.4.4 in order to use the fact that both sets can be generated using some atomic algebras $A_1,\dots ,A_k$ or $A_1^{\prime },\dots ,A_k^{\prime }$ of the size $k\in \mathbb{N}$ bounded by $k\le 2^{n-1}$. By Example 1.4.7 (Atomic algebra), let $B$ be the Boolean algebra generated by $\{A_1,\dots ,A_k,A_1^{\prime },\dots ,A_k^{\prime }\}$. Then $B$ is a Boolean algebra containing $F$ ( $E_i$ is contained in $B_{n-1}$ or $B_{n-1}^{\prime }$ and can thus be generated using one of the collections ${(A_i)}_{i=1}^k$ or ${(A_i^{\prime })}_{i=1}^k$). We hence have

  $$\#{⟨F⟩}_{\mathit{bool}}\le \#B=2^{2k}\le 2^{2\cdot 2^{n-1}}=2^{2^n}$$

To demonstrate that this bound is sharp, consider the discrete set $X={\{0,1\}}^d$. Then, there exists a family of subsets $F\subseteq P(X)$ such that ${⟨F⟩}_{\mathit{bool}}=2^{2^d}$. We prove the existence by inducting on $d\in \mathbb{N}$.

• (induction base) Let $d=2$, i.e., $X=\{(0,0),(0,1),(1,0),(1,1)\}$. Set $F:=\{\{(0,0),(1,0)\},\{(1,0),(0,1)\}\}$. Let $B$ be an arbitrary Boolean algebra containing $F$. Then all of the atom-elements of $X$ are contained in $B$. This is demonstrated by the closure under intersection and complements property of the Boolean algebra:

  $$\begin{array}{llll}\hfill (0,0)& ={\left\{(1,0),(0,1)\right\}}^c\cap \left\{(0,0),(1,0)\right\}=\left\{(0,0),(1,1)\right\}\cap \left\{(0,0),(1,0)\right\}& \hfill & \\ \hfill (0,1)& ={\{(1,0)\}}^c\cap \{(1,0),(0,1)\}=\{(0,0),(0,1),(1,1)\}\cap \{(1,0),(0,1)\}& \hfill & \\ \hfill (1,0)& ={\{(0,0)\}}^c\cap \{(0,0),(1,0)\}=\{(0,1),(1,0),(1,1)\}\cap \{(0,0),(1,0)\}& \hfill & \\ \hfill (1,1)& ={\{(0,0),(0,1),(1,0)\}}^c& \hfill & \end{array}$$

  In other words, $X\subset B$. Therefore, by the closure under unions property of the Boolean algebra, we also have $P(X)\subseteq B$. Since our choice of $B$ was arbitrary, taking intersections we obtain $P(X)\subseteq {⟨F⟩}_{\mathit{bool}}$ and therefore $2^{2^2}\le \#{⟨F⟩}_{\mathit{bool}}$. Combining this with the previosly proven assertion, we see the sharpness of the bound $2^{2^d}={⟨F⟩}_{\mathit{bool}}$.

• (induction step) Now suppose inductively that there exists a family $F_{d-1}$ of subsets of ${\{0,1\}}^{d-1}$ with $\#{⟨F_{d-1}⟩}_{\mathit{bool}}=2^{2^{d-1}}$ and ${\{0,1\}}^{d-1}\subseteq {⟨F_{d-1}⟩}_{\mathit{bool}}$. Now consider $X={\{0,1\}}^d$. Recall that we can bijectively associate ${\{0,1\}}^{d-1}$ with two subsets of ${\{0,1\}}^d$: either those ending with 0, or those ending with 1:

  $${\{0,1\}}^d=\left\{(x,0):x\in {\{0,1\}}^{d-1}\right\}\cup \left\{(x,1):x\in {\{0,1\}}^{d-1}\right\}$$

  Thus, consider extended collections

  $$F_d^{\prime }:=\left\{\{(x,0):x\in B\}\subseteq {\{0,1\}}^d:B\in F_{d-1}\right\}{F}_d^{\mathit{\prime \prime }}:=\left\{\{(x,1):x\in B\}\subseteq {\{0,1\}}^d:B\in F_{d-1}\right\}$$

  It is easy to verify that ${\{0,1\}}^d\subseteq F_d$ where $F_d:=F_d^{\prime }\cup F_d^{\mathit{\prime \prime }}$. Similarly, we must now have $P(X)\subseteq F_d$ and thus $P(X)\subseteq {⟨F_d⟩}_{\mathit{bool}}$. But this implies $2^{2^d}=\#{⟨F_d⟩}_{\mathit{bool}}$ as desired.

For the concrete bound:

The set ${\{0,1\}}^d$ has $2^d$ elements. Let $F$ be the set of singleton elements, which is an atomic base set for ${\{0,1\}}^d$, generating the discrete algebra. Then by MTE4.4, the discrete algebra consists of $2^{2^d}$ sets.