How come the set of all binary strings is uncountable?

Question

Sorry for bumping this very old problem which already has answers on multiple SE sites, but I just cannot understand any of the answers.

Let $\Sigma_{bool} = \{0, 1\}$.

Then, $(\Sigma_{bool})^*$ is the set of all binary strings, as far as I know. I've seen many posts claiming this set is uncountable. But how is that possible? If I sort the elements by length and then lexicographically, I get an ordering. Ordering of a set is, by definition, a bijection to a subset of natural numbers.

I would get:

$\Sigma_{bool}$	$\mathbb{N}$
0	0
1	1
00	2
01	3
10	4
11	5
000	6
001	7
...	...

This post claims that it matters if the strings are of infinite length - why does it matter? I don't see it, can you please explain?

Answer 1

Ok more theoretic proof here

If you are only looking at finite strings

by definition $$\Sigma_{bool}^* = \bigcup_{i \in \mathbb{N}} \Sigma_{bool}^i$$

(where $\Sigma_{bool}^i$ is the set of strings of length $i$)

$\Sigma_{bool}^i$ is finite, therefore countable. So this is a countable union of countable sets, and therefore countable.

If you are looking at infinite strings

Your set is actually the set of sequences on $\Sigma_{bool}$ or equivalently, the set of mappings from $\mathbb{N}$ to $\Sigma_{bool}$.

$$\Sigma_{bool}^{\mathbb{N}}$$

It is bijective to the powerset of $\mathbb{N}$

This is not countbale because of Cantor's theorem

Answer 2

Suppose you have the set of all the infinite binary strings (i.e. $\Sigma^{\omega}$), then whatever enumeration $E = (s_1, s_2, s_3, ... )$ you build for them you can build a string $s'$ that is not in $E$ using a simple diagonalization argument:

$s'[i] = 1 - s_i[i]$, $i \geq 1$

where $s_i[i]$ is the $i$-th digit of $s_i$.

$s'$ (which has infinite length) is different from any (infinite) string in $E$.

If you only consider the set of all finite binary strings, the enumeration you wrote in the question is enough to prove that it is countable.