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?

  • 3
    $\begingroup$ I think there should be an assumption that $E_n \neq \emptyset$ for all $n \in \mathbb N$. If not, $S$ could be empty. $\endgroup$
    – Akira
    Aug 30, 2018 at 13:48

6 Answers 6


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.

  • $\begingroup$ so I assume $S$ is countable and find some $F(m)$ and $F_m(m)$ so that $F\in S$ but $F\ne F_n$? $\endgroup$
    – lightfish
    Sep 22, 2013 at 2:17
  • 1
    $\begingroup$ @brenna The point is that $F\ne F_m$ since $F(m)\ne F_m(m)$ $\endgroup$
    – azarel
    Sep 22, 2013 at 2:21
  • $\begingroup$ For the case where $E_n=\{0,1\}$ I can use $F(m)=1$ if $F_m(m)=0$ and $F(m)=0$ if $F_m(m)=1$, but for the general case $E_n$, can I have $F(m)$ pick the digit one step to the right of the index in the Cantor diagonalization? $\endgroup$
    – lightfish
    Sep 22, 2013 at 5:45
  • 1
    $\begingroup$ This answer uses Countable Choice, to get the sequence of $a_n$s and $b_n$s. $\;$ $\endgroup$
    – user57159
    Sep 22, 2013 at 5:51
  • 1
    $\begingroup$ What do you mean $F \in S$? Do you mean $F(m) \in S$? Well that clearly doesn't make sense because $a_m$ and $b_m$ belong to $E_m$ and not the infinite product $S$. Unless there you are using shorthand notation for $(0,\ldots,0,a_m,0,\ldots)$? $\endgroup$
    – user311475
    Jan 18, 2021 at 1:40

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.

  • $\begingroup$ yes, countable as in there is a 1-1 mapping, or same cardinal number. is that the same? $\endgroup$
    – lightfish
    Sep 22, 2013 at 2:05
  • 2
    $\begingroup$ A set is countably infinite if there is a bijection between it and $\mathbb{N}$. Countable means "countably infinite or finite". The case that I'm trying to avoid is the case in which all but finitely many of the sets have cardinality 1; the argument above can be adapted to work as long as infinitely many of the sets $E_n$ contain at least two elements. $\endgroup$ Sep 22, 2013 at 2:27
  • $\begingroup$ I found this link: mathcentral.uregina.ca/QQ/database/QQ.02.06/geetha1.html, that provides essentially the same proof as the answers here. But it seems to me the "diagonalization" on that page is flawed, specifically the line "tk = xk,k". Would you mind confirming that page indeed has this mistake? $\endgroup$
    – FreshAir
    May 17, 2015 at 19:34

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.


$$ 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$?

  • $\begingroup$ So if sequence $y$ is defined by $y_i=1-x_{ii}$, then $y$ will not be found in the sequence $N_1,N_2,\ldots$ and by the Cantor diagonalization argument, $y$ is not equal to any $N_k$? So by contradiction, infinite $0-1$ strings are uncountable. Can I use the fact that $\{0,1\}$ is a subset of any sequence of countable sets $\{E_n\}_{n\in\mathbb{N}}$ and say the infinite product of this is uncountable too? $\endgroup$
    – lightfish
    Sep 22, 2013 at 2:37
  • $\begingroup$ Yes you are right. If you assume that every set has cardinality bigger than $2$, then you can show that the above will be a subset, and since the above is uncountable, you would be done. $\endgroup$ Sep 22, 2013 at 2:46
  • $\begingroup$ I see now, thank you so much! $\endgroup$
    – lightfish
    Sep 22, 2013 at 2:51

