Properties of Algebras of Sets 2

Properties of Algebras of Sets 2

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 1 page.

Proposition 1: Let $X$ be a set and let $\mathcal A$ be an algebra on $X$. Then:
a) If $A_1, A_2 \in \mathcal A$ then $A_1 \setminus A_2 \in \mathcal A$.
b) If $A, A_1, A_2, ..., A_n \in \mathcal A$ then $\displaystyle{A \setminus \left ( \bigcup_{i=1}^{n} A_i \right )} \in \mathcal A$.
  • Proof of a) Let $\mathcal A$ be an algebra on $X$ with $A_1, A_2 \in \mathcal A$. By simple properties of sets we have that:
(1)
\begin{align} \quad A_1 \setminus A_2 = A_1 \cap A_2^c \end{align}
  • By property (2) of the definition we have that since $A_2 \in \mathcal A$ that then $A_2^c \in \mathcal A$. Furthermore, from the previous page on properties of algebras of sets we know that since $A_1, A_2^c \in \mathcal A$ that $A_1 \cap A_2^c \in \mathcal A$. Therefore $A_1 \setminus A_2 \in \mathcal A$. $\blacksquare$
  • Proof of b): The proof of (b) can be done by a simple induction argument and we omit here.
Proposition 2: Let $X$ be a set and let $\mathcal A$ be an algebra on $X$. Let $(A_n)_{n=1}^{\infty}$ be a sequence of sets in $\mathcal A$. Then there exists a sequence $(B_n)_{n=1}^{\infty}$ of sets in $\mathcal A$ such with the properties that:
1) The sets in the sequence $(B_n)_{n=1}^{\infty}$ are mutually disjoint, that is, for every $m, n \in \mathbb{N}$ with $m \neq n$ we have that $B_m \cap B_n = \emptyset$.
2) $\displaystyle{\bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty} B_n}$.
  • Proof: Let $\mathcal A$ be an algebra on $X$ and let $(A_n)_{n=1}^{\infty}$ be a sequence of sets in $\mathcal A$. Define:
(2)
\begin{align} \quad B_n = \left\{\begin{matrix} A_1 & \mathrm{if} \: n = 1 \\ A_n \setminus \left ( \bigcup_{i=1}^{n-1} A_i \right ) & \mathrm{if} \: n > 1 \end{matrix}\right. \end{align}
  • By the previous proposition it is clear that $B_n \in \mathcal A$ for all $n \in \mathbb{N}$.
  • We begin by showing that the sets in the sequence, $(B_n)_{n=1}^{\infty}$ are mutually disjoint. Let $m, n \in \mathbb{N}$ with $m \neq n$. Assume without loss of generality that $m < n$. Then we have that $B_m$ and $B_n$ assume the following forms:
(3)
\begin{align} \quad B_m = A_m \setminus \left ( \bigcup_{i=1}^{m-1} A_i \right ) \quad , \quad B_n = A_n \setminus \left[ \left ( \bigcup_{i=1}^{m-1} A_i \right ) \cup A_m \cup \left ( \bigcup_{i=m+1}^{n-1} A_i \right ) \right ] \end{align}
  • So no element of $A_m$ is contained in $B_n$ and we have that $A_m \cap B_n = \emptyset$. But clearly $B_m \subseteq A_m$. Therefore $B_m \cap B_n = \emptyset$.
  • We now show that the union of every set in the sequence $(A_n)_{n=1}^{\infty}$ is equal to the union of every set in the sequence $(B_n)_{n=1}^{\infty}$.
  • Let $\displaystyle{x \in \bigcup_{n=1}^{\infty} B_n}$. Then $x \in B_n$ for some $n \in \mathbb{N}$. But $B_n \subseteq A_n$ so $x \in A_n$. So $\displaystyle{x \in \bigcup_{n=1}^{\infty} A_n}$ and hence:
(4)
\begin{align} \quad \bigcup_{n=1}^{\infty} B_n \subseteq \bigcup_{n=1}^{\infty} A_n \end{align}
  • Now let $\displaystyle{x \in \bigcup_{n=1}^{\infty} A_n}$. Then $x \in A_n$ for some $n \in \mathbb{N}$. Let $n$ be the smallest positive integer such that $x \in A_n$. This $n$ is well-defined since $\{ n : x \in A_n \}$ is a nonempty set of positive integers, so by the well-ordering principle, there exists a least $n$.
  • Either $n = 1$ or $n > 1$. If $n = 1$ then $x \in A_1 = B_1$ which implies that $\displaystyle{x \in \bigcup_{n=1}^{\infty} B_n}$. If $n > 1$ then $x \in A_n$ and since $n$ is the least positive integer such that this is true, then $x \not \in A_1, A_2, ..., A_{n-1}$, i.e., $\displaystyle{x \in A_n \setminus \left ( \bigcup_{i=1}^{n-1} A_i \right ) = B_n}$ which implies that $\displaystyle{x \in \bigcup_{n=1}^{\infty} B_n}$. Hence we can conclude that:
(5)
\begin{align} \quad \bigcup_{n=1}^{\infty} A_n = \bigcup_{n=1}^{\infty} B_n \quad \blacksquare \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License