# Clarification on the proof of Carathéodory’s lemma

Carathéodory’s lemma, as it appears in p. 197 (appendix A1) of the book “Probability with martingales” by David Williams, is stated as follows:

Let $\lambda$ be an outer measure on the measurable space $(S,\mathcal{G})$. Then the λ-sets in $\mathcal{G}$ form a σ-algebra $\mathcal{L}$ on which $\lambda$ is countably additive, so that $(S,\mathcal{L},\lambda)$ is a measure space.

Three aspects of the proof of Carathéodory’s lemma provided in Williams’ book are clarified in this blog post.

Definition of λ-system

The concept of λ-system, which is used implicitly but it is not defined in Williams’ book, is introduced in this post.

A collection $\mathcal{C}$ of subsets of a set $S$ is called a λ-system on $S$ if

1. $S\in\mathcal{C}$,
2. $L\in\mathcal{C}\Rightarrow L^{c}\in\mathcal{C}$ (it is closed under complements),
3. $(\forall n\in\mathbb{N})L_n\in\mathcal{C}$ with $L_i\cap L_j=\emptyset$ for $i\neq j$ it holds that $\underset{n\in\mathbb{N}}{\cup}L_n\in\mathcal{C}$ (it is closed under countable disjoint unions).

Not that the only difference between a λ-system and a σ-algebra is that the former is closed under countable disjoint unions while the latter is closed under countable unions. Moreover, the first condition on the definition of a λ-system could be alternatively set to $\emptyset\in\mathcal{C}$ instead of $S\in\mathcal{C}$ due to closure under complementarity, i.e. due to the second condition of the definition.

Lemma

If a collection of subsets of a set $S$ is a λ-system and a π-system on $S$, it is also a σ-algebra on $S$.

This lemma is used without being proved in Williams’ book for proving Carathéodory’s lemma. In what follows, the lemma will be proved before proceeding with the proof of Carathéodory’s lemma.

Although not relevant to subsequent developments, it is mentioned that a σ-algebra on a set $S$ is also a λ-system on $S$ as it can be trivially seen from the involved definitions.

Proof of the lemma

Let $\mathcal{C}$ be a collection of subsets $S$ that is both a λ-system and a π-system on $S$. To show that $\mathcal{C}$ is a σ-algebra on $S$, it suffices that it is closed under countable unions.

Let $B_n\in\mathcal{C},n\in\mathbb{N}$. The main idea is to express the collection $\{B_n: n\in\mathbb{N}\}$ as a collection $\{L_n: n\in\mathbb{N}\}$ of pairwise disjoint sets ($L_i\cap L_j=\emptyset$ for $i\neq j$) so that $\underset{n\in\mathbb{N}}{\cup}B_n=\underset{n\in\mathbb{N}}{\cup}L_n$. Along these lines, define $L_n:=B_n\setminus \left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)$.

