Let say that you have the alphabet $\sum$ and you wanna prove that $\sum^*$ is countably infinite. If it's countable then we can list all the strings in a well defined manner, but I think that somehow we can always come up with a string that is different to all the strings in the set. How would you do this?

up vote 7 down vote accepted

I assume $\Sigma$ itself is countable here; otherwise, of course the statement is false!

First off, let me convince you that it should be true. Consider the following standard enumeration of $\{0, 1\}^*$:

$$\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111, ...$$ It should be clear how this enumeration works. So hopefully this motivates the claim that $\Sigma^*$ is countable.

OK, now on to the proof. Remember that $\Sigma^*$ consists of the set of finite strings with elements from $\Sigma$. This lets us write $\Sigma^*$ as the union of countably many countable sets: letting $\Sigma_n$ be the set of strings from $\Sigma$ of length $n$, we have $$\Sigma^*=\bigcup_{n\in\mathbb{N}} \Sigma_n.$$

So the question is now, "Why is the countable union of countable sets countable?" To answer this, it's enough to show that the set $\mathbb{N}\times\mathbb{N}$ is countable (since this is $\bigcup_{n\in\mathbb{N}}(\mathbb{N}\times\{n\}$)), and this is handled by your favorite pairing function.

  • Why can we assume that a set of strings of length n is countable? – TheMathNoob Feb 1 '17 at 4:04
  • @TheMathNoob Induction on $n$ is one way to do it: $n=1$ is immediate, and for $n=k+1$, the set of length-$n$ strings is a countable union of countable sets: it's the set $$\bigcup_{\sigma\in\Sigma}\{p^\smallfrown\sigma: p\in\Sigma_k\},$$ and both $\Sigma_k$ and $\Sigma$ are countable (the former by the induction hypothesis). – Noah Schweber Feb 1 '17 at 4:07

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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