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.

  • $\begingroup$ Cantor's diagonal argument shows that infinite products are not countable! $\endgroup$ – tharris Apr 18 '13 at 11:19
  • $\begingroup$ So I have the right reasoning but made the wrong conclusion simply? $\endgroup$ – CAF Apr 18 '13 at 11:20
  • 3
    $\begingroup$ If $E_i$ is finite then there is no injection from $\Bbb N$ into $E_i$. $\endgroup$ – 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.

  • $\begingroup$ When I said Cantor's diagonal argument, I meant the 'array' method used to show that the rationals are countable. What is the mistake in my answer? $\endgroup$ – CAF Apr 18 '13 at 11:27
  • $\begingroup$ @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. $\endgroup$ – Michael Greinecker Apr 18 '13 at 11:30
  • $\begingroup$ 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$? $\endgroup$ – CAF Apr 18 '13 at 11:35
  • 2
    $\begingroup$ @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. $\endgroup$ – Michael Greinecker Apr 18 '13 at 11:38
  • $\begingroup$ 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}$? $\endgroup$ – CAF Apr 18 '13 at 11:43

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.