Obviously, $\underset{n\in\mathbb{N}}{\cup}L_n\subseteq \underset{n\in\mathbb{N}}{\cup}B_n$. To prove the converse set inequality, let $x\in\underset{n\in\mathbb{N}}{\cup}B_n$ and assume that $(\forall n\in\mathbb{N}) x\not\in B_n\setminus \left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)$. In this case, for each $n\in\mathbb{N}$, either $x\not\in B_n$ or $x\in B_n\cap\left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)$. There is at least one $n_{*}\in\mathbb{N}$ such that $x\in B_{n_{*}}\cap\left(\overset{n_{*}-1}{\underset{k=1}{\cup}} B_k\right)$, otherwise $(\forall n\in\mathbb{N}) x\not\in B_n$ leads to the contradiction $x\not\in\underset{n\in\mathbb{N}}{\cup}B_n$. Let $n_o\in\mathbb{N}$ be the minimum natural for which $x\in B_{n_{o}}\cap\left(\overset{n_{o}-1}{\underset{k=1}{\cup}} B_k\right)$. In turn, $x\in \overset{n_{o}-1}{\underset{k=1}{\cup}} B_k\Rightarrow (\exists i. Due to $n_o$ being the smallest natural for which $x\in B_{n_{o}}\cap\left(\overset{n_{o}-1}{\underset{k=1}{\cup}} B_k\right)$, it is deduced that $x\not\in B_i\cap\left(\overset{i-1}{\underset{k=1}{\cup}} B_k\right)$, hence $x\not\in\left(\overset{i-1}{\underset{k=1}{\cup}} B_k\right)$. Thus, $(\exists i\in\mathbb{N}) x\in B_i\setminus \left(\overset{i-1}{\underset{k=1}{\cup}} B_k\right)$, which is a contradiction. Thereby, $\underset{n\in\mathbb{N}}{\cup}B_n\subseteq \underset{n\in\mathbb{N}}{\cup}L_n$, and this establishes the equality $\underset{n\in\mathbb{N}}{\cup}L_n= \underset{n\in\mathbb{N}}{\cup}B_n$.

Assume that there are $i,j\in\mathbb{N}$ with $i\neq j$ and $L_i \cap L_j \neq \emptyset$. Let $x\in L_i \cap L_j$. Without loss of generality assume that $i. Then $x\in B_i$ with $i, while $x\in L_j=B_j\setminus \left(\overset{j-1}{\underset{k=1}{\cup}} B_k\right)$, which means that $(\forall k\in\mathbb{N})$ with $k it holds that $x\not\in B_k$, so a contradiction has been reached. Thereby, the sets $L_n, n\in\mathbb{N}$, are pairwise disjoint.

It has thus been shown that the collection $L_n:=B_n\setminus \left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)$ consists of pairwise disjoints sets that satisfy $\underset{n\in\mathbb{N}}{\cup}L_n=\underset{n\in\mathbb{N}}{\cup}B_n$.

Notice that $L_n:=B_n\setminus \left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)=B_n \overset{n-1}{\underset{k=1}{\cap}}B_k^c$. Since $\mathcal{C}$ is a λ-system, $B_k^c\in\mathcal{C}$ for the various $k$. Moreover, $\mathcal{C}$ is a π-system, hence the finite intersection $L_n=B_n \overset{n-1}{\underset{k=1}{\cap}}B_k^c$ is also in $\mathcal{C}$. Since the collection $L_n:=B_n\setminus \left(\overset{n-1}{\underset{k=1}{\cup}} B_k\right)$ is a disjoint union of elements $L_n\in\mathcal{C}$ and $\mathcal{C}$ is a λ-system, it follows that the union $\underset{n\in\mathbb{N}}{\cup}L_n= \underset{n\in\mathbb{N}}{\cup}B_n$ is also in $\mathcal{C}$.

Since the countable (but not necessarily disjoint) union $\underset{n\in\mathbb{N}}{\cup}B_n$ of any collection $\{B_n: n\in\mathbb{N}\}$ of sets $B_n\in\mathcal{C}$ is also in $\mathcal{C}$, it follows that $\mathcal{C}$ is a σ-algebra.

First clarification

The above lemma explains why the proof of Carathéodory’s lemma in Williams’ book states that it suffices to show that for a countable collection $\{L_n: n\in\mathbb{N}\}$ of disjoint sets $L_n\in\mathcal{L}$ it holds that $\underset{n\in\mathbb{N}}{\cup}L_n\in\mathcal{L}$. The conclusion then extends to any such countable union of sets, disjoint or not.

Second clarification

It is mentioned in p. 197 of Williams’ book that from

$\lambda (G)\ge\overset{n}{\underset{k=1}{\sum}}\lambda(L_k\cap G)+\lambda(L^c\cap G)$

follows

$\lambda (G)\ge\overset{\infty}{\underset{k=1}{\sum}}\lambda(L_k\cap G)+\lambda(L^c\cap G)$.

To see why this is the case, recall that the outer measure $\lambda:\mathcal{G}\rightarrow [ 0, \infty ]$ takes in values in $\lambda (G)\in[0, \infty]$ for any $G\in\mathcal{G}$.

