Generate the smallest $\sigma$-algebra containing a given family of sets

My teacher gave me an example of performing the subject:

Example

Let $\Omega = \Bbb R$ and $\mathcal R = \{(-\infty,-1),(1,+\infty)\}$. Then $\sigma(\mathcal R) = \{\emptyset, \Bbb R, (-\infty,-1), (1,+\infty), [-1, \infty), (-\infty,1], (-\infty,-1)\cup(1,+\infty),[-1,1]\}$.

There was a different example, where she also generated the smallest $\sigma$-algebra for the family of sets $\mathcal A = \{A,B\} \subset 2^\Omega$ in the same way: $\sigma(\mathcal R) = \{\emptyset, \Omega, A, B, A^C,B^C,A\cup B, (A\cup B)^C\}$.

I certainly understand why $\emptyset$, $\Omega$ and a family of sets itself are there, and I certainly know that $\sigma$-algebra is closed under the operations of complement and union. What I don't understand about the other elements of generated $\sigma$-algebras: why we are taking exactly them? Does this work in a general case?

-
You will need $A \cap B \in \sigma(\mathcal{R})$. Also the requirement is for countable unions not arbitrary unions. –  Jay Oct 11 '12 at 19:12
Be careful to be specific about what types of union operations $\sigma$-fields are closed under: you should realize specifically that a family of sets that meets the other conditions but is closed only under finite unions (e.g., $A, B \in \mathcal{A}$ implies $A \cup B \in \mathcal{A}$), but not countable unions (e.g., $A_1, A_2, \dotsc \in \mathcal{A}$ does not imply $\bigcup_{n=1}^\infty A_n \in \mathcal{A}$) is not a $\sigma$-field. –  Firefeather Oct 11 '12 at 19:18

You start with a set of sets, in your example, $\{A,B\}$. To obtain the smallest $\sigma$-algebra containing it, all you need to do is add the missing sets that make it a $\sigma$-algebra (instead of just being a set).

What this means is that you want to add all sets so that the resulting set is closed with respect to taking complements and union. To make $\{A,B\}$ closed with respect to taking complements you need to add $A^c, B^c$. To make it closed with respect to union you need to add $A \cup B$. Now you have added new elements and again you need to add all elements so that the new set of sets is closed under complement and union. Hence you need to add $A^c \cup B^c = (A \cap B)^c$ and $(A \cup B)^c = A^c \cap B^c$. Next you need to add $A \cap B$ (to make it closed with respect to complements).

So far we have $\{ A, B, A^c , B^c, A \cup B, (A \cup B)^c, A^c \cup B^c , A \cap B \}$. Do we need to add any more sets? Or does this set constitute a $\sigma$-algebra?

-
At least we need to add $\emptyset$ and $\Omega$. The (my) problem is to show that we don't need something else (if we don't). –  Victor Oct 11 '12 at 19:21
This is of course just A∪B, which is already in the σ-algebra. But it's just a special case. I don't know how to prove that this σ-algebra is OK in general. –  Victor Oct 11 '12 at 19:37
Your σ-algebra doesn't contain at least (A∩B)∪($A\cup B)^C$. –  Victor Oct 11 '12 at 20:16
I think now I understand. We're just keep going with constructing unions and complements until there's nothing more to do. It means that we've obtained a σ-algebra by definition, and it is obviously the smallest one as it wouldn't be a σ-algebra without any single element. I've also understood why there's no general recipe. But there certainly should exist an upper bound on the number of elements in the generated σ-algebra if we talk about a finite number of sets in the family, since there's a finite number of different combinations of sets (complements, unions). –  Victor Oct 12 '12 at 9:46
Yes, that's exactly what I meant. If there is a σ-algebra σ($\mathcal A$) which is smaller than our $\mathcal F$, than σ($\mathcal A$)$\subset \mathcal F$ - contradiction, because it can't be a σ-algebra. As for my "understanding", it's just an intuitive idea: there can be different "relations" between sets of a family - "gaps" between them, or "overlaps". I'm thinking about an example σ$(\{A, A^C\}) = \{\emptyset, \Omega, A, A^C\}$. –  Victor Oct 12 '12 at 13:15

