Classes of Subsets
Throughout this discussion, let $S$ be some abstract space, that is with no special structure. Let $2^S$ denote the collection of all subsets of $S$, including the empty set $\emptyset$. The basic aim of measure theory is to assign a “size” to a large class of sets, extending our intuitive idea of the volume, area or length of a finite set or an interval. The problem is that one can find sets for which the notion of such a “size” is poorly defined, so we need to proceed carefully. 1More precisely, we mean that there are sets in $2^S$ that are not measurable in the sense we will make precise shortly. See, for instance, p 93 in Taylor, S. J., Introduction to Measure and Integration (Cambridge University Press, 1966). So $2^S$ is too large for many purposes and it is usual to restrict attention to subclasses of $2^S$. However, it is important that the subclasses considered have sufficient structure, and we now define various types of classes starting with the simplest.
$z$-Classes #
Definition (Semi-ring)
A class $\cS$ of subsets of $S$ is called a semi-ring 2We take the definition from Taylor, “Introduction to Measure and Integration,” 1966 not Von Neumann’s. if
(i) $\emptyset \in \cS$;
(ii) $A, B \in \cS \Rightarrow A \cap B \in \cS$;
(iii) $A, B \in \cS \Rightarrow A \setminus B = \bigcup_{i=1}^n E_i$, where the $E_i$ are disjoint sets in $\cS$.
An important example of a semi-ring of subsets of $\R$ is the class of finite intervals $(a, b]$ which are open on the left and closed on the right. Similarly, the class of rectangles in $\R^n$ of the form $\{ (x_1, x_2, \ldots, x_n): a_i < x_i \le b_i \}$ is a semi-ring in $\R^n$.
Definition (Ring)
A ring is any non-empty class $\cR$ of subsets of $S$ such that
$$ A, B \in \cR \Rightarrow A \cap B \in \cR \text{ and } A \, \triangle \, B \in \cR. $$Since $\emptyset = A \, \triangle \, A, A \cup B = (A \, \triangle \, B) \, \triangle \, (A \cap B)$, and $A \setminus B = A \, \triangle \, (A \cap B)$ we see that a ring is a class of sets closed under the operations of (finite) union, intersection and difference and $\emptyset \in \cR$. Thus a ring is certainly also a semi-ring. As examples, the system $\{ \emptyset, S \}$ is a ring as is the class $2^S$. However, the class of half-open intervals in $\R$ is not a ring, for it is not closed under the operation of symmetric difference.
Definition ($\sigma$-ring)
A ring $\cR$ is called a $\sigma$-ring if, in addition, it is closed under countable unions, i.e. if
$$ A_i \in \cR \Rightarrow \bigcup_{i=1}^\infty A_i \in \cR. $$Denote by $A^c := S \setminus A$. De Morgan’s Rule gives us $\bigcap_{i=1}^\infty A_i = (\bigcup_{i=1}^\infty A_i^c )^c \in \cR$ which shows that a $\sigma$-ring is also closed under countable unions.
Félix Édouard Justin Émile Borel (1925-1936).
Borel is credited with introducing countable additivity (often called denumerable additivity at the time) in his foundational work on measure theory Leçons sur la théorie des fonctions (1898). [Autochrome colour portrait, 1918]
Auguste Léon (Public Domain).
Definition (Algebra)
So a ring is an algebra if and only if it is closed under the operation of taking the complement. The class of all finite subsets of a space $S$ is a ring, but it is not an algebra unless $S$ is finite. 3Precisely, $\cR = \{ A \subset S \mid A \text{ is finite} \}$ is an algebra if and only if $S$ is finite. $(\Leftarrow)$ If $S$ is a finite set, then every subset of $S$ is finite. Consequently, the class of all finite subsets $\mathcal{R}$ is simply the power set $2^S$ which is clearly an algebra. $(\Rightarrow)$ By definition, if $\cR$ is an algebra, $S$ belongs to $\cR$ and must be finite by definition. In $\R$ the class of all bounded subsets is a ring but not an algebra, since it does not contain $\R$.
Definition ($\sigma$-algebra)
For any space $S$, the class of all countable subsets is a $\sigma$-ring, but is only a $\sigma$-field if $S$ is countable.
Proposition
Consider the class $\Field \subset 2^S$ with the following properties:
(i) $\emptyset \in \Field$ and $S \in \Field$
(ii) if $A \in \Field$, then $A^c = S \setminus A \in \Field$
(iii) if $A_1, A_2 \in \Field$, then $A_1 \cup A_2 \in \Field$
(iv) if $A_1, A_2, \ldots \in \Field$, then $\bigcup_{j=1}^\infty A_j \in \Field$.
The class $\Field$ is an algebra if and only if it satisfies conditions (i), (ii) and (iii). It is a $\sigma$-algebra if and only if it satisfies (i), (ii) and (iv).
Given (ii), condition (i) can be replaced by either (i’): $\emptyset \in \Field$ or by (i’’): $S \in \Field$.
Note also that (i) & (iv) implies (iii), hence any $\sigma$-algebra is an algebra (but there algebras that are not $\sigma$-algebras). 4See Example $\ref{ex:algebra}$ (iii) and (iv).
Moreover, (ii) and De Morgan’s Rule shows that (ii) can be replaced by (iii’): if $A_1, A_2 \in \Field$, then $A_1 \cap A_2 \in \Field$ and similarly (iv) by (iv’): if $A_1, A_2, \ldots \in \Field$, then $\bigcap_{j=1}^\infty A_j \in \Field$.
Example
A few examples of algebras and $\sigma$-algebras:
(i) for any set $S$, the trivial $\sigma$-algebra $\{ \emptyset, S \}$ and the power set $2^S$ are both $\sigma$-algebras of S.
(ii) If $A$ is a subset of $S$, then $\{\emptyset, A, A^c, S \}$ is a $\sigma$-algebra on $S$.
(iii) Let $\cJ$ consist of all sets of the form $\{ (a, b] : -\infty \le a \le b < \infty \}$ or $\{ (b, \infty) : -\infty \le b < \infty \}$ and suppose $\Sigma_\cJ$ is the collection of all finite (disjoint) unions of sets in $\cJ$. Then $\Sigma_\cJ$ is an algebra of subsets of $\R$ (but not a $\sigma$-algebra). 5This is easy to verify by considering the half-open intervals $A_n = (0, 1 - \frac{1}{n}]$ whose countable union is $(0,1) \notin \Sigma_\cJ$.
(iv) Let $S$ be an infinite set (countable or not) and let $\cA$ be the family of all subsets which are either finite or have a finite complement. It is easy to check that $\cA$ is an algebra. However, it is not a $\sigma$-algebra. To verify this, take any countably infinite subset $\{x_1, x_2, \ldots \} \subset S$ and let $\{A_n\} := \{x_n\}$. Consider \[A = \bigcup_{n=1}^\infty = {x_1, x_2, \ldots }\] Since neither $A$ nor $A^c$ is finite, $A \notin \cA$ and $\cA$ is not a $\sigma$-algebra. 6This example comes from Exercise 2.17 in Jacod and Protter, “Probability Essentials,” 2004.
We use the term $z$-class 7We follow Taylor, “Introduction to Measure and Integration,” 1966 in this regard. to denote any one of the class types defined in Definitions $\ref{def.ring}$, $\ref{def.sigring}$, $\ref{def.alg}$, $\ref{def.sigalg}$, and $\ref{def.mc}$ (but, importantly, not a semi-ring), and we consider a collection of $z$-classes $\{ \cC_i\}_{i \in I}$ for some (possibly uncountable) index set $I$.
Lemma
Note that the intersection of semi-rings need not be a semi-ring. To see this consider two semi-rings $\cS_1$ and $\cS_2$. Even though $A \setminus B$ can be partitioned into sets from $\cS_1$ and separately partitioned into sets from $\cS_2$, there is no guarantee that there exists a single disjoint partition whose pieces all simultaneously belong to the intersection $\cS_1 \cap \cS_2$. For an explicit example, consider
- $\cS_1 = \{\emptyset, \{1\}, \{2, 3\}, \{1, 2, 3\}\}$
- $\cS_2 = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 2, 3\}\}.$
Their intersection is
$$\cS_1 \cap \cS_2 = \{\emptyset, \{1\}, \{1, 2, 3\}\}. $$But clearly $A \setminus B = \{2, 3\}$ cannot be formed as a disjoint union of sets from $\cS_1 \cap \cS_2$, so the intersection is not a semi-ring.
Definition
Remark
It is often important to see the interaction between $z$-classes and the topology of a set which models the intuitive concept of “openness”.
Definition
A topology of a set $S$ is a collection $\fT$ of subsets of $S$ satisfying:
(i) $\emptyset \in \fT$ and $S \in \fT$,
(ii) if $U_i \in \fT$, for all $i$ in some (possibly uncountable) index set $I$, then $\bigcup_{i \in I} U_i \in \fT$,
(iii) if $N \in \N$ and $\{U_i\}_{i=1}^N \subset \fT$, then $\bigcap_{i=1}^N U_i \in \fT$. 8Intersections are restricted to finite collections in the definition being inspired by the fact that the countable intersection of open sets in $\Reals$ can be closed. E.g. $\bigcap_{n=1}^\infty \left(-\frac{1}{n}, \frac{1}{n}\right) = \{0\}$.
The pair $(S, \fT)$ is called a topological space and the elements of $\fT$ are called the open subsets in $(S, \fT)$.
Example
Definition
Theorem
Every open set $U \subset \Reals^n$ is a countable union of open rectangles
$$R = \prod_{i=1}^n (a_i, b_i) = (a_1, b_1) \times (a_2, b_2) \times \dots \times (a_n, b_n).$$Proof. Let $\cC_\Q$ be the collection of all rational rectangles in $\Reals^n$. Since each rectangle is defined by $2n$ rational numbers $(a_1, b_1, a_2, b_2, \dots, a_n, b_n) \in \mathbb{Q}^{2n}$, $\cC_\Q$ is a countable family of sets.
Step 1. Show that $\cC_\Q$ forms a topological base. The aim is to prove that for any open set $U \subset \mathbb{R}^n$ and any point $x \in U$, there exists a rational rectangle $R \in \cC_\Q$ such that $x \in R \subset U$.
- Local ball enclosure. Since $U$ is open, there exists an open Euclidean ball centered at $x$ with radius $\varepsilon > 0$ such that $B(x, \varepsilon) \subset U$.
- Coordinate box. We can enclose $x$ in a smaller open box aligned with the coordinate axes, $V = \prod_{i=1}^n (x_i - \delta, x_i + \delta)$, chosen small enough (e.g., $\delta = \frac{\varepsilon}{2\sqrt{n}}$) such that $V \subset B(x, \varepsilon)$.
- Rational density. By the density of $\mathbb{Q}$ in $\mathbb{R}$, for each coordinate $i$, we can find rational endpoints $a_i, b_i \in \mathbb{Q}$ satisfying $$ x_i - \delta < a_i < x_i < b_i < x_i + \delta. $$
- Construct base element. Let $R = \prod_{i=1}^n (a_i, b_i)$. By construction $R \subset V \subset B(x, \varepsilon) \subset U$.
Step 2. Construct the countable union. The aim is to show that the representation $U = \bigcup_{k=1}^\infty R_k$ is possible for arbitrary open sets $U$.
- Consider the sub-family of our countable base consisting of all rational rectangles entirely contained within $U$: $$\cC_\Q^U = \{ R \in \cC_\Q : R \subset U \}.$$
- By definition $\cC_\Q^U \subset \cC_\Q$, so $\cC_\Q^U$ is at most countable and its elements are denumerable: $$ \cC_\Q^U = \{ R_1, R_2, R_3, \dots \}. $$
- We now verify that $U = \bigcup_{k=1}^\infty R_k$ for the $R_1, R_2, \ldots$ belonging to $\cC_\Q^U$.
- $(\supset)$ Since every $R_k \in \cC_\Q^U$ is defined such that $R_k \subset U$, their union must also be a subset of $U$: $$\bigcup_{k=1}^\infty R_k \subset U.$$
- $(\subset)$ Let $x$ be an arbitrary point in $U$. By Step 1, there exists some rational rectangle $R \in \cC_\Q$ such that $x \in R \subset U$. Because $R \subset U$, $R$ automatically belongs to $\cC_\Q^U$. Therefore: $$x \in R \subset \bigcup_{R' \in \cC_\Q^U} R' = \bigcup_{k=1}^\infty R_k$$Thus, $U \subset \bigcup_{k=1}^\infty R_k$. ■
Theorem
Proof. Let $\cC$ denote all the open rectangles in $\R^n$. Since every open set in $\R^n$ is the countable union of open rectangles (Theorem $\ref{thm:countablerect}$), we have $\sigma(\cC) = \cB(\R^n)$.
Let $(a_1, b_1) \times \ldots \times (a_n, b_n) \in \cC$ and let $(\alpha_1^m, \ldots, \alpha_n^m)_{m \ge 1}$ be a sequence of rational vectors whose components decrease to $(a_1, \ldots, a_n)$ and $(\beta_1^m, \ldots, \beta_n^m)_{m \ge 1}$ a sequence of rational vectors whose components increase strictly to $(b_1, \ldots, b_n)$. Then
$$ \begin{aligned} (a_1, b_1) \times \ldots \times (a_n, b_n) &= \bigcup_{m=1}^\infty (\alpha_1^m, \beta_1^m] \times \ldots \times (\alpha_n^m, \beta_n^m] \\ &= \bigcup_{m=1}^\infty \big( (-\infty, \beta_1^m] \cap (-\infty, \alpha_1^m]^c \big) \times \ldots \times \big( (-\infty, \beta_n^m] \cap (-\infty, \alpha_n^m]^c \big) \\ &= \bigcup_{m=1}^\infty \big( (-\infty, \beta_1^m] \times \ldots \times (-\infty, \beta_n^m] \big) \cap \big( (-\infty, \alpha_1^m]^c \times \ldots \times (-\infty, \alpha_n^m]^c \big). \end{aligned} $$Therefore $\cC \subset \sigma(\cD)$, whence $\sigma(\cC) \subset \sigma(\cD)$. However, since each element of $\cD$ is a closed set, it is also a Borel set, and therefore $ \cB(\R^n) = \sigma(\cC) \subset \sigma(\cD) \subset \cB(\R^n). $ ■
Corollary
Monotone Class Theorems 12See also presentation from He, Wang and Yan, “Semimartingale Theory and Stochastic Calculus,” 1992. #
Monotone class theorems constitute one of the most useful tools in measure theory. These theorems, though technical in nature, simplify some proofs considerably, as they allow us to take any desired property that is readily verified for a small class of sets or functions (i.e. a “monotone class’) and then extend it to a larger class generated by the smaller one (e.g. a $\sigma$-algebra generated by the monotone class).
Definition (Monotone Class)
A class $\cM$ of subsets such that, for any monotone sequence $\{ A_n \}$ of sets in $\cM$ we have $\lim_{n \rightarrow \infty} A_n \in \cM$ is called a monotone class. More precisely, $\cM$ is a monotone class if $A \in \cM$ whenever $\{ A_n \}_{n \in \N}$ is a sequence of sets in $\cM$ with either:
(i) $A_n \subset A_{n+1}$ and $\bigcup_{n=0}^\infty A_n = A$, or
(ii) $A_n \supset A_{n+1}$ and $\bigcap_{n=0}^\infty A_n = A$.
Remark
It is clear that a $\sigma$-ring is a monotone class, and any monotone class which is a ring is also a $\sigma$-ring since
$$ A_i \in \cM \Rightarrow \bigcup_{i=1}^n A_i \in \cM, $$and $\bigcup_{i=1}^n A_i$ is monotone so that $\bigcup_{i=1}^\infty A_i = \lim_{n \rightarrow \infty} \bigcup_{i=1}^n A_i \in \cM$.
Theorem (Monotone Class Theorem)
Corollary
Proof. Denote the $\sigma$-ring generated by $\cR$ by $\rho(\cR)$. Since a $\sigma$-ring is always a monotone class (Remark $\ref{rem.1}$) and (by definition) $\rho(\cR) \supset \cR$, we must have $\rho(\cR) \supset \cM(\cR)$. Hence it is sufficient to show that $\cM(\cR)$ is a $\sigma$-ring, and by Remark $\ref{rem.1}$ this will follow if we can prove that $\cM(\cR)$ is a ring.
For any set $F \subset S$, let $\bM(F)$ be the class of sets $E \in \cM(\cR)$ for which $E \setminus F$, $F \setminus E$, $E \cup F$ are all in $\cM(\cR)$. It is clear that the construction of $\bM(F)$ filters sets out of $\cM(\cR)$ so $\bM(F) \subset \cM(\cR)$. More explicitly,
$$ \bM(F) := \{ E \in \cM(\cR) : E \setminus F, F \setminus E \text{ and } E \cup F \in \cM(\cR) \} \subset \cM(\cR). $$If $\bM(F)$ is not empty it is obviously a monotone class. 13How do we know that $\bM(F)$ is not empty? By construction, it is clear that $\bM(F) \supset \cR$ for any $F \in \cR$ so that $\bM(F) \supset \cM(\cR)$ since $\cM(\cR)$ is the smallest monotone class containing $\cR$. Hence $\bM(F) = \cM(\cR)$ for any $F \in \cR$.
So for any $E \in \cM(\cR)$ and $F \in \cR$ then $E \in \bM(F)$ and, by symmetry of the class $\bM$, $F \in \bM(E)$. Fixing an $E \in \cM(\cR)$, we have $\cR \subset \bM(E)$ from which it follows that $\cM(\cR) = \bM(E)$ since $\bM(E)$ is a monotone class. That this argument is “short” for every $E \in \cM(\cR)$ establishes that $\cM(\cR)$ is a ring. ■
Remark
Remark
A closely related result, sometimes also referred to as the monotone class theorem, is due to Dynkin.
Definition
Lemma
Proof. Clearly every $\sigma$-algebra is both a $\pi$-system and a $\lambda$-system. To prove the converse, we only need to prove that $\cK$ is closed under countable unions of not necessarily increasing sets whenever $\cK$ is a $\pi$-system and a $\lambda$-system. For any $A, B \in \cK$, we know that $A \cup B = S \ (A^c \cap B^c) \in \cK$. Hence for any $\{A_n\}_{n \in \N} \subset \cK$ the sequence $B_n := \bigcup_{k \le n} A_k$ satisfies $B_n \subset B_{n+1}$, and so
$$ \bigcup_{n \in \N} A_n = \bigcup_{n \in \N} B_n \in \cK, $$so $\cK$ is a $\sigma$-algebra. ■
Theorem (Dynkin's $\pi$-$\lambda$ Lemma)
Proof. 14See Cohen, “Stochastic Calculus and Applications,” 2015 for a sketch of a proof Appendix A.1 in Durrett Durrett, “Probability: Theory and Examples,” 2010 for a more detailed proof.
■
We can also state the following function-space version of the monotone class theorem.
Theorem
Suppose $\cH$ is a real vector space of $\R$-valued, bounded functions defined on $\Omega$, such that
(i) $\cH$ contains the constant functions,
(ii) $\cH$ is closed under uniform convergence, and
(iii) for every uniformly bounded increasing sequence $\{ f_n \}_{n \in \N} \subset \cH$ of positive functions the limit $f = \lim_{n \rightarrow \infty} f_n$ is in $\cH$.
Suppose $\cC \subset \cH$ which is closed under multiplication and, as usual, write $\sigma(\cC)$ for the $\sigma$-algebra on $\Omega$ generated by $\cC$ (i.e. the smallest $\sigma$-algebra such that $f$ is measurable for every $f \in \cC$. Then $\cH$ contains all bounded $\sigma(\cC)$-measurable function.
Proof.
15Finish the proof looking at Section 7.4 in Cohen, “Stochastic Calculus and Applications,” 2015.
■
Remark