I. Sets and collections of sets
$$
$$
Find these notes at gregorkb.github.io/probtheory/
Basic
Notation:
Sample space \(\Omega\).
Capital letters \(A,B,\dots\) denote subsets of \(\Omega\)
Use \(\omega\) for a sample point \(\omega \in \Omega\).
Script letters \(\mathcal{A}, \mathcal{B},\dots\) denote collections of subsets of \(\Omega\).
Denote empty set by \(\emptyset\).
Elementary set operations:
Union:
- For two subsets \(A,B\subset \Omega\), \(A\cup B \equiv \{\omega \in \Omega: \omega \in A \text{ or } \omega \in B\}\).
- For a finite collection of subsets \(A_1,\dots,A_n \subset \Omega\), \(\bigcup_{i=1}^n A_i \equiv \{\omega \in \Omega : \omega \in A \text{ for some } i = 1,\dots,n \}\).
- For a countable collection of subsets \(\{A_n\}_{n \geq 1}\), \(\bigcup_{n \geq 1} A_n \equiv \{\omega \in \Omega : \omega \in A \text{ for some } n \geq 1\}\).
- For an arbitrary collection of subsets \(\{A_\alpha, \alpha \in I\}\), \(I\) finite, countable, or uncountable, \(\bigcup_{\alpha \in I} A_i \equiv \{\omega \in \Omega : \omega \in A \text{ for some } \alpha \in I \}\).
Intersection:
- For two subsets \(A,B\subset \Omega\), \(A\cap B \equiv \{\omega \in \Omega: \omega \in A \text{ and } \omega \in B\}\).
- For a finite collection of subsets \(A_1,\dots,A_n \subset \Omega\), \(\bigcap_{i=1}^n A_i \equiv \{\omega \in \Omega : \omega \in A \text{ for all } i = 1,\dots,n \}\).
- For a countable collection of subsets \(\{A_n\}_{n \geq 1}\), \(\bigcap_{n \geq 1} A_n \equiv \{\omega \in \Omega : \omega \in A \text{ for all } n \geq 1\}\).
- For an arbitrary collection of subsets \(\{A_\alpha, \alpha \in I\}\), \(I\) finite, countable, or uncountable, \(\bigcap_{\alpha \in I} A_i \equiv \{\omega \in \Omega : \omega \in A \text{ for all } \alpha \in I \}\).
Complement: For a subset \(A \subset \Omega\), \(A^c \equiv \{\omega \in \Omega: \omega \notin A\}\).
Set difference: For subsets \(A,B \subset \Omega\), \(A \setminus B \equiv A \cap B^c\)
Set containment: Write \(A \subset B\) if \(\omega \in A\) implies \(\omega \in B\).
Equality of sets: Write \(A = B\) if \(A \subset B\) and \(B \subset A\).
De Morgan’s Laws:
- For \(A,B \subset \Omega\), \((A \cup B)^c = A^c \cap B^c\) and \((A \cap B)^c = A^c \cup B^c\).
- For an arbitrary collection of subsets \(\{A_\alpha, \alpha \in I\}\), \((\bigcup_{\alpha \in I} A_\alpha)^c = \bigcap_{\alpha \in I} A_\alpha^c\) and \((\bigcap_{\alpha \in I} A_\alpha)^c = \bigcup_{\alpha \in I} A_\alpha^c\).
Indicator function: \(1_A : \Omega \to \mathbb{R}\) given by \(\displaystyle 1_A(\omega) \equiv \left\{\begin{array}{ll} 1,& \omega \in A\\ 0,& \omega \notin A. \end{array}\right.\)
Infimum and supremum of a sequence of subsets: For a sequence of subsets \(\{A_n \}_{n \geq 1}\) of \(\Omega\):
\(\inf_{n\geq 1}A_n \equiv \bigcap_{n \geq 1}A_n\). Note that \(\inf_{n \geq 1}1_{A_n}(\omega) = 1_{\cap_{n\geq 1}A_n}(\omega)\).
\(\sup_{n \geq 1} A_n \equiv \bigcup_{n \geq 1} A_n\). Note that \(\sup_{n \geq 1}1_{A_n}(\omega) = 1_{\cup_{n\geq 1}A_n}(\omega)\).
Monotone sequences: Sequence of subsets \(\{A_n\}_{n\geq 1}\) is non-decreasing if \(A_n \subset A_{n+1}\) for all \(n\geq 1\) and non-increasing if \(A_{n+1} \subset A_n\) for all \(n \geq 1\). Such sequences are called monotone sequences.
Limits of monotone sequences: For a sequence \(\{A_n\}_{n\geq 1}\) of subsets:
If \(A_n \subset A_{n+1}\) for all \(n \geq 1\), then \(\lim_{n\to \infty} A_n = \bigcup_{n \geq 1} A_n\).
If \(A_{n+1} \subset A_n\) for all \(n \geq 1\), then \(\lim_{n\to \infty} A_n = \bigcap_{n \geq 1} A_n\).
Fields and \(\sigma\)-fields
Field or algebra: A collection \(\mathcal{F}\) of subsets of \(\Omega\) is called a field or an algebra if:
- \(\Omega \in \mathcal{F}\).
- \(A \in \mathcal{F}\) implies \(A^c \in \mathcal{F}\) (closure under complementation).
- \(A, B \in \mathcal{F}\) implies \(A \cup B \in \mathcal{F}\) (closure under finite unions).
Show (by Morgan’s laws) that we can make an equivalent definition by replacing iii. above with:
- \(A, B \in \mathcal{F}\) implies \(A \cap B \in \mathcal{F}\).
\(\sigma\)-field or \(\sigma\)-algebra: A collection \(\mathcal{F}\) of subsets of \(\Omega\) is called a \(\sigma\)-field or \(\sigma\)-algebra if:
- \(\Omega \in \mathcal{F}\).
- \(A \in \mathcal{F}\) implies \(A^c \in \mathcal{F}\).
- \(A_1,A_2,\dots \in \mathcal{F}\) implies \(\bigcup_{n\geq 1} A_n \in \mathcal{F}\) (closure under countable unions).
Show that we can make an equivalent definition by replacing iii. above with the pair of conditions:
- \(A, B \in \mathcal{F}\) implies \(A \cup B \in \mathcal{F}\).
- \(A_1,A_2,\dots \in \mathcal{F}\) and \(A_n \subset A_{n+1}\) for \(n \geq 1\) implies \(\bigcup_{n \geq 1} A_n \in \mathcal{F}\) (closure under non-decreasing unions).
Show that we can make another equivalent definition by replacing iii. and iv. above with:
- \(A, B \in \mathcal{F}\) implies \(A \cap B \in \mathcal{F}\).
- \(A_1,A_2,\dots \in \mathcal{F}\) and \(A_{n+1} \subset A_n\) for \(n \geq 1\) implies \(\bigcap_{n \geq 1} A_n \in \mathcal{F}\) (closure under non-increasing intersections).
Note that every \(\sigma\)-algebra is an algebra.
Check whether the following are fields or \(\sigma\)-fields:
- With \(\Omega = \{a,b,c\}\):
- \(\mathcal{A}= \{\emptyset, \{a\},\{b,c\},\{a,b,c\}\}\)
- \(\mathcal{B}= \{\emptyset,\{a\},\{b\},\{a,b\}\}\).
- The power set \(\mathcal{P}(\Omega) = \{A : A \subset \Omega\}\), which is the collection of all subsets of \(\Omega\).
- The trivial \(\sigma\)-field \(\{\emptyset, \Omega\}\).
- \(\mathcal{F}= \{A \subset \Omega : |A|< \infty \text{ or } |A^c| < \infty \}\).
- With \(\Omega = \{a,b,c\}\):
We may refer to a \(\sigma\)-field of subsets of \(\Omega\) simply as a \(\sigma\)-field on \(\Omega\).
Let \(\mathcal{F}_1\) and \(\mathcal{F}_2\) be \(\sigma\)-fields on \(\Omega\). Show that \(\mathcal{F}_1 \cap \mathcal{F}_2\) is a \(\sigma\)-field on \(\Omega\).
Generated \(\sigma\)-field: For any collection \(\mathcal{C}\) of subsets of \(\Omega\), let \(\Sigma(\mathcal{C}) \equiv \{\mathcal{F}: \mathcal{F}\text{ is a $\sigma$-field on $\Omega$ and $\mathcal{C}\subset \mathcal{F}$}\}\) denote the set of all \(\sigma\)-fields on \(\Omega\) containing \(\mathcal{C}\). Then \[ \sigma \langle \mathcal{C}\rangle \equiv \bigcap_{\mathcal{F}\in \Sigma(\mathcal{C})}\mathcal{F} \] is called the \(\sigma\)-field on \(\Omega\) generated by \(\mathcal{C}\). We may think of \(\sigma \langle \mathcal{C}\rangle\) as the smallest \(\sigma\)-field on \(\Omega\) containing \(\mathcal{C}\). Note that \(\sigma \langle \mathcal{C}\rangle \subset \mathcal{F}\) for any \(\mathcal{F}\in \Sigma(\mathcal{C})\).
Let \(\Omega = \{a,b,c,d\}\) and find \(\sigma \langle \mathcal{C}_i \rangle\), \(i=1,2,3,4\), where \[ \begin{align} \mathcal{C}_1 &\equiv\{\{a\},\{b\}\} \\ \mathcal{C}_2 &\equiv \{\{a,b\}\}\\ \mathcal{C}_3 &\equiv \{\{a,b\},\{c\}\}\\ \mathcal{C}_4 &\equiv \{\{a,b\},\{b,c\}\}. \end{align} \]
Let \(\mathcal{C}\) and \(\mathcal{D}\) be collections of subsets of \(\Omega\). Show that \(\mathcal{C}\subset \mathcal{D}\) implies \(\sigma \langle \mathcal{C}\rangle \subset \sigma \langle \mathcal{D}\rangle\).
Borel \(\sigma\)-field
Metric space: A metric space is a pair \((\mathbb{S},d)\), where \(\mathbb{S}\) is a nonempty set and \(d:\mathbb{S}^2 \to \mathbb{R}^+ \equiv [0,\infty]\) is a function satisfying
- \(d(x,y) = d(y,x)\) for all \(x,y \in \mathbb{S}\).
- \(d(x,y) = 0\) if and only if \(x = y\).
- \(d(x,y) \leq d(x,z) + d(z,y)\) for all \(x,y,z \in \mathbb{S}\) (triangle inequality). See also.
The function \(d\) is called a metric or a distance.
Euclidean metric space: A Euclidean space \(\mathbb{R}^k\) is a metric space when equipped with the metric \[ d_p(x,y) = \left\{ \begin{array}{ll}\sum_{i=1}^k(x_i - y_i)^p,& 0 < p < 1 \\ (\sum_{i=1}^k(x_i - y_i)^p)^{1/p},& 1 \leq p < \infty\\ \max_{1\leq i \leq k}|x_i - y_i|,& p = \infty.\end{array}\right. \] for any \(p > 0\).
Open set in a metric space: A set \(O\) in a metric space \((\mathbb{S},d)\) is open if for every \(x \in O\) there exists \(\epsilon > 0\) such that \(\{y: d(x,y) < \epsilon\} \subset O\).
Open set in \(\mathbb{R}\): A set \(O \subset \mathbb{R}\) is open if for each \(x \in O\) there exists \(\delta(x) > 0\) such that \((x - \delta(x),x + \delta(x)) \subset O\). See page 60 of Kirkwood.
Borel \(\sigma\)-field: The Borel \(\sigma\)-field on \(\mathbb{R}^k\), \(1 \leq k < \infty\), denoted \(\mathcal{B}(\mathbb{R}^k)\), is the \(\sigma\)-field generated by the collection of all open sets in \(\mathbb{R}^k\). That is \[ \mathcal{B}(\mathbb{R}^k) \equiv \sigma \langle \{A \subset \mathbb{R}^k: \text{$A$ is open}\} \rangle \]
Generating the Borel sets in \(\mathbb{R}\): Define the collection \[ \mathcal{O} \equiv \{(a,b): -\infty \leq a < b \leq \infty\} \] of open intervals in \(\mathbb{R}\) and show that \(\mathcal{B}(\mathbb{R}) = \sigma\langle\mathcal{O}\rangle\).
Use the fact that any open set in \(\mathbb{R}\) can be constructed as a countable union of open intervals (See Theorem 3-5 on page 63 of Kirkwood).
Another way to generate the Borel sets in \(\mathbb{R}\): Define the collection \[ \mathcal{C} \equiv \{(a,b]: -\infty \leq a < b < \infty\} \] of half-open intervals in \(\mathbb{R}\) and show that \(\sigma \langle \mathcal{C}\rangle = \sigma\langle\mathcal{O}\rangle\) (See arguments on page 17 of Resnick).
Generating the Borel \(\sigma\)-algebra on \(\mathbb{R}^k\): Define the collection \[ \mathcal{O}_k \equiv \{(a_1,b_1)\times \dots \times (a_k,b_k) : - \infty \leq a_i < b_i \leq \infty , 1 \leq i \leq k\} \] of open rectangles in \(\mathbb{R}^k\). Show that \(\mathcal{B}(\mathbb{R}^k) = \sigma \langle \mathcal{O}_k \rangle\) (See Example 1.1.6 on page 12 of A&L).
Restricting a \(\sigma\)-field to a subset of the sample space: Let \(\mathcal{F}\) be a \(\sigma\)-field on \(\Omega\) and let \(\Omega_0 \subset \Omega\) and set \(\mathcal{F}_0\equiv \{A \cap \Omega_0 : A \in \mathcal{F}\}\). Show that \(\mathcal{F}_0\) is a \(\sigma\)-field on \(\Omega_0\) (See Theorem 1.8.1(1) on page 18 of Resnick).
Generating a \(\sigma\)-field from a restricted collection of subsets: Let \(\mathcal{C}\) be a collection of subsets of \(\Omega\) and let \(\Omega_0 \subset \Omega\) and set \(\mathcal{C}_0 \equiv \mathcal{C}\cap \Omega_0 \equiv \{A \cap \Omega_0: A \in \mathcal{C}\}\). Show that \[ \sigma \langle \mathcal{C}_0 \rangle = \sigma \langle \mathcal{C}\rangle \cap \Omega_0 \equiv \{A \cap \Omega_0 : A \in \sigma \langle \mathcal{C}\rangle \}. \] See Theorem 1.8.1(2) on page 18 of Resnick.
Borel \(\sigma\)-algebra truncated to \((0,1]\): According to the above, we can generate \(\mathcal{B}((0,1]) \equiv \{A \cap (0,1]:A \in \mathcal{B}(\mathbb{R})\}\) as \(\sigma \langle \mathcal{O}_{(0,1]}\rangle\), where \(\mathcal{O}_{(0,1]} = \{A \cap (0,1] : A \in \mathcal{O}\}\).
\(\pi\)- and \(\lambda\)-classes
\(\pi\)-system: A class (or collection) of subsets \(\mathcal{C}\) of \(\Omega\) is called a \(\pi\)-system (\(\pi\)-class) if
- \(A,B \in \mathcal{C}\) implies \(A \cap B \in \mathcal{C}\) (closure under finite intersections).
\(\lambda\)-system: A class of subsets \(\mathcal{L}\) of \(\Omega\) is called a \(\lambda\)-system (\(\lambda\)-class, monotone class, Dynkin system) if
- \(\Omega \in \mathcal{L}\).
- \(A,B \in \mathcal{L}\) and \(A \subset B\) imply \(B\setminus A \in \mathcal{L}\) (closure under proper differences).
- \(A_1,A_2,\dots\in\mathcal{L}\) and \(A_n \subset A_{n+1}\) for all \(n \geq 1\) imply \(\bigcup_{n\geq 1}A_n \in \mathcal{L}\) (closure under non-decreasing unions).
Show that ii. and iii. above can be replaced with:
- \(A \in \mathcal{L}\) implies \(A^c \in \mathcal{L}\) (closure under complementation)
- \(A_1,A_2,\dots \in \mathcal{L}\), \(A_i \cap A_j = \emptyset\) for all \(i \neq j\) implies \(\bigcup_{n\geq 1} A_n \in \mathcal{L}\) (closure under countable disjoint unions).
Show that every \(\sigma\)-algebra is a \(\lambda\)-system.
Let \(\mathcal{L}_1\) and \(\mathcal{L}_2\) be \(\lambda\)-systems on \(\Omega\). Show that \(\mathcal{L}_1\cap \mathcal{L}_2\) is a \(\lambda\)-system on \(\Omega\).
Show that a \(\lambda\)-system which is also a \(\pi\)-system is a \(\sigma\)-algebra.
Generated \(\lambda\)-system: For any collection \(\mathcal{C}\) of subsets of \(\Omega\), let \(\Lambda(\mathcal{C}) \equiv \{\mathcal{L}: \mathcal{L}\text{ is a $\lambda$-system on $\Omega$ and $\mathcal{C}\subset \mathcal{L}$}\}\) denote the set of all \(\lambda\)-systems on \(\Omega\) containing \(\mathcal{C}\). Then \[ \lambda \langle \mathcal{C}\rangle \equiv \bigcap_{\mathcal{L}\in \Lambda(\mathcal{C})}\mathcal{L} \] is called the \(\lambda\)-system on \(\Omega\) generated by \(\mathcal{C}\). Just as with a generated \(\sigma\)-algebra, we can think of \(\lambda \langle \mathcal{C}\rangle\) as the smallest \(\lambda\)-system on \(\Omega\) containing the collection \(\mathcal{C}\).
Dynkin’s \(\pi\)-\(\lambda\) theorem: Let \(\mathcal{C}\subset \mathcal{P}(\Omega)\) be a \(\pi\)-system and \(\mathcal{L}\subset \mathcal{P}(\Omega)\) be a \(\lambda\)-system such that \(\mathcal{C}\subset \mathcal{L}\). Show that \(\sigma \langle \mathcal{C}\rangle \subset \mathcal{L}\).
Nice video by Adam B. Kashlak www.youtube.com/@cachelackmathstatslectures7001. See Theorem 2.2.2 on page 37 of Resnick.
Corollary to the \(\pi\)-\(\lambda\) theorem: Let \(\mathcal{C}\) be a \(\pi\)-system of subsets of \(\Omega\). Show that \(\lambda \langle \mathcal{C}\rangle = \sigma \langle \mathcal{C}\rangle\).
That is, if you start with a \(\pi\)-system, show that the \(\lambda\)-system generated by the \(\pi\)-system is the same as the \(\sigma\)-field generated by the \(\pi\)-system (See Theorem 1.1.2 on page 13 of A&L or Theorem 2.3 on page 8 of Gut).
Semi-algebras
Semi-algebra: A collection \(\mathcal{C}\) of subsets of \(\Omega\) is called a semi-algebra if
- \(\emptyset,\Omega \in \mathcal{C}\).
- \(A,B \in \mathcal{C}\) implies \(A \cap B \in \mathcal{C}\).
- \(A \in \mathcal{C}\) implies that there exist \(A_1,\dots,A_n \in \mathcal{C}\), \(n < \infty\), with \(A_i \cap A_j = \emptyset\) for all \(i \neq j\) such that \(A^c = \bigcup_{i=1}^n A_n\).
So a semi-algebra is a \(\pi\)-class which contains the sample space and which has the property that if \(A\) is a member, \(A^c\) can be constructed as a finite union of disjoint members (though \(A^c\) need not be a member). See Exercise 2.2.3 on page 9 of Rosenthal or Definition 2.4.1 on page 44 of Resnick.
Show that the collection \[ \mathcal{C}= \{(a,b]:-\infty \leq a \leq b < \infty\} \cup \{(a,\infty): - \infty \leq a < \infty\} \] of subsets of \(\mathbb{R}\) is a semi-algebra.
Show that \(\sigma \langle \mathcal{C}\rangle = \mathcal{B}(\mathbb{R})\), where \(\mathcal{C}\) is the semi-algebra defined above.
Algebra generated by a semi-algebra: Let \(\mathcal{C}\) be a semi-algebra of subsets of \(\Omega\). Show that the intersection of all algebras containing \(\mathcal{C}\) is given by \[ \mathcal{A}\langle \mathcal{C}\rangle \equiv \{\bigcup_{i=1}^n B_i : B_1,\dots,B_n \in \mathcal{C}, B_i \cap B_j = \emptyset \text{ for } i \neq j, n < \infty\}. \]
The claim is that \(\mathcal{A}\langle \mathcal{C}\rangle\) is the smallest algebra containing \(\mathcal{C}\) or the algebra generated by \(\mathcal{C}\). See Lemma 2.4.1 on page 45 of Resnick.
Given the sample space \(\Omega = \{a,b,c,d\}\) define the collection of sets \[ \mathcal{C}= \{\emptyset, \{a,b,c,d\},\{a\},\{b\},\{c,d\},\{b,c,d\}\}. \] Show that \(\mathcal{C}\) is a semi-algebra but not an algebra.
Show that if \(\mathcal{C}\subset \mathcal{P}(\Omega)\) is a semi-algebra then \(\sigma \langle \mathcal{C}\rangle = \sigma \langle \mathcal{A}\langle \mathcal{C}\rangle \rangle\).