Question

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

Answer 1

You can prove this important result as follows:

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\\eq s_n` for all
`n\geq 1`, then
`s\\otin A`. This contradicts the fact that
`A` is the set of all binary sequences. Then
`A` must be a uncountable set.