Smallest Algebras of a Set X Containing Particular Subsets of X

Suppose that $X$ is a set and $\mathcal C$ is a collection of subsets of $X$. Since $\mathcal C \subseteq \mathcal P(X)$ and $\mathcal P(X)$ is an algebra on $X$ we know that there exists at least one algebra on $X$ containing $\mathcal C$.

We would like to be able to construct a smallest algebra on $X$ containing the sets in $\mathcal C$. We will make this clearer in the theorem below. First we must prove the following lemma.

Lemma 1: Let $X$ be a set and let $M$ be a collection of algebras on $X$. Then $\displaystyle{\bigcap_{\mathcal A \in M} \mathcal A}$ is an algebra on $X$.

• Proof: Let $\displaystyle{A_1, A_2 \in \bigcap_{\mathcal A \in M} \mathcal A}$. Then $A_1, A_2 \in \mathcal A$ for every $\mathcal A \in M$. Therefore $A_1 \cup A_2 \in \mathcal A$ for every $\mathcal A \in M$ since each $\mathcal A$ is an algebra on $X$. Hence:

(1)

\begin{align} \quad A_1 \cup A_2 \in \bigcap_{\mathcal A \in M} \mathcal A \quad (*) \end{align}

• Let $A \in \bigcap_{\mathcal A \in M} \mathcal A$. Then $A \in \mathcal A$ for every $\mathcal A \in M$. Therefore $A^c \in \mathcal A$ for every $\mathcal A \in M$ since each $\mathcal A$ is an algebra on $X$. Hence:

(2)

\begin{align} \quad A^c \in \bigcap_{\mathcal A \in M} \mathcal A \quad (**) \end{align}

• From $(*)$ and $(**)$ we conclude that $\displaystyle{\bigcap_{\mathcal A \in M} \mathcal A}$ is an algebra on $X$. $\blacksquare$

Theorem 2: Let $X$ be a set and let $\mathcal C$ be a collection of subsets of $X$. Then there exists a smallest algebra $\mathcal M$ on $X$ containing all sets in $\mathcal C$. That is: 1) $\mathcal C \subseteq \mathcal M$. 2) If $\mathcal B$ is an algebra on $X$ such that $\mathcal C \subseteq \mathcal B$ then $\mathcal M \subseteq \mathcal B$.

Property (2) in the theorem above says that there exists no algebra $\mathcal B$ on $X$ containing $\mathcal C$ that does not contain $\mathcal M$.

• Proof: Let $\mathcal C$ be a collection of subsets of $X$. Define a set $M$ as follows:

(3)

\begin{align} \quad M = \{ \mathcal A : \mathcal A \: \mathrm{is \: an \: algebra \: on \:} X \: \mathrm{and} \: \mathcal C \subseteq \mathcal A \} \end{align}

• Notice that $\mathcal P(X)$, the power set on $X$, is an algebra on $X$ containing $\mathcal C$. Therefore, $M$ is nonempty. Define an algebra $\mathcal A$ on $X$ as follows:

(4)

\begin{align} \quad \mathcal M = \bigcap_{\mathcal A \in M} \mathcal A \end{align}

• By Lemma 1, $\mathcal M$ is an algebra on $X$.

• Clearly, $\mathcal C \subseteq \mathcal M$.

• Let $\mathcal B$ be an algebra on $X$ such that $\mathcal C \subseteq \mathcal B$. Then $\mathcal B \in M$ and $\displaystyle{\mathcal M = \bigcap_{\mathcal A \in M} \mathcal A \subseteq \mathcal B}$ by definition. Hence $\mathcal M$ is the smallest algebra on $X$ containing the subsets in $\mathcal C$. $\blacksquare$