Proof of Dynkin's Pi-Lambda Theorem

Throughout, $\sigma$-algebras, $\pi$-systems and $\lambda$-systems are on $X$, and the union $\bigcup_{n\in\mathbb{N}}A_{n}$ of a sequence $(A_{n})_{n\in\mathbb{N}}$ is the union of the family, whose elements are the $x$ with $x\in A_{n}$ for some $n\in\mathbb{N}$.

Proof of (i). Let $\mathcal{F}$ be a $\sigma$-algebra. By σ-Algebra and Measurable Space (i), $\mathcal{F}\subseteq\mathcal{P}(X)$, $X\in\mathcal{F}$, $X\setminus A\in\mathcal{F}$ for every $A\in\mathcal{F}$, and the union of every sequence in $\mathcal{F}$ lies in $\mathcal{F}$, in particular the union of every sequence in $\mathcal{F}$ with pairwise disjoint terms; so $\mathcal{F}$ is a $\lambda$-system by λ-System (i). By Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (ix), $A\cap B\in\mathcal{F}$ for all $A,B\in\mathcal{F}$, so $\mathcal{F}$ is a $\pi$-system by π-System (i).

Conversely, let $\mathcal{F}\subseteq\mathcal{P}(X)$ be both a $\pi$-system and a $\lambda$-system. By λ-System (i), $X\in\mathcal{F}$ and $X\setminus A\in\mathcal{F}$ for every $A\in\mathcal{F}$. Let $(A_{n})_{n\in\mathbb{N}}$ be a sequence in $\mathcal{F}$. Once $\bigcup_{n\in\mathbb{N}}A_{n}\in\mathcal{F}$ is shown, $\mathcal{F}$ is a $\sigma$-algebra by σ-Algebra and Measurable Space (i). For $n\in\mathbb{N}$ let

$$C_{n}=\{x\in X:x\notin A_{k}\text{ for every }k\in\mathbb{N}\text{ with }k<n\},\qquad B_{n}=A_{n}\cap C_{n}.$$

First, $C_{n}\in\mathcal{F}$ for every $n\in\mathbb{N}$. There is no $k\in\mathbb{N}$ with $k<1$: by Arithmetic and Order of the Natural Numbers (x) and Arithmetic and Order of the Natural Numbers (vi), $1<k$ or $1=k$, and neither is compatible with $k<1$ by Arithmetic and Order of the Natural Numbers (vii). Hence $C_{1}=X\in\mathcal{F}$. Let $n\in\mathbb{N}$ with $C_{n}\in\mathcal{F}$. For $k\in\mathbb{N}$, $k<n+1$ holds if and only if $k<n$ or $k=n$ (as $n+1$ is the successor $S(n)$ of $n$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication (v), $k<n+1$ holds if and only if $k\le n$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (iv), that is, if and only if $k<n$ or $k=n$ by Arithmetic and Order of the Natural Numbers (vi)). Hence $C_{n+1}=C_{n}\cap(X\setminus A_{n})$, which lies in $\mathcal{F}$ by π-System (i), as $C_{n}$ and $X\setminus A_{n}$ do. By Arithmetic and Order of the Natural Numbers (xiii), applied to the set of all $n\in\mathbb{N}$ with $C_{n}\in\mathcal{F}$, the claim holds for every $n\in\mathbb{N}$.

