Assume the following result:

If $A$ is an index set with $\#A\leq\#\mathbb R$ and $\{X_{\alpha}\}_{\alpha\in A}$ is a family of sets such that $\#X_{\alpha}\leq\#\mathbb R$ for each $\alpha\in A$, then $\#(\bigcup_{\alpha\in A}X_{\alpha})\leq\#\mathbb R$.

Suppose that $E$ is a set that has the cardinality of the continuum. Is there any way to prove that the set of countable subsets of $E$ has the cardinality of the continuum, using the result above?

  • 1
    $\begingroup$ The standard proof is just to code countable sequences (hence sets, by AC) of reals as individual reals, in the obvious way; I don't see how the result you mention is directly useful, but maybe I'm missing something. $\endgroup$ – Noah Schweber Mar 20 '15 at 2:07
  • $\begingroup$ @user28111 You're right. The following chain of surjections turns out to be more pertinent: $$\#\mathbb R\geq\#\mathbb R^2\geq\#\{0,1\}^{\mathbb N\times\mathbb N}\geq\#[0,1]^{\mathbb N}\geq\#\mathbb R^{\mathbb N}\geq\#\mathbb R.$$ That is, $\#\mathbb R^{\mathbb N}=\#\mathbb R$ and there is an obvious surjection from $\mathbb R^{\mathbb N}$ onto the set of countable subsets of $\mathbb R$. $\endgroup$ – triple_sec Mar 20 '15 at 2:41
  • $\begingroup$ Is there a reason you're specifically interested in using this principle? $\endgroup$ – Noah Schweber Mar 20 '15 at 6:27
  • $\begingroup$ @user28111 The discussion of the textbook I took this claim from seems to suggest using the result on the cardinality of unions. Your suggestion made it clear, however, that exploiting the cardinality of Cartesian products seems more fruitful. Thank you. $\endgroup$ – triple_sec Mar 20 '15 at 14:42
  • $\begingroup$ To be fair, you should keep in mind it's always possible there's a sneaky application I'm missing. $\endgroup$ – Noah Schweber Mar 20 '15 at 16:57

Let $A$ be an element of the set of all the countable subsets of $\mathbb{R}$, which we shall denote simply by $\mathcal{P}_{\le\omega}(\mathbb{R})$

Assertion: $\mathcal{P}_{\le\omega}(\mathbb{R})\preccurlyeq\,^\omega\mathbb{R}$

We will identify $A$ with a $\omega$-sequence of elements of $\mathbb{R}$, that is, an element of $^\omega\mathbb{R}$, in the following way:

  • If $A$ is infinite, let $\{a_n|\;n\in\omega\}$ be an enumeration of $A$. Then it is clear that the assignation $A\longmapsto(a_n)_{n\in\omega}$ is injective.

  • If $A$ is finite, say $A=\{a_0,\dots,a_n\}$, then we define the $\omega$-sequence $(b_k)_{k\in\omega}$ defined by:

$$b_k=\begin{cases} a_k\qquad\qquad\text{if }k\le n \\ a_n+1\qquad\text{ if }k>n \end{cases}$$

And in this case, it is also clear that the correspondence $A\longmapsto(b_k)_{k\in\omega}$ is injective.

In any case, $\mathcal{P}_{\le\omega}(\mathbb{R})\preccurlyeq\,^\omega\mathbb{R}$

Now, on the one hand we have that $\mathbb{R}\preccurlyeq\mathcal{P}_{\le\omega}(\mathbb{R})$, because the function $r\in\mathbb{R}\longmapsto\{r\}\in\mathcal{P}_{\le\omega}(\mathbb{R})$ is obviously injective.

On the other hand, $\mathcal{P}_{\le\omega}(\mathbb{R})\preccurlyeq\mathbb{R}$, since $\;\mathcal{P}_{\le\omega}(\mathbb{R})\preccurlyeq\,^\omega\mathbb{R}\;$ and $\;^\omega\mathbb{R}\preccurlyeq\mathbb{R}$: in fact, $|^\omega\mathbb{R}|=\big(2^{\aleph_0}\big)^{\aleph_0}=2^{\aleph_0\times\aleph_0}=2^{\aleph_0}=|\mathbb{R}|$

From the Cantor-Bernstein theorem, we obtain that $|\mathcal{P}_{\le\omega}(\mathbb{R})|=|\mathbb{R}|=2^{\aleph_0}$

  • $\begingroup$ Let me just add that this uses choice (you fix an enumeration for each infinite $A$). This is essential, as it is consistent that the axiom of choice fails and there are more countable sets of reals than there are reals. $\endgroup$ – Andrés E. Caicedo May 3 at 20:12
  • $\begingroup$ Yes, I'm aware. Anyway, thanks for the comment. $\endgroup$ – Akerbeltz May 3 at 20:50

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.