# Are all finite strings over some infinite alphabet countable?

Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?

• What is a "group" of all finite strings? – fade2black Oct 30 '17 at 18:25
• I think by "group" the OP means "set" – Faheel Ahmad Oct 30 '17 at 18:26
• @ahmed edited with your phrase correction – Joezer Oct 30 '17 at 18:27

Assume the alphabet is countable and strings have finite length. Let's assign to each alphabet symbol a natural number, i.e., each symbol corresponds to a natural number and denote a string by a sequence of numbers. For example, if $a$ corresponds to $2$, $b$ to $5$, and $c$ to $11$ then $aabcb$ would be denoted by $2 \ 2 \ 5 \ 11 \ 5$ (I separate them by a single space to avoid confusion). We will prove that the set of all strings is countable.
We group every string of length $n$ whose individual symbols sum to $k$ into the set $C_{n,k}$. For example $000 \in C_{3,0}$, $1192 \in C_{4,13}$, and $1\ 13 \ 3 \ 1 \in C_{4,18}$. For each pair $\langle n,k \rangle$, $C_{n,k}$ is clearly finite and hence is countable. Furthermore, any string $a_1\dots a_n$ does belong to $C_{n,k}$, where $k=a_1+\dots +a_n$ which means every string is included in some set $C_{n,k}$. Since the set of all possible pairs $\langle n,k \rangle$ is countable the union of all possible $C_{n,k}$, i.e, $\bigcup_{\langle n,k \rangle \in N\times N}{C_{n,k}}$ is also countable.
Another way: If $\Sigma=\{\mathbb{a_0, a_1,a_2,...}\}$ is countable, then to show that $\Sigma^*$ is countable we need only produce an injection $f: \Sigma^*\to\mathbb{N}$. But this is easy; e.g., just let $f([\mathbb{a_{i_1},a_{i_2},...,a_{i_n}}])$ be the number whose hexadecimal (or any base $>10$) representation is $\tt{Ai_1Ai_2...Ai_n}$, where $\tt{i_k}$ is the decimal representation of $i_k$. E.g., $f([\mathbb{a_0,a_{12},a_7}]) = \tt{A0A12A7}_{hex}=168432295_{dec}$.