# Number of countable subsets of $\mathbb{R}$

More generally, if a set $S$ has cardinality $\mathfrak{m}$, how many of its subsets have cardinality $\mathfrak{n}$? Clearly there are at least $2^\mathfrak{n}$ such subsets. I don't see how many more though.

Thanks

-
@Cameron: Very bad choice of letters actually. Fraktur lowercase denote invariants of the continuum. Amongst the are $\frak a,b,c,d$ and many more. –  Asaf Karagila Sep 5 '12 at 0:49
Asaf: I've commonly found those used for cardinals that may or may not be well-orderable. Have you got alternate suggestions? –  Cameron Buie Sep 5 '12 at 2:05
$\mathfrak m,\mathfrak n,\dots$ –  Andres Caicedo Sep 5 '12 at 5:12
@Camron: What Andres said. I do generally agree that using $\frak a,b$ is fine; but when $\mathbb R$ is also mentioned then it's overloading the symbols. Especially since $\frak b,c,d$ are probably the most famous invariants (bounding number; cardinal number; dominating number). –  Asaf Karagila Sep 5 '12 at 7:21

Let's assume the axiom of choice, because it's simpler and easier and commonly done. I'll say a few words on the case without choice later.

First we use a notation: $[A]^\kappa$ is the collection of subsets of $A$ of cardinality $\kappa$. If we want to include smaller sets as well $[A]^{\leq\kappa}$. We write $A^\kappa$ for all the functions from $\kappa$ into $A$, and again with the $A^{\leq\kappa}$.

So you asked what is the cardinality of $[\mathbb R]^\omega$, for this we see that every countable set can be seen as the range of a function from $\omega$ into $\mathbb R$. Choose for every countable set an enumeration, now we have an injection from $[\mathbb R]^\omega$ into $\mathbb R^\omega$. Therefore $|[\mathbb R]^\omega|\leq|\mathbb R^\omega|$. Trivially we also have $|\mathbb R|\leq|[\mathbb R]^\omega|$. We calculuate: $$2^{\aleph_0}\leq |[\mathbb R]^\omega|\leq(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0},$$ and therefore equality ensues and there are $2^{\aleph_0}$ countable subsets of $\mathbb R$.

In the general case, $[A]^\kappa$ is empty when $|A|<\kappa$. Assuming $\kappa\leq|A|$, if $|A|<2^\kappa$ then there are $2^\kappa$ many sets, this is not too hard to prove.

On the other hand, if $2^\kappa\leq|A|$ then there will be exactly $|A|$ many sets in $[A]^\kappa$. To see this note that there are $2^\kappa$ ways to enumerate every set in $[A]^\kappa$, so we have that $|A^\kappa|=2^\kappa\cdot|[A]^\kappa|=|[A]^\kappa|$.

The exact result of $|A^\kappa|$ depends a lot on the model chosen, if we assume GCH (or some other nicely behaved continuum function) then we can calculate it pretty well, and in some cases we can calculate the value in terms of $A,2^A,\kappa$ relatively well.

However consider the following case:

$|A|=\aleph_\omega$, $\kappa=\omega$ and $2^\kappa=\aleph_4$. Koenig's theorem tells us that $|A|<|A^\omega|$, and in fact one of Shelah's most celebrated results in his PCF theory is that: $$(\aleph_\omega)^\omega<\aleph_{\omega_4}\cdot2^{\aleph_0},$$ or in our case, where $2^{\aleph_0}<\aleph_\omega$, then simply have $|A^\omega|<\aleph_{\omega_4}$.

There is work being done to try and improve this bound to be $\aleph_{\omega_3}$, which is quite an improvement but this is still quite open, and as Andres points in his comment below, it is consistent (relative to the existence of a very large cardinal) that $|A^\omega|=\aleph_{\alpha+1}$ for any countable $\alpha$.

A word on the horrors without choice:

There are models of ZF in which the axiom of choice is false, and we cannot choose an enumeration for every countable subset of $\mathbb R$. In such models something quite peculiar happens:

