Set Theory
Overview
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$.
Classes of Subsets #
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.
Semi-ring #
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 who first defined the concept. 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$.
Example (Half-open intervals)
Example (Half-open rectangles)
Ring #
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. $$Equivalently, 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 such that $\emptyset \in \cR$ which is also closed under the operations of (finite)
- union,
- intersection and
- difference.
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 difference.
Example
A non-trivial example of a ring is the class
$$ \cR = \{ A \subset S \, | \, A \text{ is finite} \}. $$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. $$Sigma-ring ($\sigma$-ring) #
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 intersections. Hence if $\cR$ is a $\sigma$-ring and $\{A_n\}$ is a sequence of sets from $\cR$ then $\limsup A_n$ and $\liminf A_n$ both belong to $\cR$.
Algebra (or field) #
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$.
Sigma-algebra ($\sigma$-algebra, Borel field, $\sigma$-field) #
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.
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).
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 A_n = \{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.
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$.
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
Monotone Class Theorems #
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). 8See also presentation from He, Wang and Yan, “Semimartingale Theory and Stochastic Calculus,” 1992.
Theorem (Monotone class theorem)
Proof.
■
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. 9How 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.
Eugene Borisovich Dynkin [Евге́ний Бори́сович Ды́нкин] (1924-2014).
Dynkin was born into a Jewish family. After being exiled to Kazakhstan in 1935, his father disappeared in the Gulag when he was 13. Dynkin was supported by A. Kolmogorov, his PhD supervisor at Moscow University despite his Jewish origin. In the late 1970s, Dynkin emigrated to the United States to become a professor at Cornell University. His contributions are very broad with fundamental results in Lie algebras and Markov processes. Of particular interest to me are his analysis of Dynkin stopping games and partially observed Markov processes.
(Cornell University)).
Definition
A collection $\cN$ of subsets of $S$ is called a $\lambda$-system on $S$ if
(i) $S \in \cN$,
(ii) for any $A, B \in \cN$ with $A \subset B, B \setminus A \in \cN$,
(iii) if $\{ A_n \}_{n \in \N} \subset \cN$ and $A_n \subset A_{n+1}$ for all $n$, then $\bigcup_{n \in \N} A_n \in \cN$.
A collection $\cN$ of sets is called a $\pi$-system if it is stable under finite intersections, that is $A \cap B \in \cN$ whenever $A, B \in \cN$.
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. 10See Cohen, “Stochastic Calculus and Applications,” 2015 for a sketch of a proof Appendix A.1 in 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.
11Finish the proof looking at Section 7.4 in Cohen, “Stochastic Calculus and Applications,” 2015.
■
Remark
The Borel Sets #
It is often important to see the interaction between $\sigma$-algebras 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$. 12Intersections 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
In general, for any given set $S$, there are usually many possible $\sigma$-algebras.
Definition
For any collection $\Sigma_n$ of $\sigma$-algebras on a set $S$, we define $\bigvee_n \Sigma_n$ to be the smallest $\sigma$-algebra containing all subsets of each $\Sigma_n$. That is,
$$ \bigvee_n \Sigma_n := \sigma(\bigcup_n \Sigma_n). $$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