Distinguish two cases. If $\lambda (G)\in [0,\infty )$ (i.e. if $\lambda (G)$ is finite), then the sequence $a_n=\overset{n}{\underset{k=1}{\sum}}\lambda(L_k\cap G),n\in\mathbb{N}$, is a bounded increasing sequence, therefore it converges, which means that the limit $\overset{\infty}{\underset{k=1}{\sum}}\lambda(L_k\cap G)=\underset{n\rightarrow\infty}{\lim}a_n < \infty$ exists, so taking limits leads from the former to the latter inequality in the book.

If $\lambda (G)=\infty$, then $\infty \ge\overset{\infty}{\underset{k=1}{\sum}}\lambda(L_k\cap G)+\lambda(L^c\cap G)$ holds trivially.

Third clarification

To show that $\lambda (L)=\underset{k\in\mathbb{N}}{\sum}\lambda (L_k)$ for $L=\underset{k\in\mathbb{N}}{\cup}L_k$, notice first that

$\lambda (L)\le\underset{k\in\mathbb{N}}{\sum}\lambda (L_k)$

follows from the countable subadditivity of the outer measure $\lambda$.

Moreover, setting $G=L$ in equation (d) of p. 197 gives

$\lambda (L)\ge\underset{k\in\mathbb{N}}{\sum}\lambda (L_k\cap L)+\lambda (L^c\cap L)=\underset{k\in\mathbb{N}}{\sum}\lambda (L_k)$,

which concludes the argument.

# Proof: a representation of the Borel σ-algebra on reals

This post elaborates on the proof of a proposition in page 17 of the book “Probability with martingales” by David Williams. The relevant proposition is first stated; the Borel σ-algebra $\mathcal{B}:=\mathcal{B}(\mathbb{R})$ on the set $\mathbb{R}$ of real numbers is given by $\mathcal{B}=\sigma (\pi (\mathbb{R}))$, where $\sigma(\pi(\mathbb{R}))$ denotes the sigma algebra on $\mathbb{R}$ generated by $\pi (\mathbb{R})=\{(-\infty, x]:x\in\mathbb{R}\}$.

It is reminded that the Borel σ-algebra $\mathcal{B}(S)$ on a set $S$ is the σ-algebra $\sigma(\mathcal{O})$ generated by the family $\mathcal{O}$ of open subsets of $S$, i.e. $\mathcal{B}(S):=\sigma(\mathcal{O})$.

Two lemmas are provided before proceeding with the proof.

Lemma 1

Let $S$ be a set, and let $\mathcal{C}_1,\mathcal{C}_2$ be two collections of subsets of $S$. If $\mathcal{C}_1\subseteq\sigma(\mathcal{C}_2)$, then $\sigma(\mathcal{C}_1)\subseteq\sigma(\mathcal{C}_2)$.

Proof of lemma 1

$\sigma(\mathcal{C}_2)$ is a σ-algebra on $S$ that contains $\mathcal{C}_1$ and $\sigma(\mathcal{C}_1)$ is the intersection of all σ-algebras on $S$ that contain $\mathcal{C}_1$, so $\sigma(\mathcal{C}_1)\subseteq\sigma(\mathcal{C}_2)$.

Lemma 2

Every open subset $G$ of $\mathbb{R}$ in the Euclidean metric space $(\mathbb{R},\|\cdot\|)$ can be represented uniquely as a countable union of disjoint open intervals.

Proof of lemma 2

This lemma appears also as theorem 1.3, p. 6, in the book “Real analysis: measure theory, integration and Hilbert spaces” by Elias M. Stein and Rami Shakarchi, where a partial proof is provided as uniqueness is not established. In what follows, the proof from Stein’s and Shakarchi’s book is reproduced in more detail, plus uniqueness is proved.

