Exercise 1.4.9 (Recursive description of a generated Boolean algebra)

Before we start, notice that ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$ is a Boolean algebra:

(i)

The empty set is practically a union of finite (that is 0) number of sets in the previous $F_{i-1}$; thus, it is even added at each step.

(ii)

Let $E\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$, and let $m\in \mathbb{N}$ be the smallest such that $E\in F_m$. Then $E^c$ is contained in $F_{m+1}$.

(iii)

Let $E\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$, and let $m,k\in \mathbb{N}$ be the smallest such that $E\in F_m$ and $F\in F_k$. Let $M:=\max <!--\; FUNCTION\; APPLICATION\; -->\{m,k\}$, and we have $E,F\in F_M$ (the set from the lower hierarchy just gets copied to the next level over and over again). Then, $E\cup F\in F_{m+1}$ by definition.

We now demonstrate that both ${⟨F⟩}_{\mathit{bool}}\subseteq {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$ and ${⟨F⟩}_{\mathit{bool}}\supseteq {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$ hold.

• We demonstrate ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n\subseteq {⟨F⟩}_{\mathit{bool}}$ by induction on $n\in \mathbb{N}$ in $F_n\subseteq {⟨F⟩}_{\mathit{bool}}$.

  • (induction base) Let $n=1$, and pick an arbitrary $E\in F_1$. Then the $E$ is either a union of sets in $F_0=F$ or a complement of such union. By the definition of a Boolean algebra ${⟨F⟩}_{\mathit{bool}}\supseteq F$ we have ${⟨F⟩}_{\mathit{bool}}$ is closed under unions and complements, and thus must contain $E$ in both of the cases.
  • (induction step) Now suppose inductively that we have proven this assertion for some $n\in \mathbb{N}$. Now consider $F_{n+1}$ and an arbitrary $E\in F_{n+1}$. By definition, we then have two cases: either $E$ is a finite union of sets in $F_n$ or it is a complement of such a union. In the former case $E=E_1\cup \dots \cup E_k$ for $E_1,\dots ,E_k\in F_n$. But each of them is contained in $F_n\subseteq {⟨F⟩}_{\mathit{bool}}$ by the induction hypothesis, and we are done by the closure under unions. In the latter case, $E=X∕(E_1\cup \dots \cup E_k)$ for $E_1,\dots ,E_k\in F_n$, and we are done in this case as well by the closure under complements.

• (alternative proof) Obviously, ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$ is a Boolean algebra, and so by Example 1.4.11, ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n={⟨{\bigcup }_{n=0}^{\infty }{F}_n⟩}_{\mathit{bool}}$. From this it easy to deduce

  $$\bigcap \left\{B\subseteq P(X):\begin{array}{c}B\text{ is a Boolean algebra}\hfill \\ F_0\subseteq B\hfill \end{array}\right\}\supseteq \bigcap \left\{B\subseteq P(X):\begin{array}{c}B\text{ is a Boolean algebra}\hfill \\ \bigcup _{n=0}^{\infty }{F}_n\subseteq B\hfill \end{array}\right\}.$$

• By Exercise 1.4.6 ${⟨F⟩}_{\mathit{bool}}$ is the finest Boolean algebra that is coarser than any other Boolean algebra containing $F_0$. But since ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$ is a Boolean algebra which contains $F_0$, we obviously have ${⟨F⟩}_{\mathit{bool}}\subseteq {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{F}_n$.