# How many countable partitions of $\mathbb{N}$ into countable sets?

I am trying to find how many partitions there are of the natural numbers into countably many countable sets. In other words, how many collections of disjoint sets $A_0,A_1,\cdots \subset \mathbb{N}$ such that: $$\mathbb{N}=\bigcup_k A_k$$

My approach to this was to first think of a way of indexing these collections. We can go as follows:

• let $A_0$ be the set containing $0$.

Suppose we have indexed $A_0,\, A_1\cdots A_m$. Consider the next integer $k$ that we have not looked at yet.

• find the set containing $k$: if it one we have already labelled (so $A_i$ for some $i\leq m$), carry on to the next integer $k+1$. If it is not, label this new set which contains $k$ as $A_{m+1}$.

This process is the same as going through the integers and sorting them out into boxes $A_0,\,A_1\cdots$, where we promise to never fill only finitely many boxes will all of $\mathbb{N}$. So we can answer the original question by asking how many ways there are to do this.

This is where I am stuck. Looking at finite subsets does not help, and I am now less convinced this rephrasing makes things simpler.

Is there an easy way to look at this?

• It's at least $2^{\aleph_0}$ because partitioning into contiguous subsets (a subset of all of the partitions) is trivally bijective to a countable sequence of natural numbers. – Q the Platypus Dec 7 '16 at 4:35

$\Bbb N$ has only $2^\omega=\mathfrak{c}$ subsets altogether, so it has $\left(2^\omega\right)^\omega=2^{\omega\cdot\omega}=2^\omega$ sequences of subsets. (All arithmetic here is cardinal arithmetic.) Thus, it has at most $2^\omega$ such partitions. We’re done if we can find $2^\omega$ distinct partitions.

Let $\{A_n:n\in\Bbb N\}$ be a fixed partition of $\Bbb N$ into countably infinite sets. For each $S\subseteq\{2n:n\in\Bbb N\}$ let

$$\mathscr{P}(S)=\left\{\bigcup_{k\in S}A_k\right\}\cup\{A_k:k\in\Bbb N\setminus S\}\;.$$

Verify that $\mathscr{P}(S)$ is a partition of $\Bbb N$ into countably infinitely many countably infinite parts, and that $\mathscr{P}(A)\ne\mathscr{P}(B)$ whenever $A$ and $B$ are distinct subsets of $\{2n:n\in\Bbb N\}$.

• Why $\omega$ here rather then $\aleph_0$? – Q the Platypus Dec 7 '16 at 4:39
• Ah I was trying to find an explicit $\mathfrak{c}$-sized collection but couldn't, thanks :) (btw, small typo below the union) – user111064 Dec 7 '16 at 4:41
• @QthePlatypus: Because $\omega,\omega_1$, etc. are perfectly good cardinal numbers, and I prefer not to muck about with alephs unless there’s a very good reason to do so. (It’s also the usage to which I became accustomed early on, in Ken Kunen’s set theory course, among other places.) – Brian M. Scott Dec 7 '16 at 4:42
• @user111064: You’re welcome, and thanks for catching the typo. – Brian M. Scott Dec 7 '16 at 4:44
• @BrianM.Scott that makes sense. I tend to use alephs when discussing cardinallity and only use omega's when dealing with ordinals but both are equally valid approaches. – Q the Platypus Dec 7 '16 at 4:45