2
$\begingroup$

We know the Cartesian product of a finite number of $\mathbb{Z}^+$ is countable, for example, $\mathbb{Z}^+ \times \mathbb{Z}^+ \times \mathbb{Z}^+$, because, let $m, n, p$ be from each of the $\mathbb{Z}^+$, we can find a one-to-one function $2^m 3^n 5^p$ that maps them to a subset of $\mathbb{Z}^+$. But what if we increase the number of $\mathbb{Z}^+$ to (countable) infinity, i.e.

$$ \mathbb{Z}^+ \times \mathbb{Z}^+ \times \mathbb{Z}^+ \times \cdots $$ ?

$\endgroup$
  • $\begingroup$ No. This set is uncountable, and has precisely the same size as the set of real numbers. $\endgroup$ – Andrés E. Caicedo Oct 8 '13 at 18:15
  • 1
    $\begingroup$ Even if you replace $\mathbb{Z}^+$ by a set of cardinality $2$, the resulting set will be uncountable. $\endgroup$ – Tobias Kildetoft Oct 8 '13 at 18:15
  • 1
    $\begingroup$ The first hint is to search the site better. $\endgroup$ – Asaf Karagila Oct 8 '13 at 18:15
  • $\begingroup$ @TobiasKildetoft Thanks. I now see this can be shown by the diagonal method. $\endgroup$ – qed Oct 8 '13 at 21:21
2
$\begingroup$

For your infinite product, map $(n_1,n_2,\ldots,)$ to the subset $\{n_1,n_2,\ldots\}$. Then you will get a surjection onto ${\mathbb P}({\mathbb Z}^+)$, which has cardinality greater than the cardinality of ${\mathbb Z}^+$ by Cantor's theorem. Thus your infinite product has cardinality greater than or equal to that of ${\mathbb P}({\mathbb Z}^+)$, and it is in fact equal, which can be shown with a little more work. It is the same cardinality as the set of real numbers, which can also be shown with a little more work. What is true is that the union of countably many countable sets is countable, but not the product.

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