Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the cardinality of the set $$A=\{ P| P\ \text{is a countable partition of the reals} \}$$ ? I am searching on this for a while. I think the cardinality is $2^w$ where $w$ is the cardinality of $\mathbb{N}$. Clearly $|A|\geq |\mathbb{R}|=2^w$, but I cannot prove the other direction. I tried (but did not succeed)to construct an injection $A \rightarrow C$ for some set $C$ with cardinality equal to $2^w$.

share|cite|improve this question
I'd say its more likely to be $2^{\mathfrak c}$. – tomasz Jun 24 '12 at 16:05
I am inclined to agree with @tomasz but the 'countable' bit is making it difficult. Interesting question. – nullUser Jun 24 '12 at 16:06
Related is the 17-18 March 2011 sci.math thread The cardinality of the collection of all partitions of the natural numbers equals that of the real numbers. See my response and Fred Galvin's follow-up comments. – Dave L. Renfro Jun 25 '12 at 17:00
up vote 4 down vote accepted

I think it's not very hard. A countable partition of reals can be seen as just a function from the reals into natural numbers, up to a permutation of the naturals. So we have $$\lvert \mathbf N^{\mathbf R}\rvert=\aleph_0^{2^{\aleph_0}}=2^{2^{\aleph_0}}$$ (because $\aleph_0\leq 2^{\aleph_0}$ we can do the last substitution)

On the other hand, there are only $\aleph_0^{\aleph_0}=\mathfrak c<2^{\mathfrak c}$ permutations of natural numbers, so there are $2^{2^{\aleph_0}}$ equivalence classes of functions from reals to naturals under the relation of equivalence up to a permutation of naturals (because each has at most $\mathfrak c$ elements), which are precisely correspondent to the countable partitions of reals.

share|cite|improve this answer
Different functions to $\omega$ can give rise to the same partition. – Michael Greinecker Jun 24 '12 at 16:11
Yes, but there are at most $\mathfrak c$ different functions that give rise to each partition. – Henning Makholm Jun 24 '12 at 16:13
Right. I just noticed that. Correcting now. – tomasz Jun 24 '12 at 16:13
@aerdna91: Yes, that's correct, except it's enough that every class has cardinality $\leq\lambda$ (otherwise this argument would not work in case $2^{\mathfrak c}=\mathfrak c^+$!). – tomasz Feb 18 '14 at 17:49
@aerdna91: you are. You only used that the classes are smaller than or equal to lambda in the very first step: that $\lvert X\rvert\leq\lvert X/\sim\rvert\cdot \lambda$. In the final step you use that $\lambda<\lvert X\rvert$. – tomasz Feb 18 '14 at 17:57

What is a countable partition? It means that we have some function from $\mathbb R$ into $\mathbb N$ and every part in the partition is the fiber of such function. However counting like this we count many partitions several times, for example take a partition into two parts, then we can see it as a function whose range is $\{0,1\}$ or $\{2,3\}$ or any other pair of numbers.

However note that there are exactly $2^{\aleph_0}$ many ways to re-order the natural numbers therefore at most continuum many functions generate the same partition.

So we have $\aleph_0^{2^{\aleph_0}}=2^{2^{\aleph_0}}$ many functions and each is equivalent to at most $2^{\aleph_0}$ many of them. Therefore there are $2^{2^{\aleph_0}}$ many partitions.

Why can't there be another number? Well, we denote by $\frak p$ the cardinality of all countable partitions, then we have that $2^{2^{\aleph_0}}=2^{\aleph_0}\cdot\frak p$, by the general argument appearing in Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice? we have that $2^{2^{\aleph_0}}=\frak p$.

share|cite|improve this answer

Hint: how many subsets does $\mathbb R$ have? Can't (almost) all of them be part of a partition?

share|cite|improve this answer
Since $\mathbb{R}$ is separable, for every closed subset $C$ it is possible to construct a sequence whose set of limit points is exactly $C$. How many closed subsets of $\mathbb{R}$ are there? Is this enough? – nullUser Jun 24 '12 at 16:11
@nullUser: are you saying the elements of the partition need to be open sets or something like that? I was just taking $\mathbb R$ to be a collection of size $\mathfrak c$ and partitioning it arbitrarily. – Ross Millikan Jun 24 '12 at 16:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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