Sigma-algebras on the Natural Numbers

One direction should be easy: Suppose that $\mathbb N$ is partitioned into nonempty sets $(A_i\mid i\in I)$, so $A_i\cap A_j=\emptyset$ if $i\ne j$ are in $I$, and $\bigcup_{i\in I}A_i=\mathbb N$. Note first that $I$ is countable (possibly finite), since we can inject $I$ into $\mathbb N$ via the function $i\mapsto\min(A_i)$.

Consider now the family of unions of subsets of the partition, that is, the family $$ \mathcal F=\left\{\bigcup_{i\in J}A_i\mid J\subset I\right\}. $$ We easily verify that $\mathcal F$ is a $\sigma$-algebra on $\mathbb N$, in fact, it is the smallest $\sigma$-algebra that contains each $A_i$ as an element.

To see this, note that $\emptyset,\mathbb N\in\mathcal F$, as witnessed by $J=\emptyset, I$, respectively. Also, $\mathcal F$ is closed under complements, since $$\bigcup_{i\in I\setminus J}A_i=\mathbb N\setminus\left(\bigcup_{i\in J}A_i\right). $$ Each $A_i$ is in $\mathcal F$, as witnessed by $J=\{i\}$, and $\mathcal F$ is closed under countable unions, since if $(J_n\mid n\in\mathbb N)$ is a countable family of subsets of $I$, then $$ \bigcup_n\left(\bigcup_{i\in J_n} A_i\right)=\bigcup_{i\in\bigcup_n J_n} A_i. $$ (That the $J_n$ may fail to be disjoint is irrelevant.)

This shows that $\mathcal F$ is a $\sigma$-algebra on $\mathbb N$, and contains each $A_i$ as an element. To see that $\mathcal F$ is indeed the smallest $\sigma$-algebra on $\mathbb N$ containing all the sets $A_i$ as elements, simply notice that any such $\sigma$-algebra must contain $\mathcal F$, since $I$ is countable.

I consider the above the easy direction, because the verification of all details is more or less automatic. The other direction involves more thought. Suppose then that $\mathcal F$ is a $\sigma$-algebra on $\mathbb N$. We need to somehow extract a partition of $\mathbb N$ from $\mathcal F$, in such a way that $\mathcal F$ is just the $\sigma$-algebra obtained by taking unions of the pieces in the partition.

A natural approach consists in trying to identify the atoms of $\mathcal F$. Here, an atom is a nonempty set $A\in\mathcal F$ such that if $\emptyset\ne B\subset A$ and $B\in\mathcal F$, then in fact $B=A$. We want to verify not just that there are atoms at all, but moreover that any $A\in\mathcal F$ contains an atom. Once we have the atoms, we should be done. The point is that any two distinct atoms must in fact be disjoint, since if $A\ne B$ are atoms, then $A\cap B$ is in $\mathcal F$, and a proper subset of at least one of them. Hence, it must be empty, or $A,B$ cannot both be atoms. The key observation is that the union of the atoms is all of $\mathbb N$. Once we know this, then $\mathcal F$ is just the $\sigma$-algebra generated by the atoms, which is just the family obtained by taking unions of collections of atoms, by the argument given in the first part.

There are several ways of verifying the claims we made. An elegant one is as suggested by Thomas Andrews in a comment: Since atoms cannot be further divided, it is natural to consider the relation on $\mathbb N$ where $x\sim y$ iff any set in $\mathcal F$ containing $x$ also contains $y$. It is straightforward to verify that this is an equivalence relation. The claim is that the atoms of $\mathcal F$ are precisely the equivalence classes of this relation. To see this, all that needs proving is that each equivalence class is in $\mathcal F$, since the rest follows from general properties of equivalence relations. For example, if $A\in\mathcal F$ and $x\in A$, then $A$ also contains each member of the equivalence class of $x$, so $A$ is the union of the equivalence classes of its members.

Let $x\in\mathbb N$. For each $y\in \mathbb N$ with $x\not\sim y$, let $A_y$ be a set in $\mathcal F$ containing $x$ but not $y$. Now consider the intersection $B_x$ of all these sets $A_y$. Note that this is a countable intersection, so it is in $\mathcal F$, and that $x\in B_x$. The punchline is that $B_x$ is the equivalence class of $x$. (Otherwise, there is a $z\in B_x$ with $x\not\sim z$, but then $z\notin A_z$ and $B_x\subset A_z$, so certainly $z\notin B_x$.)

Let me close by mentioning that the argument above uses choice, since I picked for each $y\not\sim x$ a set $A_y\in\mathcal F$ witnessing this. I would think this use of choice can be removed, but haven't pursued this.

Finally, to explain the comment by André Nicolas, note that if $(A_i\mid i\in I)$ is a partition of $\mathbb N$ into nonempty pieces, then there is a natural identification of the $\sigma$-algebra generated by the partition with $\mathcal P(I)$: Simply identify $J\subset I$ with $\bigcup_{i\in J}A_i$, and verify that this is a bijection. Moreover, it preserves containments ($J\subseteq K$ iff $\bigcup_{i\in J}A_i\subseteq \bigcup_{i\in K}A_i$), and complements, so the bijection is in fact an isomorphism of $\sigma$-algebras.