# 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.