This is really bugging me. On a final exam I had an extra credit question that said to prove that the countable Cartesian Product of countable sets is countable. I know this is true for a finite product and I thought I proved it using induction. But on the way home I thought up a counter example:
Ignoring the decimal point, every real number can be expressed as a string of characters 0-9 with the first number non-zero. Therefore the real numbers can be put in 1-1 correspondence with a subset of
$\mathbb{Z}_{10}-\{0\}\times\mathbb{Z}_{10}\times\mathbb{Z}_{10}\times\mathbb{Z}_{10}\times\mathbb{Z}_{10}\times…$
which is a countable Cartesian product of finite sets. Yet, wouldn't this provide a counterexample since a countable set cannot have an uncountable subset?
Best Answer
No, a Cartesian product of countably infinite, countable sets (with at least two elements in each) is uncountable. Let $S_i|i\in \mathbb{N}$ be the countably many countable sets. Then the Cartesian product of them is just the set of all sequences $(s_1,s_2,s_3,\dots ,s_i,\dots)$ with $s_i \in S_i$ for each $i\in \mathbb{N}$. You can apply Cantor's diagonal argument to see that this set is not countable.