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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Feb 1, 2017 at 3:47
-
$\begingroup$ Why can we assume that a set of strings of length n is countable? $\endgroup$ Feb 1, 2017 at 4:04
-
1$\begingroup$ @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). $\endgroup$ Feb 1, 2017 at 4:07