Consequently $B_{n}\in\mathcal{F}$ for every $n\in\mathbb{N}$, by π-System (i), and $n\mapsto B_{n}$ is a sequence in $\mathcal{F}$ (by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (iv), applied to $(A_{n})$, a sequence in $\mathcal{P}(X)$ as $\mathcal{F}\subseteq\mathcal{P}(X)$, there are sequences $(C'_{n})$ and $(B'_{n})$ in $\mathcal{P}(X)$ with $C'_{1}=X$, $C'_{n+1}=C'_{n}\cap(X\setminus A_{n})$ and $B'_{n}=A_{n}\cap C'_{n}$ for every $n\in\mathbb{N}$; by the identities $C_{1}=X$ and $C_{n+1}=C_{n}\cap(X\setminus A_{n})$ shown above, whose derivation does not use $C_{n}\in\mathcal{F}$, and Arithmetic and Order of the Natural Numbers (xiii), $C'_{n}=C_{n}$, and so $B'_{n}=B_{n}$, for every $n\in\mathbb{N}$; and $(B'_{n})$ is a sequence in $\mathcal{F}$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v)). Its terms are pairwise disjoint: let $m,n\in\mathbb{N}$ with $m\neq n$; by Arithmetic and Order of the Natural Numbers (vii), $m<n$ or $n<m$, and as disjointness is symmetric we may take $m<n$; then every element of $B_{n}\subseteq C_{n}$ lies outside $A_{m}$, while $B_{m}\subseteq A_{m}$, so $B_{m}$ and $B_{n}$ are disjoint. Hence $\bigcup_{n\in\mathbb{N}}B_{n}\in\mathcal{F}$ by λ-System (i).

Finally $\bigcup_{n\in\mathbb{N}}B_{n}=\bigcup_{n\in\mathbb{N}}A_{n}$. As $B_{n}\subseteq A_{n}$ for every $n$, the left side is contained in the right. Conversely, let $x\in A_{n}$ for some $n\in\mathbb{N}$. The set $S=\{k\in\mathbb{N}:x\in A_{k}\}$ has the element $n$, so by Arithmetic and Order of the Natural Numbers (xv) it has an element $m$ with $m\le v$ for every $v\in S$. For $k\in\mathbb{N}$ with $k<m$ we have $x\notin A_{k}$: otherwise $k\in S$, so $m\le k$, that is $m<k$ or $m=k$ by Arithmetic and Order of the Natural Numbers (vi), and either contradicts $k<m$ by Arithmetic and Order of the Natural Numbers (vii). As $x\in A_{m}\subseteq X$, it follows that $x\in C_{m}$, hence $x\in B_{m}$. Thus $\bigcup_{n\in\mathbb{N}}A_{n}=\bigcup_{n\in\mathbb{N}}B_{n}\in\mathcal{F}$.

Disjoint pairs in a $\lambda$-system. Let $\mathcal{M}$ be a $\lambda$-system and let $A,B\in\mathcal{M}$ be disjoint. Then $A\cup B\in\mathcal{M}$. Indeed, $X\setminus X\in\mathcal{M}$ by λ-System (i); the set $X\setminus X$ has no element, so it equals the empty set $\emptyset$ by Elements Are Sets, and the Empty Set and the Pair of Two Sets Exist and Are Unique (ii), and $\emptyset\in\mathcal{M}$. By Arithmetic and Order of the Natural Numbers (xiv), $2=1+1$ is a natural number, and $2\neq1$ by Arithmetic and Order of the Natural Numbers (xi). For $n\in\mathbb{N}$ let

$$E_{n}=\{x\in A:n=1\}\cup\{x\in B:n=2\}.$$

Then $E_{1}=A$ and $E_{2}=B$, and for every $n\in\mathbb{N}$ other than $1$ and $2$ the set $E_{n}$ has no element, so $E_{n}=\emptyset$ by Elements Are Sets, and the Empty Set and the Pair of Two Sets Exist and Are Unique (ii); so $n\mapsto E_{n}$ is a sequence in $\mathcal{M}$ (as $A,B\subseteq X$, because $\mathcal{M}\subseteq\mathcal{P}(X)$, Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (iii) gives a sequence in $\mathcal{P}(X)$ with first term $A$, second term $B$ and every other term $\emptyset$, which is $n\mapsto E_{n}$; it is a sequence in $\mathcal{M}$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v), as $A$, $B$ and $\emptyset$ lie in $\mathcal{M}$). Its terms are pairwise disjoint: if $x\in E_{m}\cap E_{n}$ for some $m,n\in\mathbb{N}$ with $m\neq n$, then each of $m$ and $n$ is $1$ or $2$, so one of them is $1$ and the other is $2$, and $x\in A\cap B$, which has no element. Its union is $A\cup B$, as every $E_{n}$ is contained in $A\cup B$ while $A=E_{1}$ and $B=E_{2}$. Hence $A\cup B\in\mathcal{M}$ by λ-System (i).