Let $G$ be an open subset of $\mathcal{R}$ and $x\in G$. Introduce the sets $\mathcal{A}_x:=\{a\in\mathbb{R}: a and $\mathcal{B}_x:=\{b\in\mathbb{R}: x. Moreover, let $a_x:=\mbox{inf}\mathcal{A}_x$ and $b_x:=\mbox{sup}\mathcal{B}_x$, allowing for $a_x,b_x$ to be infinite. Consider also the interval $I_x:=(a_x,b_x)$.

It will be shown that $I_x\subseteq G$. Let $y\in I_x$. Assume that $(\forall a\in\mathcal{A}_x)y\le a$, in which case $y$ is a lower bound of $\mathcal{A}_x$, so $y\le a_x$, thus contradicting the assumption $y\in I_x=(a_x, b_x)$. Hence, there exists $a\in\mathcal{A}_x$ such that $a. By a symmetric argument, there exists $b\in\mathcal{B}_x$ such that $y. So, $y\in (a,b)\subseteq (a_x,b_x)$. If $y=x$, then obviously $y\in G$. If $y\neq x$, then $y\in (a,x)\cup (x, b)$. Note that $a\in\mathcal{A}_x$ means that $(a,x)\subseteq G$. So, if $y\in (a,x)$, then $y\in G$. Similarly, if $y\in (x,b)$, then $y\in G$. Thus, $y\in I_x\Rightarrow y\in G$, which means that $I_x\subseteq G$.

$(\forall x\in G) I_x\subseteq G\Rightarrow\underset{x\in G}{\bigcup}I_x\subseteq G$. Furthermore, let $y\in G$. As $G=G^{o}$, there exists $r>0$ such that $(x-r,x+r)\subseteq G$. It follows from $y-r and $(y-r,y)\subseteq (y-r,y+r)\subseteq G$ that $y\in\mathcal{A}_y$. In a similar way, $y\in\mathcal{B}_y$. So, $a_y\le y\le b_y\Rightarrow y\in I_y\subseteq\underset{x\in G}{\bigcup}I_x$. Hence, $G=\underset{x\in G}{\bigcup}I_x$.

Assume that $I_x\cap I_y\neq\emptyset$, in which case $I_x\cup I_y$ is also an open interval. It is straightforward to confirm that if $I$ is an open interval containing $x$ and being contained in $G$, then $I\subseteq I_x$. So, $I_x\cup I_y\subseteq I_x$ and $I_x\cup I_y\subseteq I_y$, which yields $I_x=I_y$. It has been shown that $I_x\cap I_y\neq\emptyset\Rightarrow I_x=I_y$. By contraposition, $I_x\neq I_y\Rightarrow I_x\cap I_y=\emptyset$, which means that the sets of the collection $\{I_x:x\in G\}$ are pairwise disjoint.

For every set $I_x$ in $\{I_x :x\in G\}$, pick a rational $q_x\in I_x$. The set $S:=\{q_x: q_x\in I_x\}$ of selected rationals is obviously a subset of the set $\mathbb{Q}$ of rationals. $S\subseteq\mathbb{Q}$ implies the cardinality inequality $|S|\le |Q|$, so $S$ is a countable set. Since  $|\{I_x :x\in G\}|=|S|$, it is deduced that the collection $\{I_x :x\in G\}$ is also countable.

It has been proved so far that $G$ can be expressed as a countable union of disjoint open intervals. Although not pertinent to the subsequent proof, it will be shown that such representation is unique for the sake of completeness of exposition.

Let $\{I_k : k\in K\}$ and $\{J_{\ell} : \ell\in L\}$ be two collections of disjoint open intervals such that $G=\underset{k\in K}{\bigcup}I_k=\underset{\ell\in L}{\bigcup}J_{\ell}$.

For any $k\in K$, it holds that $I_k=\underset{\ell\in L}\bigcup(I_k\cap J_{\ell})$. Moreover, the sets of the collection $\{I_k\cap J_{\ell}:\ell\in L\}$ are pairwise disjoint. Since $I_k$ and $J_{_\ell}$ are open, $(I_k\cap J_{\ell})^{o}=I_k^{o}\cap J_{\ell}^{o}=I_k\cap J_{\ell}$, which means that $I_k\cap J_{\ell}$ is also open.

In the collection $\{I_k\cap J_{\ell}:\ell\in L\}$, at least one set is non-empty, otherwise trivially $G=\emptyset$.

In the Euclidean metric space $(\mathbb{R},\|\cdot\|)$, every interval is a connected set. Since $I_k$ is an interval, it is connected. Furthermore, a subset $S$ of a metric space $E$ is connected, if and only if there is no open cover $\{A,B\}$ of $S$ such that $S\cap A\neq\emptyset$, $S\cap B\neq\emptyset$ and $S\cap A\cap B=\emptyset$. Hence, by also considering that $I_k$ is connected, it is deduced that at most one set in $\{I_k\cap J_{\ell}:\ell\in L\}$ is non-empty.

So, exactly one set in $\{I_k\cap J_{\ell}:\ell\in L\}$ is non-empty, say $I_k\cap J_{\ell}$. Consequently, $I_k=I_k\cap J_{\ell}$, which in turns gives $I_k\subseteq J_{\ell}$.

In an analogous manner, starting from $J_{\ell}=\underset{k\in K}\bigcup(J_{\ell}\cap I_k)$, it is concluded that $J_{\ell}\subseteq I_k$. So, $I_k=J_{\ell}$, therefore the collections $\{I_k : k\in K\}$ and $\{J_{\ell} : \ell\in L\}$ coincide.

Proof of $\boldsymbol{\mathcal{B}(\mathbb{R})=\sigma(\pi(\mathbb{R}))}$

Let $\mathcal{O}$ be the family of open subsets in the Euclidean metric space $(\mathbb{R},\|\cdot\|)$. It will be shown that the Borel σ-algebra $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{O})$ on $\mathbb{R}$ is equal to the σ-algebra $\sigma(\pi(\mathbb{R}))$ on $\mathbb{R}$ generated by $\pi (\mathbb{R})=\{(-\infty, x]:x\in\mathbb{R}\}$.

Firstly, it will be proved that $\pi (\mathbb{R})\subseteq\sigma(\mathcal{O})$. Consider a set $(-\infty, x]\in\pi (\mathbb{R})$. Note that $(-\infty, x]=\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$. Indeed, for $y\in\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$, it holds that $(\forall n\in\mathbb{N})y. Now assume that $x, in which case $y-x>0$, so by the Archimedean property, there exists $n_o \in\mathbb{N}$ such that $0<1/n_o , whence $x+1/n_o, which is a contradiction. Thus, $y\le x$, i.e. $y\in(-\infty,x]$. It has been established that $\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)\subseteq (-\infty,x]$. Obviously  $(-\infty,x]\subseteq\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$ holds too.

