Uncountability of the Set of all Infinite Binary Sequences - Diagonalization

159 Views Asked by At

One proof of the uncountability of $R$ goes:

Suppose a correspondence $f$ exists between $N$ and $R$ such that:
$f(1)=m_1.x_{11}x_{12}x_{13}x_{14}...$
$f(2)=m_2.x_{21}x_{22}x_{23}x_{24}...$
$f(3)=m_3.x_{31}x_{32}x_{33}x_{34}...$
$\quad \quad . $
$\quad \quad . $
$\quad \quad . $

Construct $x$ such that its $i^{th}$ fractional digit is different than the $i^{th}$ digit of $f(i)$.
Constructed in this $x$ will be different from any $f(i)$
Hence $R$ is uncountable.

The author then states that the proof that the set of all infinite binary sequences is uncountable is similar. Does that mean we just replace the decimal digits with binary digits?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes. In the binary case you construct $x$ such that the $i$-th digit of $x$ is $0$ if the $i$-th digit of $f(i)$ is $1$ and vice-versa.