Let \(X\) be a nonempty set, and let \(\mathcal P(X)\) be its power set.
Algebra. An algebra of sets on \(X\) is a collection \(\mathcal{A}\subseteq\mathcal P(X)\) that satisfies
\(\mathcal{A} \neq \varnothing\).
If \(E \in \mathcal{A}\), then \(E^c \in \mathcal{A}\) (closed under complements).
If \(E_1,E_2,\ldots,E_N \in \mathcal{A}\), then \(\bigcup_{j=1}^{N}E_j \in \mathcal{A}\) (closed under finite unions).
Example. \(\mathcal{A}=\{\varnothing, X, E,E^c\}\) is an algebra.
\(\sigma\)-Algebra. A \(\sigma\)-algebra of sets on \(X\) is a collection \(\mathcal{A}\subseteq \mathcal P(X)\) that satisfies
\(\mathcal{A} \neq \varnothing\).
If \(E \in \mathcal{A}\), then \(E^c \in \mathcal{A}\), (closed under complements).
If \(E_1,E_2,\ldots \in \mathcal{A}\), then \(\bigcup_{j=1}^{\infty}E_j \in \mathcal{A}\), (closed under infinite unions).
The pair \((X, \mathcal A)\) is then called a measurable space.
Examples.
If \(X\) is any set then \(\{\varnothing, X\}\) and \(\mathcal{P}(X)\) are \(\sigma\)-algebras.
If \(X\) is uncountable, then \[\mathcal{A}=\{E \subseteq X: E \text{ is countable or } E^c \text{ is countable}\}\] is \(\sigma\)-algebra of countable and co-countable sets.
Algebras (resp. \(\sigma\)-algebras) are also closed under finite (resp. countable) intersections, since \(\big(\bigcup_{j=1}^{\infty}E_j\big)^{c}=\bigcap_{j=1}^{\infty} E_j^{c}\).
If \(\mathcal{A}\) is an algebra, then \(\varnothing \in \mathcal{A}\) and \(X\in \mathcal{A}\). Take \(E \in \mathcal{A}\neq\varnothing\), then \(E^c \in \mathcal{A}\), and consequently \(\varnothing=E \cap E^c \in \mathcal{A}\) and \(X=E \cup E^c \in \mathcal{A}\).
An algebra \(\mathcal{A}\) is a \(\sigma\)-algebra provided it is closed under countable disjoint unions. Indeed, let \(F_1=E_1\) and \[F_k=E_k \setminus \bigg(\bigcup_{j=1}^{k-1}E_{j}\bigg)=E_k \cap \bigg(\bigcup_{j=1}^{k-1}E_j\bigg)^c \quad \text{ for any } \quad k\in\mathbb N.\] Then the \(F_k\)’s belong to \(\mathcal{A}\) and are disjoint, and \[\bigcup_{j=1}^{\infty}E_j=\bigcup_{j=1}^{\infty}F_j.\]
The intersection of any family of \(\sigma\)-algebras on \(X\) is again a \(\sigma\)-algebra.
\(\sigma\)-algebra generated by \(\mathcal{E}\). If \(\mathcal{E} \subseteq\mathcal{P}(X)\), then \[\sigma(\mathcal{E})=\bigcap_{\substack{\mathcal{A} \supseteq \mathcal{E}\\ \mathcal{A}\text{ is a }\sigma\text{-algebra}}}\mathcal A\] is the smallest \(\sigma\)-algebra containing \(\mathcal{E}\).
\(\sigma(\mathcal{E})\) is called the \(\sigma\)-algebra generated by \(\mathcal{E}\) and is unique.
Example. The family \(\mathcal{E} = \{\{x\}: x \in X\}\) generates \[\sigma(\mathcal E)=\{E \subseteq X: E \text{ is countable or } E^c \text{ is countable}\}.\]
Lemma. If \(\mathcal{E} \subseteq \sigma(\mathcal{F})\), then \(\sigma(\mathcal{E})\subseteq \sigma(\mathcal{F})\).
Proof. We know that \[\sigma(\mathcal{E})=\bigcap_{\substack{\mathcal{A} \supseteq \mathcal{E}\\ \mathcal{A}\text{ is a }\sigma\text{-algebra}}}\mathcal A \subseteq \sigma(\mathcal{F})\]
It is also easy to see that \(\sigma(\mathcal E)=\sigma(\sigma(\mathcal E))\). Indeed, \[\sigma(\sigma(\mathcal{E}))=\bigcap_{\substack{\mathcal{A} \supseteq \sigma(\mathcal{E})\\ \mathcal{A}\text{ is a }\sigma\text{-algebra}}}\mathcal A \subseteq \sigma(\mathcal{E})\subseteq \sigma(\sigma(\mathcal{E})).\]
Borel sets. If \(X\) is any metric space, or more generally any topological space, the \(\sigma\)-algebra generated by the family of open sets in \(X\) (or, equivalently, by the family of closed sets in \(X\)) is called the Borel \(\sigma\)-algebra on \(X\) and is denoted by \[{\rm Bor}(X) \subseteq\mathcal P(X).\] Its members are called Borel sets.
\(F_{\sigma}\) and \(G_{\delta}\) sets.
A countable intersection of open sets is called a \(G_{\delta}\) set.
A countable union of closed sets is called an \(F_{\sigma}\) set.
A countable union of \(G_{\delta}\) set is called a \(G_{\delta \sigma }\) set.
A countable intersection of \(F_{\sigma}\) sets is called an \(F_{\sigma \delta}\) sets.
Problem 1. Prove that \({\rm Bor}(\mathbb{R})\) is generated by each of the following:
the open intervals: \(\mathcal{E}_1=\{(a,b): a<b\};\)
the closed intervals: \(\mathcal{E}_2=\{[a,b]: a<b\};\)
the half-open intervals: \[\mathcal{E}_3=\{(a,b]: a<b\} \quad \text{ or } \quad \mathcal{E}_4=\{[a,b): a<b\};\]
the open rays: \[\mathcal{E}_5=\{(a,\infty): a \in \mathbb{R}\} \quad \text{ or } \quad \mathcal{E}_6=\{(-\infty,a): a \in \mathbb{R}\};\]
the closed rays: \[\mathcal{E}_7=\{[a,\infty): a \in \mathbb{R}\} \quad \text{ or } \quad \mathcal{E}_8=\{(-\infty,a]: a \in \mathbb{R}\}.\]
Definition of the product \(\sigma\)-algebra. Let \((X_{\alpha})_{\alpha \in A}\) be an indexed collection of nonempty sets, \(X=\prod_{\alpha \in A}X_{\alpha}\), and \(\pi_{\alpha}:X \to X_{\alpha}\) the coordinate maps. If \(\mathcal{A}_{\alpha}\) is a \(\sigma\)-algebra on \(X_{\alpha}\) for each \(\alpha\in A\), the product \(\sigma\)-algebra on \(X\) is the \(\sigma\)-algebra generated by \[\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\}.\] We denote this \(\sigma\)-algebra by \(\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}\). In other words, \[\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha} =\sigma\left(\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\}\right).\] If \(A=\{1,\ldots,n\}\), we write \(\mathcal{A}_1 \otimes \mathcal{A}_2 \otimes \ldots \otimes \mathcal{A}_n\).
Proposition . If \(A\) is countable, then \(\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}\) is the \(\sigma\)-algebra generated by \[\big\{\prod_{\alpha \in A}E_{\alpha}: E_{\alpha}\in \mathcal{A}_{\alpha}\big\}.\]
Proof. Let \[\mathcal{E}=\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\},\] and \[\mathcal{F}=\big\{\prod_{\alpha \in A}E_{\alpha}: E_{\alpha }\in \mathcal{A}_{\alpha}\big\}.\] By the definition \(\sigma(\mathcal{E})=\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}\).
We first show that \(\mathcal{E} \subseteq \mathcal{F} \subseteq\sigma(\mathcal{F})\), this will imply \(\sigma(\mathcal{E}) \subseteq \sigma(\mathcal{F})\).
Indeed, if \(\pi_{\alpha}^{-1}[E_{\alpha}] \in \mathcal{E}\) for some \(\alpha\in A\) and \(E_{\alpha}\in\mathcal A_{\alpha}\), then \[\pi_{\alpha}^{-1}[E_{\alpha}]=\prod_{\beta \in A}E_{\beta},\] where \(E_{\beta}=X_{\beta}\) for \(\alpha \neq \beta\). Thus \(\pi_{\alpha}^{-1}[E_{\alpha}] \in \mathcal{F}\) as desired.
We now show that \(\sigma(\mathcal{F}) \subseteq \sigma(\mathcal{E})\). Is suffices to prove that \(\mathcal{F} \subseteq \sigma(\mathcal{E})\). Note that \[\mathcal{F} \ni \prod_{\alpha \in A}E_{\alpha}=\bigcap_{\alpha \in A}\pi_{\alpha}^{-1}[E_{\alpha}] \in \sigma(\mathcal{E}).\] The fact that \(A\) is countable, is essential in the argument.
Proposition. Suppose that \(\mathcal{A}_{\alpha}=\sigma(\mathcal E_{\alpha})\) for any \(\alpha \in A\). Then \(\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}\) is generated by \[\mathcal{F}_1=\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{E}_{\alpha}, \ \alpha \in A\}.\] If \(A\) is countable and \(X_{\alpha} \in \mathcal{E}_{\alpha}\) for any \(\alpha \in A\), then \(\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}\) is generated by \[\mathcal{F}_2=\big\{\prod_{\alpha \in A}E_{\alpha}\::\: E_{\alpha} \in \mathcal{E}_{\alpha}\big\}.\]
Proof. We have \[\sigma(\mathcal{F}_1) \subseteq \sigma \left(\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\}\right) =\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}.\] We have to prove that \(\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha} \subseteq \sigma(\mathcal{F}_1)\).
For each \(\alpha \in A\), consider the collection \[\mathcal{G}_{\alpha}=\{E \subseteq X_{\alpha}: \pi_{\alpha}^{-1}[E] \in \sigma(\mathcal{F}_1)\}.\]
By the definition of \(\mathcal F_1\) we have \(\mathcal{E}_{\alpha}\subseteq \mathcal{G}_{\alpha}\), since \[\pi_{\alpha}^{-1}[E] \in \sigma(\mathcal{F}_1)\] for all \(E \in \mathcal{E}_{\alpha}\) and \(\alpha \in A\).
One can easily show that \(G_{\alpha}\) is a \(\sigma\)-algebra on \(X_\alpha\). Why?
Hence \(\mathcal{G}_{\alpha}\) is a \(\sigma\)-algebra containing \(\mathcal{E}_{\alpha}\) thus \(\mathcal{A}_{\alpha}=\sigma(\mathcal{E}_{\alpha}) \subseteq \mathcal{G}_{\alpha}\) for all \(\alpha \in A\), so \(\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\}\subseteq \sigma(\mathcal{F}_1)\) and consequently \[\bigotimes_{\alpha \in A}\mathcal{A}_{\alpha}=\sigma \left(\{\pi_{\alpha}^{-1}[E_{\alpha}]: E_{\alpha} \in \mathcal{A}_{\alpha}, \ \alpha \in A\}\right) \subseteq \sigma(\mathcal{F}_1)\] as claimed.
Problem 2. Let \(N\in\mathbb N\) and \(X_1,\ldots,X_N\) be metric spaces and let \(X=\prod_{j=1}^{N}X_j\) be equipped with the product metric. Then show that \[\bigotimes_{j=1}^{N}{\rm Bor}(X_j) \subseteq {\rm Bor}(X).\] If the \(X_j\)’s are separable, then prove that \[\bigotimes_{j=1}^{N}{\rm Bor}(X_j) = {\rm Bor}(X).\] What can be said if \(N=\infty\)?
Semi-algebras. A semi-algebra of sets on \(X\) is a collection \(\mathcal{I}\subseteq \mathcal P(X)\) such that
\(\varnothing \in \mathcal{I}\),
if \(E,F \in \mathcal{I}\), then \(E \cap F \in \mathcal{I}\),
if \(E \in \mathcal{I}\), then \(E^c\) is a finite disjoint union of members of \(\mathcal{I}\).
Examples.
A family containing \(\varnothing\), \(\mathbb R\) and all closed-open intervals \([a, b)\) with \(-\infty\le a<b\le \infty\) is a semi-algebra.
A family containing \(\varnothing\), \(\mathbb R\) and all open-closed intervals \((a, b]\) with \(-\infty\le a<b\le \infty\) is a semi-algebra.
If we consider two measurable spaces \((X, \mathcal A)\) and \((Y, \mathcal B)\) then the set \(\mathcal A\times \mathcal B=\{A\times B: A\in \mathcal A \text{ and } B\in\mathcal B\}\) is a semi-algebra.
Proposition. If \(\mathcal{I}\) is a semi-algebra, the collection \(\mathcal{A}\) of finite disjoint unions of members of \(\mathcal{I}\) is an algebra.
Proof. If \(A,B \in \mathcal{A}\) we first show that \(A \cup B \in \mathcal{A}\). Note that \[B^c=\bigcup_{j=1}^JC_j,\] where \(C_j \in \mathcal{I}\) are disjoint. Then \[A \setminus B=\bigcup_{j=1}^{J}A \cap C_j \in \mathcal{A},\] thus \(A \cup B=(A \setminus B) \cup B \in \mathcal{A}\).
By induction one can easily show that if \(A_1,A_2,\ldots,A_n \in \mathcal{A}\), then \[\bigcup_{j=1}^{n}A_j \in \mathcal{A}.\]
We now show that if \(A \in \mathcal{A}\), then \(A^c \in \mathcal{A}\). If \(A \in \mathcal{A}\), then it can be represented as a disjoint union of the elements from \(\mathcal{I}\), i.e. \[A=A_1 \cup A_2 \cup \ldots \cup A_n,\]
where \(A_1,A_2, \ldots,A_n \in \mathcal{I}\) and \[A_m^c=\bigcup_{j=1}^{J_m}B_{m}^{j}\] for every \(m\in\{1,2,\ldots,n\}\) with disjoint members \(B_{m}^{1},\ldots, B_{m}^{J_m}\) of \(\mathcal{I}\).
Finally, one sees that \[\begin{align*} A^c&=\bigg(\bigcup_{m=1}^{n}A_m\bigg)^c\\ &=\bigcap_{m=1}^{n}A_m^c\\ &=\bigcap_{m=1}^{n}\bigcup_{j=1}^{J_m}B_m^j\\&=\bigcup_{j_1=1}^{J_1}\bigcup_{j_2=1}^{J_2}\cdots \bigcup_{j_n=1}^{J_n}\left(B^{j_1}_{1} \cap B_{2}^{j_2} \cap \ldots \cap B_{n}^{j_n}\right), \end{align*}\] where the last sum is disjoint. Thus \(\mathcal{A}\) is an algebra as claimed.
Let \(J_o\) be the collection of all open intervals in \(\mathbb{R}\): \[J_o=\{(a,b): -\infty \leq a<b \leq \infty\} \cup \{\varnothing\}.\]
Let \(J_{co}\) be the collection of all closed-open intervals in \(\mathbb{R}\): \[J_{co}=\{[a,b): -\infty \leq a<b \leq \infty\} \cup \{\varnothing\}.\]
Let \(J_{oc}\) be the collection of all open-closed intervals in \(\mathbb{R}\): \[J_{oc}=\{(a,b]: -\infty \leq a<b \leq \infty\} \cup \{\varnothing\}.\]
Let \(J_{c}\) be the collection of all closed intervals in \(\mathbb{R}\): \[J_c=\{[a,b]: -\infty \leq a<b \leq \infty\} \cup \{\varnothing\}.\]
Let \(J=J_o \cup J_{oc} \cup J_{co} \cup J_c\) be the collection of all intervals in \(\mathbb{R}\).
Finally, we define the family of all rectangles by \[\begin{align*} J^d=J_o^d \cup J_{oc}^d \cup J_{co}^d \cup J^d_c, \end{align*}\] where \[J_{\ell}^d=\{E_1 \times \ldots \times E_d: E_1,\ldots, E_d\in J_{\ell}\}\quad \text{ for } \quad \ell\in\{o, oc, co, c\}.\]
In other words, \(J_o^d, J_{oc}^d, J_{co}^d, J^d_c\), are, respectively, the families of open, open-closed, closed-open, and closed rectangles in \(\mathbb R^d\).
Problem 3. Show that both \(J_{oc}^d\) and \(J_{co}^d\) are semi-algebras.
Problem 4. Let \(X\) and \(Y\) be sets and let \(f:X \to Y\) be a function.
Let \(\Sigma\) be a \(\sigma\)-algebra of subsets of \(X\). Show that \[\{F \subseteq Y: f^{-1}[F] \in \Sigma\}\] is a \(\sigma\)-algebra of subsets of \(Y\).
Let \(\Sigma\) be a \(\sigma\)-algebra of subsets of \(Y\). Show that \(\{f^{-1}[F]: F \in \Sigma\}\) is a \(\sigma\)-algebra of subsets of \(X\).
Problem 5. Let \(X\) be a set and \(\mathcal{E} \subseteq \mathcal P(X)\). Suppose that \(Y\) is another set and \(f:Y \to X\) a function. Show that \(\{f^{-1}[E]: E \in \sigma(\mathcal{E})\}\) is the \(\sigma\)-algebra of subsets of \(Y\) generated by \(\{f^{-1}[E]: E \in \mathcal{E}\}\).
Problem 6. Show that the Borel \(\sigma\)-algebra \({\rm Bor}(X)\) of a metric space \(X\) equals the smallest family \(\mathcal{B} \subseteq \mathcal P(X)\) that contains
all open subsets of \(X\) and is closed under countable intersections and countable unions;
all closed subsets of \(X\) and is closed under countable intersections and countable unions;
all open subsets of \(X\) and is closed under countable intersections and countable disjoint unions.
Monotone class. A collection \(\mathcal{M} \subseteq \mathcal P(X)\) is called a monotone class if
whenever \((E_n)_{n \in \mathbb N} \subseteq \mathcal{M}\) and \(E_1 \supseteq E_2 \supseteq \ldots\), then \(\bigcap_{n=1}^{\infty}E_n \in \mathcal{M}\), (closed under nonincreasing intersections)
whenever \((E_n)_{n \in \mathbb N} \subseteq \mathcal{M}\) and \(E_1 \subseteq E_2 \subseteq \ldots\), then \(\bigcup_{n=1}^{\infty}E_n \in \mathcal{M}\), (closed under nondecreasing unions).
Problem 7. Prove that the intersection of all monotone classes containing \(\mathcal E\subseteq \mathcal P(X)\) is a unique smallest monotone class containing \(\mathcal E\).
Problem 8. Show that if \(\mathcal{A}\) is an algebra on \(X\), then the smallest monotone class containing \(\mathcal{A}\) equals \(\sigma(\mathcal{A})\).
Let \(\mathcal{E}=\{E_1,\ldots,E_n\}\) be a finite collection of distinct, but not necessarily disjoint, subsets of \(X\). Let \(\mathcal{D}\) be the collection of all subsets of \(X\) of the form \[F_1 \cap \ldots \cap F_n, \quad \text{ where } \quad F_i \in \{E_i, E_i^c\} \ \text{ for each } \ i\in\{1,\ldots,n\},\] and let \(\mathcal{U}\) be the collection of all finite unions of members of \(\mathcal{D}\), where the empty union is understood to be \(\varnothing\).
Problem 9.
Show that \(\mathcal{D}\) has at most \(2^n\) distinct members.
Show that \(\sigma(\mathcal{E})=\mathcal{U}\).
Show that \(\mathcal{U}\) has at most \(2^{2^n}\) distinct members.
Problem 10. Let \(\mathcal{M}\) be an infinite \(\sigma\)-algebra. Show that
\(\mathcal{M}\) contains an infinite sequence of nonempty pairwise disjoint sets;
\({\rm card}(\mathcal{M}) \geq \mathfrak{c}\).
Problem 11. Let \(\mathcal{A}\) be a \(\sigma\)-algebra on \(X\) and suppose that a set \(S \subseteq X\) does not belong to \(\mathcal{A}\). Show that \(\sigma(\mathcal{A} \cup \{S\})=\{(A \cap S) \cup (B \cap S^c): A,B \in \mathcal{A}\}.\)
Problem 12. Let \(\mathcal{E} \subseteq \mathcal P(X)\) and let \(\mathcal{M}=\sigma(\mathcal{E})\). Show that
\[\mathcal{M}=\bigcup_{\substack{\mathcal{F} \subseteq \mathcal{E}\\ \mathcal{F} \text{ is countable}}}\sigma(\mathcal{F}).\] (Hint: show that the right-hand side is a \(\sigma\)-algebra.)
Let \(X\) be a nonempty set.
\(\pi\)-system. A collection \(\Pi \subseteq \mathcal P(X)\) is a \(\pi\)-system of subsets of \(X\) if it satisfies
\(\Pi \neq \varnothing\),
if \(A,B \in \Pi\), then \(A \cap B \in \Pi\).
\(\lambda\)-system. A collection \(\Lambda \subseteq \mathcal P(X)\) is a \(\lambda\)-system of subsets of \(X\) if it satisfies
\(X \in \Lambda\),
if \(A,B \in \Lambda\) and \(A \subseteq B\), then \(B \setminus A \in \Lambda\),
if \((A_n)_{n \in \mathbb N} \subseteq \Lambda\) and \(A_1 \subseteq A_2 \subseteq \ldots\), then \(\bigcup_{n=1}^{\infty}A_n \in \Lambda\).
Problem 13. Show that if \(\mathcal{D}\) is a \(\lambda\)-system containing a \(\pi\)-system \(\mathcal{A}\), then \(\sigma(\mathcal{A}) \subseteq \mathcal{D}\).