Infinite Cartesian product of countable sets is uncountable

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?

Solution 1:

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.

Solution 2:

When you say "countable", do you mean "countably infinite"? This result doesn't need to be true otherwise; take, for instance, the case where $E_n=\{0\}$ for all $n$.

Assuming that you did mean "countably infinite": the usual idea here is what's called a diagonalization argument.

Suppose that $S$ is countable, so that all elements of $S$ can be listed as $a_1,a_2,\ldots$. Let $a_n^m$ denote the $m$th element of the tuple representing $a_n$.

Let us construct a sequence which is not in the list. Choose $b_1\in E_1$ such that $a_1^1\neq b_1$. Choose $b_2\in E_2$ such that $a_2^2\neq b_2$. Continue in this way, choosing $b_n\in E_n$ such that $a_n^n\neq b_n$.

The element $(b_n)_{n=1}^{\infty}$ must show up somewhere in the list; however, it cannot be the first element, as they differ in the first coordinate; it cannot be the second, as they differ in the second coordinate; etc.

Solution 3:

Ok first of all if $E_n$ is $\{0,1\}$ then you are trying to prove that infinite $0-1$ strings are uncontable. Assume ab absurdo that you can count them.

Then

$$ N_1=x_{11}x_{12}x_{13}.... $$ $$ N_2=x_{21}x_{22}x_{23}... $$And so on. Define a sequence $y$, by $y=y_1y_2y_3...$ where $y_i=1-x_{ii}$ (so if $x_{ii}$ is $1$ it give you $0$ and if its $0$ it gives you $1$.

Can you prove that $y$ is not equal to any $N_k$?