6
$\begingroup$

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

  • 0
    @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).2012-09-05

3 Answers 3

4

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!

  • 0
    In the answer, the paragraph beginning with "On the other hand", should it read "On the other hand, if $2^\kappa\leq|A|$ then there will be exactly $|A^\kappa|$ many sets in $[A]^\kappa$."?2012-11-02
3

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, then there are $0$ subsets of size $B$.

  • 0
    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.2012-09-04
0

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$

  • 0
    Yes. You can fix this with the axiom of choice.2014-09-14