Proper differences in a $\lambda$-system. Let $\mathcal{M}$ be a $\lambda$-system and let $A,B\in\mathcal{M}$ with $A\subseteq B$. Then $B\setminus A\in\mathcal{M}$. Indeed, $X\setminus B\in\mathcal{M}$ by λ-System (i), and $A$ and $X\setminus B$ are disjoint as $A\subseteq B$; so $A\cup(X\setminus B)\in\mathcal{M}$ by the paragraph on disjoint pairs, and $X\setminus\bigl(A\cup(X\setminus B)\bigr)\in\mathcal{M}$ by λ-System (i). This set is $B\setminus A$: its elements are the $x\in X$ with $x\notin A$ and $x\in B$, and $B\subseteq X$ since $\mathcal{M}\subseteq\mathcal{P}(X)$.

Proof of (ii). Let

$$\mathcal{L}_{0}=\{B\in\mathcal{P}(X):B\in\mathcal{M}\text{ for every }\lambda\text{-system }\mathcal{M}\text{ on }X\text{ with }\mathcal{E}\subseteq\mathcal{M}\}.$$

This is a set (by Predicative Formulas for σ-Algebras, π-Systems and λ-Systems, and the Sets of Them Containing a Given Family (iii), applied with $\mathcal{C}=\mathcal{E}$, a subset of $\mathcal{P}(X)$ by π-System (i), the $\lambda$-systems $\mathcal{M}$ on $X$ with $\mathcal{E}\subseteq\mathcal{M}$ are the elements of a set $\mathcal{S}$, and $\mathcal{L}_{0}$ is the set of those $B\in\mathcal{P}(X)$ with $B\in\mathcal{M}$ for every $\mathcal{M}\in\mathcal{S}$). Then $\mathcal{E}\subseteq\mathcal{L}_{0}$, since $\mathcal{E}\subseteq\mathcal{P}(X)$ by π-System (i), and $\mathcal{L}_{0}\subseteq\mathcal{L}$, since $\mathcal{L}$ is one of the $\lambda$-systems $\mathcal{M}$ in the condition. Moreover, if $\mathcal{M}$ is a $\lambda$-system with $\mathcal{E}\subseteq\mathcal{M}$, then $\mathcal{L}_{0}\subseteq\mathcal{M}$.

$\mathcal{L}_{0}$ is a $\lambda$-system. It is a subset of $\mathcal{P}(X)$. By λ-System (i), applied to each $\lambda$-system $\mathcal{M}$ with $\mathcal{E}\subseteq\mathcal{M}$: $X$ lies in every such $\mathcal{M}$, so $X\in\mathcal{L}_{0}$; for $A\in\mathcal{L}_{0}$, $X\setminus A$ is a subset of $X$ lying in every such $\mathcal{M}$, so $X\setminus A\in\mathcal{L}_{0}$; and a sequence in $\mathcal{L}_{0}$ with pairwise disjoint terms is a sequence in every such $\mathcal{M}$, as $\mathcal{L}_{0}\subseteq\mathcal{M}$, so its union lies in every such $\mathcal{M}$, and that union is a set by The Union and Product of a Family of Sets Indexed by a Set, and the Intersection of a Family with an Inhabited Index Class, Are Sets (i), contained in $X$ as every term is; so the union lies in $\mathcal{L}_{0}$.

