Let $\sum=\{0,1\}$. I know that $\sum^{*}$ ( the set of all binary strings plus empty string ) is a countable set. Let $B$ be the set of all infinite length binary strings. I know that $B$ is an uncountable set ( in a similar way like set of real numbers is uncountable ). But it seems weird to me. If I am not wrong $B \subset \sum^{*}$ and yet $\sum^{*}$ is countable and $B$ is not. I am misunderstanding something but can't figure out what.

  • $\begingroup$ Why $B$ is uncountable? Simply becoz it contains all infinite length strings? $\endgroup$ – chandresh Oct 14 '15 at 5:44
  • $\begingroup$ $\sum^{*}$ does not contain infinite strings and hence $B \subset \sum^{*}$ is wrong. $\endgroup$ – cr001 Oct 14 '15 at 5:49
  • $\begingroup$ $B$ is not a subset of $\Sigma^\ast$, for all strings in $\Sigma^\ast$ are of finite length. $\endgroup$ – André Nicolas Oct 14 '15 at 5:49
  • $\begingroup$ @cr001 But $\sum^{*}=\{0,1,00,01,10........\}$ the set is infinite so could you explain why it does not contain infinite strings ? $\endgroup$ – sashas Oct 14 '15 at 5:50
  • 1
    $\begingroup$ It's infinite but all it's elements are finite. This is just like Z every integer is finite. But the set is infinite because there are an infinite number of (finite) integers. $\endgroup$ – fleablood Oct 14 '15 at 5:53

"∑∗ ( the set of all binary strings plus empty string )"

This is ambiguous. Do you mean finite strings only or all strings finite and infinite.

If this includes infinite strings then it is not countable.

If this doesn't include infinite strings than B is not a subset.


Ah, Apparently $\sum$ = {0,1} and $\sum *$ is Kleene closure, the set of all finite strings of $\sum$. Kleene closure most certainly is countable. But B the set of infinite binary strings is not a subset of $\sum$*. In fact the two sets are completely disjoint.

(I hadn't come across the notation nor the name "Kleene closure" before. Although the concept of set of finite strings being countable but set of infinite strings being uncountable is very well known under other names and notations. [Usually I see it referred to as cross-products or sets of n-tuples which is equivalent, of course.])


Briefly, No.

"X is uncountable" iff it's not countable iff there's no injection $X \to \mathbb{N}$.

If a set $A$ is countable, there is an injection $f \colon A \to \mathbb{N}$. If $X \subseteq A$ is any subset of $A$, then $ f \restriction X \colon X \to \mathbb{N}$ is an injection too.

As discussed in the comments to your question, $\Sigma^{*}$ is the Kleene closure of $\Sigma$, thus it's all finite strings of symbols from a typically finite alphabet $\Sigma$. In your example, $\Sigma = \{0, 1\}$. So $\Sigma^{*}$ is countable.

Your set $B$ is $\Sigma^{\mathbb{N}}$ ie. $\{0,1\}^{\mathbb{N}}$, countably infinite sequences (/ "strings") of symbols in $\Sigma$. Cantor's diagonal proof shows that $B$ is uncountable.

Far from being a subset of $\Sigma^{*}$, $B$ and $\Sigma^{*}$ don't even have one element in common: they're disjoint.


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.