Since $(-\infty,x+1/n)\in\mathcal{O}$ and $\sigma(\mathcal{O})$ is a σ-algebra on $\mathbb{R}$, the countable intersection $(-\infty, x]=\underset{n\in\mathbb{N}}{\bigcap}(-\infty,x+1/n)$ belongs to $\sigma(\mathcal{O})$.

With the help of lemma 1, $\pi (\mathbb{R})\subseteq\sigma(\mathcal{O})$ yields $\sigma(\pi (\mathbb{R}))\subseteq\sigma(\mathcal{O})=\mathcal{B}(\mathbb{R})$.

To prove the converse set inequality $\sigma(\mathcal{O}) \subseteq\sigma(\pi (\mathbb{R}))$, start by proving that $\mathcal{O}\subseteq\sigma(\pi (\mathbb{R}))$. Along these lines, consider an open set $G\in\mathcal{O}$. It is known from lemma 2 that $X$ can be written as a countable union of open intervals.

Let $(a, b)$ be one of these open intervals in the countable union. Recall from the proof of lemma 2 that $a, b$ can be infinite. Consequently, four cases are distinguished:

1. $a\in\mathbb{R}, b\in\mathbb{R}$. Set $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$, where $\epsilon=(b-a)/2$. This case will be treated in detail.
2. $a=-\infty, b\in\mathbb{R}$. Set $(-\infty, b)=\underset{n\in\mathbb{N}}{\bigcup}(-\infty,b-\epsilon/n]$, where $\epsilon=(b-a)/2$.
3. $a\in\mathbb{R}, b=\infty$. Set $(a,\infty)=\underset{n\in\mathbb{N}}{\bigcup}(a,n]$.
4. $a=\infty, b=\infty$. Set $(-\infty, \infty)=(-\infty,c]\cup(c,\infty)$ for any real $c$, which leads back to case 3.

