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$.
cardinality of the set of countable partitions of $\mathbb{R}$
-
0I'd say its more likely to be $2^{\mathfrak c}$. – 2012-06-24
-
0I am inclined to agree with @tomasz but the 'countable' bit is making it difficult. Interesting question. – 2012-06-24
-
0Related 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](http://mathforum.org/kb/message.jspa?messageID=7409356) and [Fred Galvin's](http://mathforum.org/kb/message.jspa?messageID=7409624) follow-up comments. – 2012-06-25
3 Answers
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.
-
0Different functions to $\omega$ can give rise to the same partition. – 2012-06-24
-
0Yes, but there are at most $\mathfrak c$ different functions that give rise to each partition. – 2012-06-24
-
0Right. I just noticed that. Correcting now. – 2012-06-24
-
0Hi, would you add the details, please? I have some doubts about the passage "so there are $2^{2^{\aleph_0}}$ equivalence classes of functions". It seems to me that you are using some kind of results regarding the cardinality of a quotient set. Would you explain it more precisely? Thank you – 2014-02-18
-
0@aerdna91: if you have an equivalence class on a set $X$ such that each class has cardinality bounded below $\lvert X\rvert$, then clearly there must be $\lvert X\rvert$ classes (because their union is $X$!). Does that clear up your doubts? – 2014-02-18
-
0Yeah, intuitively I got it. It was more a "formalism" question...I mean, how can I prove the statement in your comment? Maybe the following is enough: let $\lambda<|X|$ such that every class has cardinality $<\lambda$. Then $|X|\leq|X/\sim|\cdot \lambda \leq |X|\cdot|X|=|X|$. Then every "$\leq$" is an "$=$", so $|X|=|X/\sim|\cdot \lambda=\max(|X/\sim|, \lambda)$ and therefore $|X|=|X/\sim|$. – 2014-02-18
-
1@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^+$!). – 2014-02-18
-
0uhm...but if I change the hypothesis, then I am not allowed to do the very last step, right? EDIT: sorry, obviously wrong observation – 2014-02-18
-
1@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$. – 2014-02-18
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$.
Hint: how many subsets does $\mathbb R$ have? Can't (almost) all of them be part of a partition?
-
0Since $\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? – 2012-06-24
-
0@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. – 2012-06-24