I am supposed to watch out for sigma algebras that belong to the set $X=\{1,2,3,4\}$. I found 15(now with the new set even more) of them. I was wondering whether there is some nice proof how to see that there are no more of them? The problem is, that I would try to prove this by looking at a lot of different cases, how a new sigma-algebra would have to look like and prove then that it already is the whole set. Does anybody here have a better idea?
only the set and the empty one//
the set of all subsets//
4 sets, where you take the set, the empty one and one element with its complement.//
3 sets with the empty one, the set itself and a set containing two elements and its complement.//
EDIT:
I have even found 6 of another type that are possible, just like: $\Sigma = \{\{1\},\{2\},\{1,2\},\{3,4\},\{1,3,4\},\{2,3,4\},\emptyset,X\}$
Does anybody have an idea?
Best Answer
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$.