Case 1 is now treated in detail. The equality $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$ is proved by observing that $y\in (a,b)\Leftrightarrow (\exists n_o \in\mathbb{N}) a. Leaving aside the remaining trivial deductions among these equivalences, it will be clarified that $y\in (a,b)\Rightarrow (\exists n_o \in\mathbb{N}) a. So, $y means $0 < (b-y)/\epsilon$. By the Archimedean property, there exists $n_o\in\mathbb{N}$ such that $0 < 1/n_o < (b-y)/\epsilon$, whence $y.

A set of the form $(a, u], a, can be written as $(a,u]=(-\infty, u]\cap(-\infty, a]^{c}$. So, the sets $(a,b-\epsilon/n], n\in\mathbb{N}$, appearing in $(a, b)=\underset{n\in\mathbb{N}}{\bigcup}(a,b-\epsilon/n]$ can be expressed as $(a,b-\epsilon/n]=(-\infty,b-\epsilon/n]\cap(-\infty, a]^{c}$. Thereby, $(-\infty,b-\epsilon/n]\in\pi(\mathbb{R})$ and $(-\infty,a]\in\pi(\mathbb{R})$ along with the fact that $\sigma (\pi(\mathbb{R}))$ is a σ-algebra lead to $(a,b-\epsilon/n]\in\sigma (\pi(\mathbb{R}))$. So, $(a,b)\in\sigma (\pi(\mathbb{R}))$, which implies $\mathcal{O}\subseteq\sigma(\pi (\mathbb{R}))$. Finally, $\sigma(\mathcal{O}) \subseteq\sigma(\pi (\mathbb{R}))$ by application of lemma 1, so $\mathcal{B}(\mathbb{R})=\sigma(\mathcal{O}) =\sigma(\pi (\mathbb{R}))$.

# Clarification on the σ-algebra generated by a set

This post elaborates on the concept of σ-algebra generated by a set, as presented in p. 17 of the book “Probability with martingales” by David Williams.

Let $\mathcal{C}$ be a class of subsets of a set $S$. It is stated in the book that the σ-algebra $\sigma(\mathcal{C})$ generated by $\mathcal{C}$ is the smallest σ-algebra on $S$ such that contains $\mathcal{C}$. Moreover, it is mentioned that $\sigma(\mathcal{C})$ is the intersection of all σ-algebras on $S$ that contain $\mathcal{C}$.

Three clarifications will be made. Let $\mathcal{G}:=\{\sigma\mbox{-algebra }\Sigma_i\mbox{ on }S\mbox{ with }\mathcal{C}\subseteq \Sigma_i:i\in I\}$ be the set of all σ-algebras on $S$ that contain $\mathcal{C}$.

Firstly, it will be shown that the intersection $\underset{i}{\bigcap}\Sigma_i$, which is the intersection of all σ-algebras on $S$ that contain $\mathcal{C}$, is itself a σ-algebra on $S$ that contains $\mathcal{C}$. Since $S\in\Sigma_i$ for all $i\in I$, it follows that $S\in\underset{i}{\bigcap}\Sigma_i$. Moreover, consider a set $F\in\underset{i}{\bigcap}\Sigma_i$. So $F\in\Sigma_i$ for all $i$, which means $F^{c}\in\Sigma_i$ for all $i$, so $F^{c}\in\underset{i}{\bigcap}\Sigma_i$. Let $\{F_j:j\in J\}$ be a countable collection of sets $F_j\in\underset{i}{\bigcap}\Sigma_i$. It follows that $F_j\in \Sigma_i$ for all $i\in I$ and all $j\in J$, so $\underset{j}{\bigcup}F_j\in\Sigma_i$ for all $i$, which gives $\underset{j}{\bigcup}F_j\in\underset{i}{\bigcap}\Sigma_i$. It has thus been confirmed that $\underset{i}{\bigcap}\Sigma_i$ is a σ-algebra on $S$. As $\mathcal{C}\subseteq\Sigma_i$ for all $i$, it becomes obvious that $\mathcal{C}\subseteq\underset{i}{\bigcap}\Sigma_i$, so the σ-algebra $\underset{i}{\bigcap}\Sigma_i$ on $S$ contains $\mathcal{C}$.