Here is a simple recipe for finding the $\sigma$-algebra generated by a finite family $\mathcal{F}$ of subsets of a set $\Omega$: For each $\omega\in \Omega$, let $$A(\omega)=\bigcap\Big\{A\ni\omega:A\in\mathcal{F}\text{ or } A^C\in\mathcal{F}\Big\}$$ be the atom containing $\omega$. Then the $\sigma$-algebra generated by $\mathcal{F}$ consists of all finite unions of sets of the form $A(\omega)$. Note that $\emptyset$ is a union of finitely many such sets ($0$ many, to be exact).

Justification: Clearly, all such finite unions must be in the $\sigma$-algebra generated. On the other hand, the $A(\omega)$ form a finite partition of $\Omega$, so the set of finite unions forms a $\sigma$-algebra. It is easy to see that every $F\in\mathcal{F}$ has the form $\bigcup_{\omega\in F} A(\omega)$, a union of finitely many sets.

In general, there is no easy recipe for writing down the generated $\sigma$-algebra when $\mathcal{F}$ is infinite. There exists a construction based on transfinite recursion in $\omega_1$ many steps, but that is much more sophisticated.

-
For some strange reason, I got stuck in my head "Rebel Yell", and I went to the Tube to listen; and I saw this album cover and it took me back to that beer we had with that song in the background. I realized that in that photo, you look a bit like him (modulo the hair, and the bulging 80's-ness that is). –  Asaf Karagila Oct 28 '12 at 15:32
@Asaf Maybe I should try that look some time. The next 80s party is coming... –  Michael Greinecker Oct 28 '12 at 15:37
Well, it's better to be an Idol than it is to be a Joel. At least when it comes to the hill Billies... :-) –  Asaf Karagila Oct 28 '12 at 15:40

The sigma needs to contain $\varnothing$, $\Omega$, $A$ and $B$. Since a sigma algebra is closed under countable unions and complements it must contain $A \cup B$, $A^{C}$, and $B^{C}$.Since a sigma algebra is closed under complements it must contain $(A^{C} \cup B^{C})^{C} = A \cap B$. A more general construction of a sigma algebra from $\mathcal{A} \subseteq 2^{X}$ is a follows:

The construction is in stages indexed by the ordinals.

Stage $0$. $\sigma_{0} = \mathcal{A} \cup \{ \varnothing, X\}$.

Stage $\alpha + 1$. We suppose we have defined $\sigma_{\alpha}$. Then $\sigma_{\alpha + 1} = \sigma_{\alpha} \cup \{ \cup f(i)\colon f: \mathbb{N} \rightarrow \sigma_{\alpha} \} \cup \{ X \smallsetminus \cup f(i)\colon f: \mathbb{N} \rightarrow \sigma_{\alpha} \}$.

Stage $\lambda$. Here $\lambda$ is a limit ordinal. We suppose that we have defined $\sigma_{\alpha}$ for all $\alpha < \lambda$. The $\sigma_{\lambda} = \cup \{ \sigma_{\alpha} \colon \alpha < \lambda \}$.

This step might require the axiom of choice. With this construction $\sigma_{\aleph_{1}}$ is the smallest sigma algebra containing $\mathcal{A}$. Stage $\alpha + 1$ guarantees if something is in the collection its complement is also in the collection. Suppose the for each $i \in \mathbb{N}$ we have $A_{i} \in \sigma_{\aleph_{1}}$. For each $i \ in \mathbb{N}$ there exists a least countable $\alpha_{i}$ with $A_{i} \in \sigma_{i}$. Possibly using the axiom of choice there is a countable ordinal $\alpha^{*}$ greater than any of the $\alpha_{i}$. We will have both $\cup \{A_{i} \colon i \in \mathbb{N} \} \in \sigma_{\alpha^{*}}$ and $X \smallsetminus \cup \{A_{i} \colon i \in \mathbb{N} \} \in \sigma_{\alpha^{*}}$.

-