1
$\begingroup$

Consider $\Sigma = \{a,b\}$. Now $\Sigma^*$ represents the collection of all possible strings over alphabet $\Sigma = \{a,b\}$. As there exists an enumeration procedure for $\Sigma^*$, it is countably infinite. As $\Sigma^*$ consists of strings of all lengths, it also consists of strings of infinite length. Let us consider a subset $S$ of $\Sigma^*$, namely

$$ S = \{\text{Set of all strings of infinite length}\}. $$

From Cantor’s diagonalization argument, it can be proved that $S$ is uncountably infinite. But we also know that every subset of a countably infinite set is finite or countably infinite. This leads to a contradiction.

Where did the above argument go wrong?

Improve this question
$\endgroup$
4
  • 8
    $\begingroup$ $\Sigma^*$ does not contain infinite length strings. It contains all strings with finite length, however. $\endgroup$
    – nir shahar
    Jan 11, 2022 at 11:27
  • 2
    $\begingroup$ Adding to what @nirshahar said. If you are having problem to get the idea. Note $\Sigma^*$ is set of all possible strings of finite length from our alphabet $\Sigma$. $\Sigma^*=\Sigma^0 \cup \Sigma^1 \cup \Sigma^2 ...$ Any possible string which you take from $\Sigma^*$ as per the above definition has a finite length say $n$, but this length might be very very huge, but is finite however. And the strings of infinite length are a different situation after all. They do not have a finite length. $w \in S$ ($S$ defined by you) is a continuous stretch of symbols from $\Sigma$, $\notin \Sigma^n$ $\endgroup$
    – Abhishek Ghosh
    Jan 11, 2022 at 15:19
  • 1
    $\begingroup$ $\Sigma ^*$ is the set of all finite strings over $\Sigma$. By contrast, the set of all strings of infinite length over $\Sigma$ is sometimes referred to as $\Sigma^\omega$ or $\Sigma^{\mathbb{N}}$. As you already know, $\Sigma^*$ is countable, and as you've just discovered, $\Sigma^\omega$ is uncountable. $\endgroup$
    – Stef
    Jan 11, 2022 at 15:44
  • 1
    $\begingroup$ Similar question: Strings of infinite length? $\endgroup$
    – Stef
    Jan 11, 2022 at 15:46

1 Answer 1

Reset to default
2
$\begingroup$

The argument went wrong at the point where you said that $\Sigma^*$ includes strings of infinite length. Specifically your set $S$ is an empty set. $\Sigma^*$ includes just an infinite number of strings of arbitrarily large but finite lengths.

As some commenters pointed out infinite strings are in $\Sigma^\omega$ which is uncountable.

Improve this answer
$\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.