Inductive Construction of Sigma-Algebra Generated by Collection of Subsets

== Theorem ==
Let $\EE$ be a set of sets which are subsets of some set $X$.
Let $\map \sigma \EE$ be the $\sigma$-algebra generated by $\EE$.
Then $\map \sigma \EE$ can be constructed inductively.
The construction is as follows:
Let $\Omega$ denote the minimal uncountable well-ordered set.
Let $\alpha$ be an arbitrary initial segment in $\Omega$.
Considering separately the cases whether or not $\alpha$ has an immediate predecessor $\beta$, we define:
:$\EE_1 = \EE$
:$\EE_\alpha = \begin{cases} \set {\SS \in \powerset {\EE_\beta}: \SS \text { is countable or } \SS^\complement \text{ is countable} } & \alpha \text{ has an immediate predecessor } \beta \\
\ds \bigcup_{\beta \mathop \prec \alpha} \EE_\beta & \text { otherwise} \end{cases}$
:$\EE_\Omega = \ds \bigcup_{\alpha \mathop \in \Omega} \EE_\alpha$
Then:
:$\map \sigma \EE = \EE_\Omega$
=== Corollary ===
== Proof ==
=== Step 1 ===
We will show that:
:$\map \sigma \EE \subseteq \EE_\Omega$.
Define: 
:$\OO := \set {o \in \Omega: \EE_o \in \map \sigma \EE}$
By the definition of a $\sigma$-algebra:
:$\EE_1 \subseteq \map \sigma \EE$.
From $\sigma$-Algebra of Countable Sets, if $\beta$ immediately precedes $\alpha$, then $\EE_\alpha$ is a $\sigma$-algebra containing $\EE_\beta$.
If $\beta$ strictly precedes $\alpha$ but is not an immediate predecessor of $\alpha$, then $\EE_\alpha$ is a countable union of measurable sets.
By the definition of a $\sigma$-algebra and of union, $\EE_\alpha$ is a $\sigma$-algebra containing $\EE_\beta$.
Thus the hypotheses of well-ordered induction are satisfied, and:
:$\OO = \Omega$
Thus:
:$\EE_\alpha \subseteq \map \sigma \EE$ 
for all $\alpha \in \Omega$
By Set Union Preserves Subsets:General Result:
:$\ds \bigcup_{\alpha \mathop \in \Omega} \EE_\alpha \subseteq \map \sigma \EE$
Thus:
:$\EE_{\Omega} \subseteq \map \sigma \EE$
=== Step 2 ===
We identify numbers in $\N$ with the finite ordinals, using the definition of ordinals as initial segments.
This identification is justified from Minimally Inductive Set forms Peano Structure.
Thus every $j \in \N$ can be treated as a finite initial segment of $\Omega$.
By the definition of a $\sigma$-algebra generated by $\EE$, the reverse inclusion:
:$\EE_\Omega \supseteq \map \sigma \EE$
will follow if $\EE_\Omega$ is a $\sigma$-algebra.
First note that:
:$\EE = \EE_1 \in \EE_\Omega$
so $\EE_\Omega$ has a unit.
Let: 
:$\family {E_j}_{j \mathop \in \N}$
be an arbitrary countable indexed family of sets in $\EE_\Omega$.
By the inductive construction of $\EE_\Omega$, for all $j \in \N$:
:$E_j, E_j^\complement \in \EE_{\alpha_j}$
for some initial segment $\alpha_j$, 
Thus $\EE_\Omega$ is closed under complement.
The set:
:$\family {\alpha_i}_{i \mathop \in \N} = \set {\alpha_1, \alpha_2, \alpha_3, \ldots}$
is countable, because it is indexed by $\N$.
By Countable Subset of Minimal Uncountable Well-Ordered Set Has Upper Bound, $\family {\alpha_i}$ has an upper bound.
Call this bound $\gamma$.
Then $\EE_\gamma$ is an initial segment.
Also, $E_j \in \EE_\gamma$ for all $j \in \N$, by the definition of upper bound.
For any $\delta$ strictly succeeding $\gamma$:
:$\ds \bigcup_{j \mathop \in \N} E_j \in \EE_\delta$
Thus by the construction of $\EE_\Omega$:
:$\EE_\delta \subseteq \EE_\Omega$
This means that $\EE_\Omega$ is closed under countable union.
We have that:
:$\EE_\Omega$ has a unit
:$\EE_\Omega$ is closed under complement.
:$\EE_\Omega$ is closed under countable union.
By the definition of $\sigma$-algebra, $\EE_\Omega$ is indeed a $\sigma$-algebra.
By the definition of a generated $\sigma$-algebra:
:$\map \sigma \EE \subseteq \EE_\Omega$
The result follows from Part 1 and Part 2 of the proof combined, by the definition of set equality.
== Sources ==
* : $\S 1.23$
Category:Sigma-Algebras