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?

  • $\begingroup$ 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. $\endgroup$ – 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\}$.

  • $\begingroup$ Why $ \omega$ here rather then $\aleph_0$? $\endgroup$ – Q the Platypus Dec 7 '16 at 4:39
  • $\begingroup$ Ah I was trying to find an explicit $\mathfrak{c}$-sized collection but couldn't, thanks :) (btw, small typo below the union) $\endgroup$ – user111064 Dec 7 '16 at 4:41
  • 1
    $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Dec 7 '16 at 4:42
  • $\begingroup$ @user111064: You’re welcome, and thanks for catching the typo. $\endgroup$ – Brian M. Scott Dec 7 '16 at 4:44
  • $\begingroup$ @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. $\endgroup$ – Q the Platypus Dec 7 '16 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.