Hint: there is a bijectiоn between $\mathbb R$ and $\{0,1\}^{\mathbb N}$ and you can create an injective function from $\{0,1\}^{\mathbb N}$$S$ if at least an infinite amоunt of the $E_i$ have twо or mоre elements.

  • $\begingroup$ How can I create an injective function from $\{0,1\}^\mathbb{N}$ to $S$? I'm not sure what $\{0,1\}^{\mathbb{N}}$ is. $\endgroup$
    – lightfish
    Sep 22, 2013 at 5:30
  • $\begingroup$ $\{0,1\}^\mathbb N = \Pi_{n \in \mathbb N} \{0,1\}$ (or the functions from $\mathbb N$ to $\{0,1\}$), supose $E_n=(a_{n,1},a_{n,2},a_{n,3},....)$, if $(x_n) \in \{0,1\}^\mathbb N $ you define $f:\{0,1\}^{\mathbb N} \to S$ by $ f(x_n)=(a_{n,i})$ where $i=1 \text{ if } x_n=0,\quad i=2 \text{ if } x_n=1$ $\endgroup$ Sep 23, 2013 at 2:57

One can show, without using any part of the axiom of choice,
that the product is not countably infinite.

By definition, $\;\; \omega \: = \: \big\{\hspace{-0.02 in}0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.05 in}\big\} \;\;\;$.

Let $\:\langle \hspace{.02 in}E_{\hspace{.03 in}0}\hspace{.02 in},\hspace{-0.01 in}E_{\hspace{.02 in}1},E_{\hspace{.03 in}2}\hspace{.02 in},E_{\hspace{.03 in}3}\hspace{.02 in},...\hspace{-0.02 in}\rangle\:$ be a sequence of sets, infinitely many of which have more than

one element. $\;\;\;\;\;\;$ Let $\;\; S \: = \: \displaystyle\prod_{n=0}^{\infty} E_{\hspace{.02 in}n} \;\;\;$. $\;\;\;\;\;\;$ If $\;\; S \: = \: \{\} \;\;$, $\;\;$ then $S$ is not countably infinite.

Now suppose $\;\; S \: \neq \: \{\} \;\;$, $\;\;$ and let $\: \hspace{.05 in}f : \omega \to S \:$ be an arbitrary function.
Let $\;\; D \: = \: \{n\in \omega : (\exists m)((\hspace{.045 in}f(m))(n) \neq (\hspace{.045 in}f(0))(n))\} \;\;\;$.

If $D$ is finite, then
Let $i$ be the least element of $\:\omega\hspace{-0.04 in}-\hspace{-0.04 in}D\:$ such that $E_{\hspace{.02 in}i}$ has more than
one element, and let $x$ be an element of $E_{\hspace{.02 in}i}$ other than $(\hspace{.045 in}f(0))(i\hspace{.02 in})$.
Let $s$ be the element of $S$ given by if $\:n=i\:$ then $\:s(n) = x\:$ else $\:\: s(n) = (\hspace{.045 in}f(0))(i\hspace{.02 in}) \;\;$.
For all elements $n$ of $\omega$, $\:(\hspace{.045 in}f(n))(i\hspace{.02 in}) = (\hspace{.045 in}f(0))(i\hspace{.02 in}) \neq x = s(i)\;$.
For all elements $n$ of $\omega$, $\:\hspace{.045 in}f(n) \neq s \;$. $\;\;\;$ $s$ is not an element of $\operatorname{Range}(\hspace{.045 in}f\hspace{.025 in})$. $\;$ $\hspace{.045 in}f$ is not surjective.

