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

Solution 1:

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^\kappa|$ 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!

Solution 2:

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