For $A\in\mathcal{L}_{0}$ let $\mathcal{D}_{A}=\{B\in\mathcal{P}(X):A\cap B\in\mathcal{L}_{0}\}$. Then $\mathcal{D}_{A}$ is a $\lambda$-system. First, $X\in\mathcal{D}_{A}$, as $A\cap X=A$. Next let $B\in\mathcal{D}_{A}$. As $A\subseteq X$, $A\cap(X\setminus B)=A\setminus(A\cap B)$, where $A\cap B\subseteq A$ and both lie in $\mathcal{L}_{0}$; so $A\cap(X\setminus B)\in\mathcal{L}_{0}$ by the paragraph on proper differences, applied to the $\lambda$-system $\mathcal{L}_{0}$, and $X\setminus B\in\mathcal{D}_{A}$. Last let $(B_{n})_{n\in\mathbb{N}}$ be a sequence in $\mathcal{D}_{A}$ with pairwise disjoint terms. Then $n\mapsto A\cap B_{n}$ is a sequence in $\mathcal{L}_{0}$ (Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (ii), applied with $Y=A$ to the sequence $(B_{n})$ in $\mathcal{D}_{A}$, gives a sequence in $\mathcal{P}(A)$, hence in $\mathcal{P}(X)$ as $A\subseteq X$, with terms $B_{n}\cap A=A\cap B_{n}$; it is a sequence in $\mathcal{L}_{0}$ by Sequences and Maps of Sets: Complements, Traces, Two-Term Sequences, the Disjointing Sequence, and Sequences in a Subset (v), as $A\cap B_{n}\in\mathcal{L}_{0}$ for every $n$ by the definition of $\mathcal{D}_{A}$) whose terms are pairwise disjoint, as $(A\cap B_{m})\cap(A\cap B_{n})\subseteq B_{m}\cap B_{n}$; so its union lies in $\mathcal{L}_{0}$ by λ-System (i). That union is $A\cap\bigcup_{n\in\mathbb{N}}B_{n}$, and $\bigcup_{n\in\mathbb{N}}B_{n}$ is a set by The Union and Product of a Family of Sets Indexed by a Set, and the Intersection of a Family with an Inhabited Index Class, Are Sets (i), contained in $X$; so $\bigcup_{n\in\mathbb{N}}B_{n}\in\mathcal{D}_{A}$. By λ-System (i), $\mathcal{D}_{A}$ is a $\lambda$-system, and therefore $\mathcal{L}_{0}\subseteq\mathcal{D}_{A}$ whenever $\mathcal{E}\subseteq\mathcal{D}_{A}$.

Let $C\in\mathcal{E}$. Then $C\in\mathcal{L}_{0}$, and $C\cap B\in\mathcal{E}\subseteq\mathcal{L}_{0}$ for every $B\in\mathcal{E}$ by π-System (i); so $\mathcal{E}\subseteq\mathcal{D}_{C}$, hence $\mathcal{L}_{0}\subseteq\mathcal{D}_{C}$, that is, $C\cap B\in\mathcal{L}_{0}$ for every $B\in\mathcal{L}_{0}$. Now let $A\in\mathcal{L}_{0}$. For $C\in\mathcal{E}$, $A\cap C=C\cap A\in\mathcal{L}_{0}$ by what was just shown; so $\mathcal{E}\subseteq\mathcal{D}_{A}$, hence $\mathcal{L}_{0}\subseteq\mathcal{D}_{A}$, that is, $A\cap B\in\mathcal{L}_{0}$ for every $B\in\mathcal{L}_{0}$. Thus $\mathcal{L}_{0}$ is a $\pi$-system by π-System (i), and, being also a $\lambda$-system, a $\sigma$-algebra by (i). As $\mathcal{E}\subseteq\mathcal{L}_{0}$, Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (iv) gives $\sigma(\mathcal{E})\subseteq\mathcal{L}_{0}$, and so $\sigma(\mathcal{E})\subseteq\mathcal{L}_{0}\subseteq\mathcal{L}$.

Proof of (iii). Let $\mathcal{L}_{0}$ be as in the proof of (ii); it is the set described in (iii), and $\sigma(\mathcal{E})\subseteq\mathcal{L}_{0}$ was shown there. By Closure Properties of σ-Algebras, Intersections and Traces of σ-Algebras, and the Generated σ-Algebra (iii), $\sigma(\mathcal{E})$ is a $\sigma$-algebra with $\mathcal{E}\subseteq\sigma(\mathcal{E})$, so it is a $\lambda$-system by (i), and hence $\mathcal{L}_{0}\subseteq\sigma(\mathcal{E})$. Therefore $\sigma(\mathcal{E})=\mathcal{L}_{0}$.