Is the set of all finite sequences of the letters x y z countable?

Question

The question is asking if the set of all finite sequences of the letters x y z is countable. For instance elements such as xyzxyy, yzzxxyyyy, xxxyzyx exist in the set.

Would cantors Cantor's diagonal argument work here to prove that the set is uncountable? So far, I have only seen Cantor's diagonal argument used to proof that the set an infinite sequence is uncountable. Such as the infinite sequence of possible binary numbers. Does the fact that the set contains finite sequences of letters mean that it is actually countable? Or is it there to trick us?

Answer 1

I think this set is countable. Let $\{p_i\}_{i\in \mathbb{N}}$ be the sequence of prime numbers. Define a map $f$ from this set to natural numbers. Given a finite sequence $\{a_i\}_{i=0}^{n-1}$ where $a_i\in \{x, y, z\}$,

$$f(\{a_i\}_{i=0}^{n-1})=\prod_{i=0}^{n-1}p_i^{\sigma_i}$$

where $\sigma_i=0,1,2$ respectively when $a_i=x,y,z$.

By unique factorization, $f$ is injective so this set is countable.

Note that $f$ is well defined since we only look at finite sequences. It is exactly the finiteness that makes this construction possible. This method can be generalized to show Robert Shore's comment. If we consider the set of all sequences including the infinite ones, the set is uncountable by diagonal argument.

Answer 2

Food for thought. What's the difference between a finite sequence of three characters, and the natural numbers expressed in a base notation (and thus the set of all finite sequences of $b$ characters.)

The answer is.... nothing.

A key component of Cantor's argument is that the sequences are infinite. If it were a list of finite sequences the proof would fail. Why? Well the key to creating the problem string but changing each character you change an infinite number of characters and so the result is an infinite sequence.

But you list was a list of finite sequences and your goal was to show the set of finite sequences is uncountable. So what if you get an infinite sequence that doesn't belong on your list of finite sequences? That's not a contradiction all. You did not create a finite sequence not on your list.