Properties of Algebras of Sets 1

Properties of Algebras of Sets 1

Recall from the Algebras of Sets page that if $X$ is a set then an algebra on $X$ is a nonempty collection $\mathcal A$ of subsets of $X$ satisfying the following properties:

• For every $A_1, A_2 \in \mathcal A$ we have that $A_1 \cup A_2 \in \mathcal A$.
• For every $A \in \mathcal A$ we have that $A^c \in \mathcal A$.

We will now prove some nice properties of algebras of sets. More properties can be found on the Properties of Algebras of Sets 2 page.

 Proposition 1: If $\mathcal A$ is an algebra on a set $X$ then: a) $X \in \mathcal A$. B) $\emptyset \in \mathcal A$.
• Proof of a) Since $\mathcal A$ is nonempty there exists at least one set in $\mathcal A$. Let $A \in \mathcal A$. By property (2) of the definition, this means that $A^c \in \mathcal A$. By property (1) of the definition, since $A, A^c \in \mathcal A$ we have that:
(1)
\begin{align} \quad A \cup A^c = X \in \mathcal A \quad \blacksquare \end{align}
• Proof of b) Since $X \in \mathcal A$ by part (a) and from property (1) of the definition, we have that:
(2)
 Proposition 2: If $\mathcal A$ is an algebra on a set $X$ then for all sets $A_1, A_2 \in \mathcal A$ we have that $A_1 \cap A_2 \in \mathcal A$.
• Proof: Let $\mathcal A$ be an algebra on $X$. Let $A_1, A_2 \in \mathcal A$. Since $A_1 \cap A_2$ is the set of all elements of $X$ contained in both $A_1$ and $A_2$, we note that:
(3)
\begin{align} \quad (A_1 \cap A_2)^c = X \setminus (A_1 \cap A_2) = (X \setminus A_1) \cap (X \setminus A_2) = A_1^c \cup A_2^c \end{align}
• We take the complement of both sides above to get:
(4)
\begin{align} A_1 \cap A_2 = (A_1^c \cup A_2^c)^c \quad (*) \end{align}
• Since $\mathcal A$ is an algebra on $X$ we have that since $A_1, A_2 \in \mathcal A$ that $A_1^c, A_2^c \in \mathcal A$ by property (2) in the definition. By property (1) of the definition, since $A_1^c, A_2^c \in \mathcal A$ we have that $A_1^c \cup A_2^c \in \mathcal A$. Lastly, by property (2) of the definition, since $(A_1^c \cup A_2^c) \in \mathcal A$ we have that $(A_1^c \cup A_2^c)^c \in \mathcal A$. But by $(*)$ this means that $A_1 \cap A_2 \in \mathcal A$. $\blacksquare$
 Proposition 3: If $\mathcal A$ is an algebra on a set $X$ and if $A_1, A_2, ..., A_n \in \mathcal A$ for any $n \in \mathbb{N}$ then: a) $\displaystyle{\bigcup_{i=1}^{n} A_i \in \mathcal A}$. b) $\displaystyle{\bigcap_{i=1}^{n} A_i \in \mathcal A}$.
• Proof of a) Let $\mathcal A$ be an algebra on $X$. Assume that for $k \in \mathbb{N}$, $k \leq n$, that if $A_1, A_2, ..., A_{k-1}, A_k \in \mathcal A$ that $\displaystyle{\bigcup_{i=1}^{k-1} A_i \in \mathcal A}$. Then by property (1) of the definition we have that:
(5)
\begin{align} \quad \bigcup_{i=1}^{k} A_i = \left ( \bigcup_{i=1}^{k-1} A_i \right ) \cup A_k \in \mathcal A \end{align}
• By the principle of mathematical induction, for all $n \in \mathbb{N}$ we have that if $A_1, A_2, ..., A_n \in \mathcal A$ then $\displaystyle{\bigcup_{i=1}^{n} A_i \in \mathcal A}$. $\blacksquare$
• Proof of b) Let $\mathcal A$ be an algebra on $X$. Assume that for $k \in \mathbb{N}$, $k < n$, that if $A_1, A_2, ..., A_{k-1}, A_k \in \mathcal A$ that $\displaystyle{\bigcap_{i=1}^{k-1} A_i \in \mathcal A}$. Then by the previous proposition we have that:
(6)
\begin{align} \quad \bigcap_{i=1}^{k} A_i = \left ( \bigcap_{i=1}^{k-1} A_i \right ) \cap A_k \in \mathcal A \end{align}
• By the principle of mathematical induction, for all $n \in \mathbb{N}$ we have that if $A_1, A_2, ..., A_n \in \mathcal A$ then $\displaystyle{\bigcap_{i=1}^{n} A_i \in \mathcal A}$. $\blacksquare$