[Math] Example of generated sigma-algebra

measure-theory

I looked at the definition of a generated $\sigma$-algebra in wikipedia (https://en.wikipedia.org/wiki/Sigma-algebra) and would like to know if this is correct.

Let $X=\{1,2,3,4\}$ and $F=\{\{1\},\{2\}\}$. Is it correct that $\sigma(F)=\{\emptyset,\{1,2,3,4\},\{1\},\{2,3,4\},\{2\},\{1,3,4\}\}$? Thanks.

edit: The correct answer is $\sigma(F)=\{\emptyset,\{1,2,3,4\},\{1\},\{2,3,4\},\{2\},\{1,3,4\},\{1,2\},\{3,4\}\}$.

Best Answer

You missed $$\{ 3,4 \} = \{ 1,3,4 \} \cap \{ 2,3,4 \}$$ and $$\{ 1,2 \} = \{ 1 \} \cup \{ 2 \}$$ Adding these two, you get a $\sigma$-algebra.

Related Solutions

[Math] Generated $\sigma$-algebra question

As a general comment on this kind of construction, I might suggest reading this answer.

Generally speaking, what you describe is the "top-down" approach to the construction. It is not, generally, practical to actually know the description of the elements in the generated object. For that, you want the "bottoms-up" construction. In the question linked-to above, Asaf Kargila provides the description of the bottoms-up construction.

In your particular case, of course, since $E$ is small (3 elements), so $P(E)$ is small (8 elements), the number of possible $\sigma$-algebras is somewhat manageable (though still large).

What are all $\sigma$-algebras on $E=\{1,2,3\}$ that contain $\{1\}$ as an element? They must contain $\emptyset$, $\{1\}$, $\{2,3\}$, and $E$. There are 4 other elements in $P(E)$ which may or may not be in a $\sigma$-algebra.

One $\sigma$-algebra is just $\{\emptyset, \{1\}, \{2,3\}, E\}$.
If the $\sigma$-algebra contains either $\{2\}$ or $\{3\}$ in addition to those, then it must also contain the other (symmetric difference with $\{2,3\}$), and hence be all of $P(E)$.
If the $\sigma$-algebra contains any other $2$-element subset, then it must contain another singleton (symmetric difference with $\{2,3\}$), hence must be all of $P(E)$.

So in fact the only $\sigma$-algebras on $E$ that contain $\{1\}$ are $\{\emptyset, \{1\},\{2,3\}, E\}$ and $P(E)$. The intersection is just $\{\emptyset,\{1\},\{2,3\},E\}$, so the $\sigma$-algebra generated by $\{1\}$ is $\{\emptyset, \{1\}, \{2,3\}, E\}$.

Number of Sigma Algebras for a Set with Four Elements

As noted in the comments, it suffices to count the number of partitions of $X$ in nonempty parts. The number of partitions of a set $X$ of cardinality $n$ in $k$ nonempty parts is denoted $\left\lbrace\begin{matrix} n \\ k \end{matrix}\right\rbrace$. Those numbers are called Stirling numbers of the second kind. Up to relabeling, a partition of $X$ into $k$ nonempty parts is the same thing as a surjection $X \to \lbrace 1,2,\ldots ,k\rbrace$. Since there are $k!$ such relabelings, the number of such surjections is $k!\left\lbrace\begin{matrix} n \\ k \end{matrix}\right\rbrace$.

Let $[k]$ denote the inetger interval $\lbrace 1,2,\ldots ,k\rbrace$, $F(X,k)$ denote the set of all maps $X \to [k]$, and for a given set $A$, denote by $S(X,A)$ the set of all surjections $X \to A$. So $|S(X,A)|=|A|!\left\lbrace\begin{matrix} n \\ |A| \end{matrix}\right\rbrace$, and $F(X,k)$ is obviously partitioned by all the $S(X,A)$ for $A\subseteq [k]$. Since there are $\binom{k}{r}$ subsets of cardinality $r$ in $[k]$, we see that

$$ k^n=|F(X,k)|=\sum_{r=0}^k \binom{k}{r} r! \left\lbrace\begin{matrix} n \\ r\end{matrix}\right\rbrace = \sum_{r=0}^k \frac{k!}{(k-r)!} \left\lbrace\begin{matrix} n \\ r\end{matrix}\right\rbrace= k! \left\lbrace\begin{matrix} n \\ k\end{matrix}\right\rbrace+ \sum_{r=1}^{k-1} \frac{k!}{(k-r)!} \left\lbrace\begin{matrix} n \\ r\end{matrix}\right\rbrace $$

and hence

$$ \left\lbrace\begin{matrix} n \\ k \end{matrix}\right\rbrace= \frac{k^n}{k!}-\sum_{r=1}^{k-1} \frac{\left\lbrace\begin{matrix} n \\ r\end{matrix}\right\rbrace}{(k-r)!} $$

Starting from the obvious $\left\lbrace\begin{matrix} n \\ 1 \end{matrix}\right\rbrace=1$, we deduce successively that $$ \begin{array}{lclcl} \left\lbrace\begin{matrix} n \\ 2 \end{matrix}\right\rbrace &=& \frac{2^n}{2!}- \frac{\left\lbrace\begin{matrix} n \\ 1\end{matrix}\right\rbrace}{1!} &=& 2^{n-1}-1 \\ \left\lbrace\begin{matrix} n \\ 3 \end{matrix}\right\rbrace &=& \frac{3^n}{6!}- \frac{\left\lbrace\begin{matrix} n \\ 1\end{matrix}\right\rbrace}{2!}- \frac{\left\lbrace\begin{matrix} n \\ 2\end{matrix}\right\rbrace}{1!} &=& \frac{3^{n-1}-1}{2}-(2^{n-1}-1) \\ \end{array} $$

In your example $n=4$ and hence

$$ \left\lbrace\begin{matrix} 4 \\ 1\end{matrix}\right\rbrace=1, \ \left\lbrace\begin{matrix} 4 \\ 2\end{matrix}\right\rbrace=2^{4-1}-1=7, \ \left\lbrace\begin{matrix} 4 \\ 3\end{matrix}\right\rbrace=\frac{3^{4-1}-1}{2}-(2^{4-1}-1)=6, \ \left\lbrace\begin{matrix} 4 \\ 4\end{matrix}\right\rbrace= 1 $$

So the total number of partitions you’re looking for is $1+7+6+1=15$.

Best Answer

Related Solutions

[Math] Generated $\sigma$-algebra question

Number of Sigma Algebras for a Set with Four Elements

Related Question