# Countability of $E_1 \times E_2 \times …$

True or False: If $E_1, E_2,...$ are finite sets and $$E:= E_1 \times E_2 \times ...\,\, := \left\{(x_1,x_2...): x_j \in E_j\,\,\forall j \in \mathbb{N}\right\}$$ then $E$ is countable.

Attempt: Each $E_j$ is finite so there exists a $1-1$ function taking $\mathbb{N} \rightarrow E_j$. Hence each $E_j$ is at most countable. This means that for any two of the $E_j$, $E_i \times E_j$ is also countable. The Cartesian Product of infinitely many $E_j$ can be counted in a similar way to Cantor's Diagonal Argument. So I conclude that the statement is True. Yet in my answer scheme, it says False.

Can someone clarify my mistake?

Thank you.

• Cantor's diagonal argument shows that infinite products are not countable! – tharris Apr 18 '13 at 11:19
• So I have the right reasoning but made the wrong conclusion simply? – CAF Apr 18 '13 at 11:20
• If $E_i$ is finite then there is no injection from $\Bbb N$ into $E_i$. – Asaf Karagila Apr 18 '13 at 11:31

Let $\{0,1\}=E_1=E_2=\cdots$ Then $E$ is simply the set of all sequences of zeros and ones. Suppose the set were countable and $e_1,e_2,e_3,\ldots$ an enumeration. Then the sequence $(d_n)$ given by $d_n=1-e_n(n)$ differs from each element in the sequence $e_1,e_2,e_3,\ldots$. So $E$ can't be countable. This is simply the Cantor diagonal argument.
• @CAF "The Cartesian Product of infinitely many $E_j$ can be counted in a similar way to Cantor's Diagonal Argument." is simply not true. Try to write out what "similar way" is supposed to mean. Btw: There is a surjection from $\mathbb{N}$ to $E_j$, but no 1-1-function. – Michael Greinecker Apr 18 '13 at 11:30
• Yes, sorry, I reliased that. What I meant to say was they can be counted via the same way as was used to show that the rationals are countable (e.g using arrows in a grid like structure). Doesn't a finite set $E$ imply there exists a function from $\mathbb{N} \rightarrow E$? – CAF Apr 18 '13 at 11:35
• @CAF What you wrote can be done in a similar way cannot be done. If you try to fill in the details, you will see that. There is always a functionf from $\mathbb{N}$ to a finite nonempty set. But a 1-1-function maps different elements to different elements, and this would require the function to take on infinitely many values. – Michael Greinecker Apr 18 '13 at 11:38
• I see. It makes sense. How does it conform with my defintion in my book: Let $E$ be a set. $E$ is said to be finite if and only if either $E = \emptyset$ or there exists a $1-1$ function which takes $\left\{1,2,...n\right\}$ onto $E$, for some $n \in \mathbb{N}$. Is it because here we restict $n$ to some value within $\mathbb{N}$? – CAF Apr 18 '13 at 11:43