1. There exists an injective function from $\mathbb R$ into $[\mathbb R]^\omega$.
2. There exists a surjective function from $\mathbb R$ onto $[\mathbb R]^\omega$.
3. There does not exist a bijection between $\mathbb R$ and $[\mathbb R]^\omega$ (i.e. the sets have a strictly distinct cardinality).

Not to mention all sort of strange sets which have strange properties. For example, if $A$ is an infinite set which cannot be written as a disjoint union of two infinite sets (such set is called amorphous) then we have a very interesting property:

The set $[A]^\omega$ is actually empty (as $A$ cannot have a countably infinite subset), let us consider $[A]^{<\omega}$ instead. It is in fact exactly half of $\mathcal P(A)$. When I say exactly, I mean that. If you add or remove even a single element you will properly change the cardinality. We have the following: $$|[A]^{<\omega}|+|[A]^{<\omega}|=2^{|A|}.$$

Yes, such wonderful horrors are consistent with ZF when the axiom of choice is absent!

-
From supercompacts, Shelah has shown for any countable $\alpha$ that $\aleph_{\alpha+1}$ can be the size of $A^\omega$. We do not know if it is possible to lift this to $\aleph_{\omega_1}$ or beyond. –  Andres Caicedo Sep 4 '12 at 18:26
@Andres: Thanks! –  Asaf Karagila Sep 4 '12 at 18:33
I'm fascinated by the bit in the last paragraph: "It is in fact exactly half...change the cardinality." Could you provide a reference for that, please? I'd like to look into it in further detail. –  Cameron Buie Sep 5 '12 at 0:37
@Cameron: I could probably give you an exact location tomorrow morning, but in the meantime: if $A$ is amorphous then it's power set is D-finite (easy). Now note that the finite subsets and co-finite subsets are in bijection (complement). There you have it! –  Asaf Karagila Sep 5 '12 at 0:47
@Cameron: I couldn't find anything substantial in Jech's book nor in Herrlich's book. I'd think that my previous comment should suffice... let me know if you need more. –  Asaf Karagila Sep 5 '12 at 7:59

Each real number can be written down (not necessarily uniquely) as a countable sequence of digits and decimal points.

Thus, you can write down a countable set of real numbers simply by interlacing the digits of its members according to some fixed rule.

Therefore there must be exactly continuum many countable subsets of $\mathbb R$.

In the general case, as long as $\aleph_0\le B\le A\le2^B$, an analogous argument shows that there are $2^B$ subsets of $S$ with cardinality $B$. (This depends on the Axiom of Choice).

If $A>2^B$, then there are of course at least $A$ subsets. My intuition is that there will be no more, but I have no proof of that ready.

If $A<B$, then there are $0$ subsets of size $B$.

-
How about the general case? Is it $2^B$ or $A$? –  Karolis Juodelė Sep 4 '12 at 16:18
Edited. ${}{}{}$ –  Henning Makholm Sep 4 '12 at 16:24
About all you can say in general when $A>2^B$ is that $A\le A^B\le 2^A$, and if $B\ge\operatorname{cf}A$, then $A^B>A$. –  Brian M. Scott Sep 4 '12 at 17:29

How about this map, send each countable set $A$ to $f_A$ where $f_A:\mathbb{N} \to A$ a bijection. This is injection because, let $f_A=f_B$ then $im(f_A)= im(f_B)=A=B$. So we get injection from set of all countable sets to set of all bijections $\mathbb{N} \to \mathbb {R}$, which is subset of set of all functions $f:\mathbb{N} \to \mathbb {R} \cong \mathbb{R}$. Now also exist injection from $\mathbb{R} \cong P(\mathbb{N})$ to set of all countable subsets. So we get cardinality exactly $c$

-
So... you're going to go through all these questions, and posts answers? –  Asaf Karagila Sep 14 '14 at 19:51
Is my answer wrong ? at least for this question ? –  dragoboy Sep 14 '14 at 19:54
It's incomplete. Just for $\Bbb N$ there are many $f_\Bbb N$'s. Which one do you choose? –  Asaf Karagila Sep 14 '14 at 19:56
for every $A$ take any fixed $f_{A}$ , isn't it ? –  dragoboy Sep 14 '14 at 19:59
But how do you fix it? –  Asaf Karagila Sep 14 '14 at 20:01