# Is $\Sigma^*$ countable or uncountable?

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?

• $\Sigma^*$ does not contain infinite length strings. It contains all strings with finite length, however. Jan 11, 2022 at 11:27
• 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$ Jan 11, 2022 at 15:19
• $\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.
– Stef
Jan 11, 2022 at 15:44
• Similar question: Strings of infinite length?
– Stef
Jan 11, 2022 at 15:46

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.