Prove that the set of words (from a countable infinite alphabet) is countable Here is the question:
Define a word as a finite string of letters from a countable infinite alphabet $\{ a_{1}, a_{2}, a_{3},...\}$
a) Prove that the set of three letter words is countable.
b) Prove that the set of all finite-letter words is countable.
I'm having a little trouble with part a). My first instinct was to define a function $f: \mathbf{W} \to \mathbf{N}$ (where $\mathbf{W}$ is the set of three letter words) as $f(w) = ijk$ where $w \in \mathbf{W}, w = a_{i}, a_{j}, a_{k}$ for some $i,j,k \in \mathbf{N}$. But this wouldn't be a bijection, since natural numbers can have multiple sets of factors so more than one word would map to the same natural number.
I've seen a similar proof for words in the English language being countable, but the thing that's tripping me up here is the fact that the alphabet is infinite, so I don't think I could use the same method of proof as I would for a finite (English) alphabet. Am I on the right track here? Some guidance would be appreciated.
 A: Let us denote by $W_n$ the set of all $n$-letter words over your alphabet $\Sigma$ and further, let $W = \bigcup_{n \in \mathbb N} W_n$ be the set of all finite words over $\Sigma$.
(a) The idea is actually really close to one standard proof of this fact which goes like this: As $\Sigma$ is countable, there exists some bijection $f \colon \Sigma \to \mathbb N$.
Now consider the map $g \colon W_3 \to \mathbb N$ with $g(\alpha \beta \gamma) = 2^{f(\alpha)} \cdot 3^{f(\beta)} \cdot 5^{f(\gamma)}$ where $\alpha, \beta, \gamma \in \Sigma$.
Note that for any $w \in W$ we know that $g(w) = 2^i \cdot 3^j \cdot 5^k$ and by doing a prime factorization of $g(w)$ we can recover $i, j$ and $k$, allowing us to find $w = f^{-1}(i)f^{-1}(j)f^{-1}(k)$.
Hence $g$ is an injection and hence, $W_3$ must be countable.
(b) As we have infinitely many primes we can reuse the idea from the first part with the simple change of
$$h \colon W \to \mathbb N, g(\sigma_1...\sigma_m) \mapsto \prod_{i \in [1, m]} p_i^{f(\sigma_i)},$$
where $p_i$ denotes the $i$-th prime number.
By essentially the same argument we get that $h$ is an injection, showing that $W$ is countable (in fact, one can show that $h$ is a bijection).
