Let $\{E_n\}_{n\in\mathbb{N}}$ be a sequence of countable sets and let $S=E_1\times\cdots\times E_n\times\cdots $. Show $S$ is uncountable. Prove that the same statement holds if each $E_n=\{0,1\}$.
By the definition of Cartesian product of sets,
$$\displaystyle S=\Pi_{n\in\mathbb{N}} \{f\colon\mathbb{N}\rightarrow\cup_{n\in\mathbb{N}}E_n\mid\forall n, f(n)\in E_n\}$$
If $E_n=\{ 0,1\}$, then
$$\displaystyle S_{01}=\Pi_{n\in\mathbb{N}}\{0,1\}=E^{\mathbb{N}}$$, where $E=\{0,1\}$.
By a theorem, $\cup_{n\in\mathbb{N}} E_n$ is countable since the sequence is countable.
I'm not sure how to go on from here to show $S$ is uncountable. Can we say anything about the function $f$ that maps a countable $\mathbb{N}$ to another countable union of sequence of countable sets?
Best Answer
You can reproduce Cantor's diagonal trick for both problems.
Suppose $S$ is countable. Let $(F_n: n\in\mathbb N)$ be an enumeration of $S$. For each $n$,pick two points $a_n,b_n\in E_n$. Then define a new function $F\in S$ as follows: $$F(m)= \begin{cases} b_m &\mbox{if } F_m(m)=a_m \\ a_m & \mbox{otherwise } \end{cases}$$ It follows that $F\in S$ but it is different of all $F_n$'s which is a contradiction.