12
$\begingroup$

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?

$\endgroup$
  • 1
    $\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$ – Le Anh Dung Aug 30 '18 at 13:48
13
$\begingroup$

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.

$\endgroup$
  • $\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 '13 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 '13 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 '13 at 5:45
  • $\begingroup$ This answer uses Countable Choice, to get the sequence of $a_n$s and $b_n$s. $\;$ $\endgroup$ – user57159 Sep 22 '13 at 5:51
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yes, countable as in there is a 1-1 mapping, or same cardinal number. is that the same? $\endgroup$ – lightfish Sep 22 '13 at 2:05
  • 1
    $\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$ – Nick Peterson Sep 22 '13 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 '15 at 19:34
2
$\begingroup$

Hint: there is a biyection between $\mathbb R$ and $\{0,1\}^{\mathbb N}$ and you can create an injective function from $\{0,1\}^{\mathbb N}$ to $S$ if at least an infinite amount of the $E_i$ have two or more elements.

$\endgroup$
  • $\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 '13 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$ – k76u4vkweek547v7 Sep 23 '13 at 2:57
1
$\begingroup$

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

$\endgroup$
  • $\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 '13 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$ – Daniel Montealegre Sep 22 '13 at 2:46
  • $\begingroup$ I see now, thank you so much! $\endgroup$ – lightfish Sep 22 '13 at 2:51
0
$\begingroup$

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.


QED

$\endgroup$
  • $\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 '13 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 '13 at 5:49
0
$\begingroup$

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.

$\endgroup$

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.