0
$\begingroup$

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?

$\endgroup$
7
  • 5
    $\begingroup$ The set of finite binary strings is countable. The set of infinite binary strings is uncountable. That's just the way it is. Finite and infinite behave differently. $\endgroup$ Jun 13 at 17:36
  • $\begingroup$ @YuvalFilmus Which one of these is $(\Sigma_{bool})^*$ if defined as above? $\endgroup$ Jun 13 at 17:37
  • $\begingroup$ $\Sigma^*$ is the set of finite words over $\Sigma$. In contrast, $\Sigma^\omega$ is the set of infinite words over $\Sigma$. $\endgroup$ Jun 13 at 17:40
  • 4
    $\begingroup$ Right, $\Sigma^*$ consists only of finite words. $\endgroup$ Jun 13 at 17:44
  • 2
    $\begingroup$ The set of all infinite binary strings is uncountable. That's just the way it is. $\endgroup$ Jun 13 at 17:54
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.