0
$\begingroup$

How to prove that the countably infinite product of countably infinite sets has cardinality of the continuum?

I know that it is uncountable thus the only thing to prove is the existence of a one-one function from the set $\prod_{n \in \mathbb{N}}{\mathbb{N}}$ to $\mathbb{R}$ .

Thanks

$\endgroup$
  • $\begingroup$ It would be enough to prove that the cardinality of the product is not greater than the cardinality of $\mathbb R$, assuming the continuum hypothesis is true. $\endgroup$ – Peter Dec 1 '15 at 19:02
  • $\begingroup$ @Peter Not, it wouldn't. The continuum hypothesis plays no role here. $\endgroup$ – Andrés E. Caicedo Dec 1 '15 at 19:16
  • 1
    $\begingroup$ A standard approach is to note that you can identify the members of $\prod_n\mathbb N$ with the irrational numbers (in $(0,1)$, say), for instance, via continued fractions. This shows the result, since it is easy to see that $\mathbb R$ has the same size as the set of irrationals. $\endgroup$ – Andrés E. Caicedo Dec 1 '15 at 19:19
  • $\begingroup$ Please explain why the proof that the cardinality of the product is not greater than the cardinality of $\mathbb R$ would not be enough ? $\endgroup$ – Peter Dec 1 '15 at 19:22
  • 1
    $\begingroup$ @Peter I think he is talking about assuming the CH. Your proof would not show the result holds in normal set theory, which is probably what OP needs to show. $\endgroup$ – Trevor Norton Dec 1 '15 at 19:38
0
$\begingroup$

There are two things which need to be proved:

  • $\mathbb{N}^\mathbb{N}$ has size at least that of $\mathbb{R}$. To each real in $(0, 1)$, we can associate an infinite string of zeroes and ones - its binary expansion. This (ignoring the expansions which are eventually all "$1$"s) yields an injection from $(0, 1)$ into $\mathbb{N}^\mathbb{N}$. Note that it is not enough to merely observe that $\mathbb{N}^\mathbb{N}$ is uncountable - it is consistent that there are uncountable sets of size strictly less than that of $\mathbb{R}$.

  • $\mathbb{N}^\mathbb{N}$ injects into $\mathbb{R}$. This is slightly more complicated. If you understand why $\mathbb{N}^\mathbb{N}$ and $2^\mathbb{N}$ have the same cardinality, it's enough to observe that the map defined above had range $2^\mathbb{N}$; if you haven't seen that yet, then here's a straightforward (if somewhat unnatural) injection: given $\alpha=(a_i)_{i\in\mathbb{N}}\in\mathbb{N}^\mathbb{N}$, let $f(\alpha)$ be the real with binary expansion $$0.0...010...010...01...$$ where the $i$th block of zeroes has length $a_i+1$.

$\endgroup$

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.