3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I'd say its more likely to be $2^{\mathfrak c}$. $\endgroup$
    – tomasz
    Jun 24, 2012 at 16:05
  • $\begingroup$ I am inclined to agree with @tomasz but the 'countable' bit is making it difficult. Interesting question. $\endgroup$
    – nullUser
    Jun 24, 2012 at 16:06
  • $\begingroup$ 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. $\endgroup$ Jun 25, 2012 at 17:00

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Different functions to $\omega$ can give rise to the same partition. $\endgroup$ Jun 24, 2012 at 16:11
  • $\begingroup$ Yes, but there are at most $\mathfrak c$ different functions that give rise to each partition. $\endgroup$ Jun 24, 2012 at 16:13
  • $\begingroup$ Right. I just noticed that. Correcting now. $\endgroup$
    – tomasz
    Jun 24, 2012 at 16:13
  • 1
    $\begingroup$ @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^+$!). $\endgroup$
    – tomasz
    Feb 18, 2014 at 17:49
  • 1
    $\begingroup$ @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$. $\endgroup$
    – tomasz
    Feb 18, 2014 at 17:57
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – nullUser
    Jun 24, 2012 at 16:11
  • $\begingroup$ @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. $\endgroup$ Jun 24, 2012 at 16:31

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.