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?
Countably Infinite – Proving Set of All Strings of an Alphabet
automatafinite-automata
Best Answer
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.