# $\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.

• Hint: Given a $\sigma$-algebra on $X$, we want to find a bunch of small building blocks for our $\sigma$-algebra which partition $X$. For a given $x\in X$, consider the intersection of all elements of your $\sigma$-algebra which contain $x$. See if you can prove that sets of this type are still in your $\sigma$-algebra. Also, see if you can prove that for different elements $x$ and $y$, the sets I described are either disjoint or equal. – Josh Keneda Sep 15 '14 at 1:31
• @JoshKeneda I think this works if $X$ is finite. But there are some trouble in the case $X$ is infinite. Since there could uncountably many sets in the $\sigma$-algebra which contain $x$, then the intersection may not lie in the $\sigma$-algebra. – Kato yu Sep 15 '14 at 1:37
• Sure, it's at first an uncountable intersection. But I claim that, since $X$ is countable, you can express this intersection as a countable intersection of sets in your $\sigma$-algebra. It's just about finding a clever way to rephrase the sets I described. – Josh Keneda Sep 15 '14 at 1:42
• Try to do it without this additional hint, but if you need it, read on. Fix $x\in X$. For $y\in X$, either your $\sigma$-algebra can tell the difference between $x$ and $y$ or it can't. If it can, let $L_{x, y}$ be a set in your $\sigma$-algebra which includes $x$ but not $y$. If it can't, let $L_{x, y} = X$. What is $\cap_{y\in X} L_{x, y}$? – Josh Keneda Sep 15 '14 at 1:47
• @BlueBuck Sure. Good question. Suppose $\cap L'_{x,y}$ is another such set, and let $z\in \cap L'_{x,y}$. Then every set in the $\sigma$-algebra which contains $x$ must also contain $z$. In particular, $z\in L_{x,y}$ for all $y$, so $z \in \cap L_{x, y}$. By symmetry, we get the reverse inclusion, so $\cap L'_{x,y} = \cap L_{x,y}$. The heuristic is that $\cap L_{x,y}$ is just the collection of points that are inseparable from $x$ from the $\sigma$-algebra's perspective. And this description of $\cap L_{x,y}$ makes it a little more clear that it won't depend on the choice of $L_{x,y}$. – Josh Keneda Sep 22 '15 at 5:41

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.
• Sure. Consider the Borel measurable sets on $\mathbb{R}$. Suppose that this $\sigma$-algebra is generated by a partition of $\mathbb{R}$. We note that the singleton sets $\{x\}$ are Borel measurable, which means that $\{x\}$ must belong to the partition for all $x$. Therefore the generating partition is just the partition into singletons, which generates the discrete $\sigma$-algebra. But not all sets are Borel measurable. Contradiction. – Josh Keneda Sep 12 '15 at 1:51
• Ah, sorry. I was taking the atomic algebra (allowing arbitrary unions) generated by the partition instead of the usual $\sigma$-algebra. If you just want to see that the co-countable $\sigma$-algebra and the Borel $\sigma$-algebra are unequal, then note that $[0,1]$ is in the Borel algebra but isn't countable/co-countable. All elements of the co-countable $\sigma$-algebra will of course be Borel measurable, though. – Josh Keneda Sep 16 '15 at 16:14
• In other words, the Borel algebra is strictly finer than the $\sigma$-algebra generated by our partition, so the Borel algebra isn't generated by a partition of $\mathbb{R}$. – Josh Keneda Sep 16 '15 at 16:16