# Is the set of all finite sequences of letters of Latin alphabet countable/uncountable? How to prove either?

Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can define a set $A^{*}=\left \{ \left. a, ksdjf, blocks, coffee, maskdj, \dots, asdlkajsdksjfs \right \} \right.$ (words) as a set that consists of all finite sequences of the elements/letters from our $A$/alphabet. My question is, is this set $A^{*}$ countably or uncountably infinite? Does it matter how many letters there are in your alphabet? If it was, say, $A=\left \{ \left. a \right \} \right.$, then the words in $A^{*}$ would be of form $a, aa, aaa, \dots$ which, I think, would allow a bijection $\mathbb{N} \to A^{*}$ where an integer would signify the number of a's in a word. Can something analogous be done with an alphabet that consists of 26 letters (Latin alphabet), or can countability/uncountability be proved otherwise? And as mentioned before, I am wondering if the number of elements in the alphabet matters, or if all it does is change the formula for a bijection.

P.S. Now that I think of it, maybe we could biject from $\underset{n}{\underbrace{\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\dots\times\mathbb{N}}}$ to some set of words $A^{*}$ whose alphabet $A$ has $n$ elements? Thanks!

• You can enumerate first the one-letter words, then the two-letter words, etc. For each word length, you can order all the words of that length lexicographically and then count through them. Mar 28, 2011 at 22:16

Proposition. If the alphabet $A$ is countable, the set $A^*$ of all finite strings in that alphabet is also countable.
Proof. $A, A^2 = A \times A, A^3 = A \times A \times A$, etc. are all countable and well-ordered (under the lexicographic ordering induced by the well-ordering of $A$), and $$A^* = \bigcup_{n=0}^{\infty} A^n$$ and the union of countably many well-ordered countable sets is again countable, so $A^*$ is countable. Note this does not require the axiom of (countable) choice.
However, the set $A^{\mathbb{N}}$ of all countably-infinite strings is countable if and only if $A$ is empty or is a 1-letter alphabet.