0

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?

Ѕᴀᴀᴅ
  • 34,263
testcase0_
  • 51
  • 3
    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. – copper.hat Nov 28 '22 at 03:59
  • Even more is true. The set of finite sequences drawn from a countably infinite alphabet (such as $\Bbb N ^{\lt \omega}$) is countable. – Robert Shore Nov 28 '22 at 04: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. – fleablood Nov 28 '22 at 04:35

2 Answers2

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.

Ja_1941
  • 536
  • 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 – testcase0_ Nov 28 '22 at 04:22
  • @testcase0_ Your construction will get an infinite sequence since you choose the kth letter for all k. – Ja_1941 Nov 28 '22 at 04: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. – Ja_1941 Nov 28 '22 at 04: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. – Ja_1941 Nov 28 '22 at 23:26
0

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.

fleablood
  • 124,253