MHB Is the set of infinite binary sequences countable?

[Chris L T521]

Here's this week's problem!

-----

Problem: Show that the set of all infinite sequences with entries from $\{0,1\}$ is not countable.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Chris L T521]

This week's problem was correctly answered by Ackbach, Deveno, and magneto. You can find magneto's solution below.

[sp]Proof by Cantor's diagonal argument. Let us consider a sequence of infinite binary sequence, $(s_i)_{i \in \mathbb{N}}$:
\begin{align*}
s_1 &= d_{11} d_{12} d_{13} \cdots \\
s_2 &= d_{21} d_{22} d_{23} \cdots \\
&\vdots \\
s_i &= d_{i1} d_{i2} d_{i3} \cdots
\end{align*}

$d_{ij}$ is either 0 or 1 and denotes the $j$-th character of the $i$-th sequence.
Define $s := d_1 d_2 d_3 \cdots$ where $d_k := 1 - d_{kk}$. (I.e., if $d_{kk} = 1$,
$d_k = 0$, otherwise $d_k = 1$.) Note that $s$ is different from all the $s_i$'s at the
$i$-th position by design. There does not exist an integer $t$ where $s = s_t$.
So, we cannot establish a 1-to-1 correspondence from
the infinite sequence of binary digits to $\mathbb{N}$ (since we can find some $s$ that is not
part of the original enumeration), hence the set is uncountable.[/sp]