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

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?

• The union of a countable number of countable (or finite) sets is countable (think of $\mathbb{N}^2$). Each $\{x,y,z\}^n$ is finite. Nov 28, 2022 at 3:59
• Even more is true. The set of finite sequences drawn from a countably infinite alphabet (such as $\Bbb N ^{\lt \omega}$) is countable. Nov 28, 2022 at 4:04
• Not to mention. Every natural number can be expressed as a fine string of $10$ characters and that's countable. And every natural number can be express in trinary and that is a finite string of $3$ characters. Nov 28, 2022 at 4:35

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.

• I think I may have phrased the question poorly. The finite part is referring to each element in the set so there cant be an element that has an infinite letters of x y and z. Using cantors theorem, I would be able to construct a new sequence of letters x y and z that is not in the Set. I do so by changing the kth letter in the new sequence to be different to f(k) for all k, where f is the bijection between the natural numbers and the Set Hence making it an uncountable set. Does this work or did I make a mistake somewhere Nov 28, 2022 at 4:22
• @testcase0_ Your construction will get an infinite sequence since you choose the kth letter for all k. Nov 28, 2022 at 4:29
• @testcase0_ It's a bit late for me so I am going to sleep. If you have other questions, I will look at them tomorrow. Nov 28, 2022 at 4:36
• @testcase0_ If you are not clear about why I say the constructed sequence must be infinite, fleablood has a very good answer for that. Nov 28, 2022 at 23:26

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.)