If $D$ is infinite, then
Let $\: h : \omega \to D \:$ be the natural bijection.
Let $\: g : D\to \omega \:$ be given by $\:\:g(n)$ is the least element $m$ of $\omega$ such that $\:(\hspace{.045 in}f(m))(n) \neq (\hspace{.045 in}f(0))(n)\;\;$.
Let $s$ be the element of $S$ given by
if $\:$ [$n\in D\:$ and $\:(\hspace{.045 in}f(h^{-1}(n)))(n) = (\hspace{.045 in}f(0))(n)$] $\:$ then $\: s(n) = (\hspace{.045 in}f(g(n)))(n) \:$ else $\: s(n) = (\hspace{.045 in}f(0))(n)\;$.
For all elements $n$ of $\omega$, $\:\:$ if $\: (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) = (\hspace{.045 in}f(0))(h(n)) \:$ then
$(\hspace{.045 in}f(n))(h(n)) = (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) = (\hspace{.045 in}f(0))(h(n)) \neq (\hspace{.045 in}f(g(h(n))))(h(n)) = s(h(n)) \;$.
For all elements $n$ of $\omega$, $\:\:$ if $\: (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) \neq (\hspace{.045 in}f(0))(h(n)) \:$ then
$(\hspace{.045 in}f(n))(h(n)) = (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) \neq (\hspace{.045 in}f(0))(h(n)) = s(h(n)) \;$.
For all elements $n$ of $\omega$, $\: (\hspace{.045 in}f(n))(h(n)) \neq s(h(n)) \;$. $\;\;\;$ For all elements $n$ of $\omega$, $\: \hspace{.05 in}f(n) \neq s \;$.
$s$ is not an element of $\operatorname{Range}(\hspace{.045 in}f\hspace{.025 in})$. $\;$ $\hspace{.045 in}f$ is not surjective.

If $D$ is finite then $\hspace{.045 in}f$ is not surjective. $\:$ If $D$ is infinite then $\hspace{.045 in}f$ is not surjective. $\:$ $\hspace{.045 in}f$ is not surjective.
That was supposing $\: S\neq \{\} \:$, $\:$ so we have $\;\;$ "If $\: S\neq \{\} \:$ then $S$ is not countably infinite" $\;\;$.
Therefore $S$ is not countably infinite.


  • $\begingroup$ Could you explain what $D$ is and how you thought of it? And is $(f(m))(n)$ notation for $f_m(n)$? Thank you $\endgroup$
    – lightfish
    Sep 22, 2013 at 5:42
  • $\begingroup$ $D$ is the set of indices on which the elements (of $S$) that are in $\operatorname{Range}(\hspace{.045 in}f\hspace{.025 in})$ take Different values. $\hspace{.77 in}$ Yes, and writing it that way would have required huge subscripts. $\;\;\;$ $\endgroup$
    – user57159
    Sep 22, 2013 at 5:49

If the sets $A_i$ are all countably infinite, then the product $A$ is also countably infinite. The argument is like this: if the product $A$ is countably infinite, then you can enumerate all of the elements of $A$ as a countable sequence like this one:

$$x_1=\langle a_1, b_1,c_1,d_1,\ldots\rangle\\ x_2=\langle a_2, b_1,c_1,d_1,\ldots\rangle\\ x_3=\langle a_1,b_2,c_1,d_1,\ldots\rangle\\ x_4=\langle a_2,b_2,c_1,d_1,\ldots\rangle\\\vdots$$

(The exact order doesn't matter; all that matters is that all the elements in $A$ appear in this sequence, by asumption.)

You can use a diagonal argument to define a member of $A$ that doesn't appear in this list. Because the list is supposed to contain all of the elements of $A$, this will be a contradiction; therefore $A$ is uncountable.

Define the member $y=\langle a,b,c,d,\ldots\rangle \in A$ as follows. For the first item in $y$, pick some element of $A_1$ that's different from the first item in $x_1$. This ensures that $y\neq x_1$. For the second item in $y$, pick some element of $A_2$ that's different from the second item in $x_2$. This ensures that $y\neq x_2$. And so on.

The resulting member $y$ is a member of the product $A=A_1\times\ldots$ because we chose its first item from $A_1$, its second item from $A_2$, and so on. However, $y$ is different from every element in the countable list of $x_i$. (Each $x_i$ has a different $i$th item .) Therefore $y$ is a member of $A$ that was missed by the countable enumeration. Therefore $A$ is uncountable.

You can extend this argument to the case where most, but not all, of the $A_i$ are infinite. $A$ will be uncountable whenever infinitely many $A_i$ are infinite. Otherwise, $A$ will be countably infinite.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .