$\sigma$-algebras on a countable set is generated by partitions of the set

Let $X$ be a countable set, show that every $\sigma$-algebra is generated by a partition of $X$.

I don't even know how to start. I 've been stuck on this problem for a long time. Any hints are welcomed.

Solution 1:

Sketch of proof: For each $x\in X$, we want to find the smallest element in our $\sigma$-algebra which contains $x$. Then these building blocks will serve to partition $X$ and generate our $\sigma$-algebra.

Fix $x\in X$. For $y\in X$, either our $\sigma$-algebra can separate $x$ from $y$ or it can't. If it can, let $L_{x, y}$ be a set in our $\sigma$-algebra which contains $x$ and does not contain $y$. If it can't, let $L_{x, y} = X$. Then $\cap_{y \in X} L_{x, y}$ is the smallest set in the $\sigma$-algebra which contains $x$ (formally, it's equal to the intersection over all elements in the $\sigma$-algebra containing $x$ - I'll omit that proof).

If $z \in \cap_{y \in X} L_{x, y}$, then $\cap_{y \in X} L_{z, y} \subset \cap_{y \in X} L_{x, y}$ since $\cap_{y \in X} L_{z, y}$ is the smallest measurable set containing $z$. Applying this symmetrically, we must have $\cap_{y \in X} L_{x, y} = \cap_{y \in X} L_{z, y}$. So these small sets are either the same or disjoint, and thus they form a partition of $X$ which generates the $\sigma$-algebra.