Number of sigma algebras for set with 4 elements 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?
 A: 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$.
