Question

Show by using "proof by contradiction" that the set of binary sequences {0,1}N is uncountable.

Answer 1

Answer:

You can prove this important result as follows:

Step-by-step explanation:

Let $A$ be the set of all binary sequences, that is to say, $\{0,1\}^{\mathbb{N}}$. Suppose that $A$ is a countable set. Then the elements of  $A$ can be ordered as a sequence $\{s_{1},s_{2}, s_{3},...\}$, where each $s_{i}$ is a binary sequence. The $k\text{-th}$ digit of each sequence is expressed by $s_{n}(k)$. Define the sequence $s$ as follows:

$s(k)=\begin{cases}1&\text{if}\,s_{k}(k)=0\\ 0 &\text{if}\,s_{k}(k)=1\end{cases}$

Note that $s$ differ from each $s_{k}$ in at least one digit. Then $s\neq s_n$ for all $n\geq 1$, then $s\notin A$. This contradicts the fact that $A$ is the set of all binary sequences. Then $A$ must be a uncountable set.