Consider now those σ-algebras $\Sigma_k\in\mathcal{G}$ with $\mathcal{C}\subseteq\Sigma_k$ that satisfy $\Sigma_k\subseteq\Sigma_i$ for all $\Sigma_i\in\mathcal{G}$ with $\mathcal{C}\subseteq\Sigma_i$. This is what is meant by “smallest σ-algebra $\Sigma$ on $S$ such that $\mathcal{C}\subseteq\Sigma$” in William’s book. Assume that there are two such distinct σ-algebras $\Sigma_k$ and $\Sigma_{\ell}$, i.e. $\Sigma_k\neq\Sigma_{\ell}$. Since $\Sigma_{\ell}\in\mathcal{G}$, it is then deduced that $\Sigma_k\subseteq\Sigma_{\ell}$. Similarly, $\Sigma_{\ell}\subseteq\Sigma_{k}$, so $\Sigma_k=\Sigma_{\ell}$, which is a contradiction. Hence, there is a single σ-algebra in $\mathcal{G}$ that contains $\mathcal{C}$ and is a subset of any other σ-algebra in $\mathcal{G}$ that also contains $\mathcal{C}$.

It has been shown that $\underset{i}{\bigcap}\Sigma_i\in\mathcal{G}$. Moreover, $\underset{i}{\bigcap}\Sigma_i$ satisfies $\underset{i}{\bigcap}\Sigma_i\subseteq\Sigma$ for any $\Sigma\in\mathcal{G}$. Uniqueness has also been established, so $\underset{i}{\bigcap}\Sigma_i$ is the only element in $\mathcal{G}$ that is a subset of all $\Sigma\in\mathcal{G}$. Put in words, $\underset{i}{\bigcap}\Sigma_i$ is the only σ-algebra on $S$ that contains $\mathcal{C}$ and is contained in any other σ-algebra $\Sigma$ on $S$ that satisfies $\mathcal{C}\subseteq\Sigma$.

$\underset{i}{\bigcap}\Sigma_i$ is called the σ-algebra generated by $\mathcal{C}$ and is denoted by $\sigma(\mathcal{C})$.

# Clarification on algebras and σ-algebras of a set

David Williams makes a terminological remark on algebras in p. 16 of his book “Probability with martingales”; he mentions that an algebra $\Sigma$ on a set $S$ (defined ordinarily as a collection of subsets of $S$ that contains $S$ and that is closed under set complementation and closed under finite set unions) is “a true algebra in the algebraists’ sense”.

This remark emphasises two aspects of the concept of algebra $\Sigma$ on a set $S$. Firstly, it means that $\Sigma$ is an algebra over a field $K$. The field $K$ contains exactly two elements, so it can be defined to be the subset $K=\{0,1\}$ of integers. According to the definition of algebra over a field, $\Sigma$ is a vector space equipped with a bilinear product. So any algebra (and consequently any σ-algebra) is a type of vector space of sets (subsets of $S$).

Secondly, consider the defining operations of an algebra $\Sigma$ on a set $S$. The vector space addition is defined to be the symmetric difference $A\Delta B:= (A\cup B)\setminus (A\cap B)$. The bilinear product, which turns the vector space to an algebra over $\{0,1\}$, is the set intersection $A\cap B$. It is straightforward to check that the product $A\cap B$ satisfies right and left distributivity and compatibility with scalars. The two operations (addition and bilinear product) defined from the product space $\Sigma\times\Sigma$ to the vector space $\Sigma$ are both symmetric.

In summary, any algebra (and any σ-algebra) is a vector space of sets equipped with two symmetric set operations.