2

How can I show that the set of all words using the letters a, b, and c are countable?

The hint I was given says to establish a one-to-one correspondence with non-negative integers but I am not following the reason why.

user489819
  • 39

3 Answers3

3

Put $U$ the set of all words using a, b, c; and, for each $k\in \mathbb{N}$, $U_k\subset U$ the set of all words with exactly $k$ letters.

Now, $U=\cup_k U_k$ and each $U_k$ is finite, because $\#U_k=3^k$. Then, $U$ is countable.

If you want a bijection, consider $a\iff 0, b\iff 1, c\iff 2$ and asigns each word with the descomposition in base 3 with coefficients the letters (in order)

Martín Vacas Vignolo
  • 4,710
2

The hint suggests that you look for a bijection because that is the definition of countability. A set is countable if and only if it can be placed in one-to-one correspondence with [a subset of] the natural numbers (i.e. the set of positive integers). There are typically ways of establishing that such correspondences exist without constructing them explicitly, but when you say that a set is countable, you are asserting that such a bijection exists.

If you require an explicit bijection, you might consider the following: every natural number has a base-3 expansion. For example, since $$ 47 = 27 + 18 + 2 = 1\cdot 3^3 + 2\cdot 3^2 + 0\cdot 3^1 + 2\cdot 3^0, $$ we can write $$ 47_{10} = 1202_{3}$$ (where the subscript indicates the base). But then every natural number can be put into bijective correspondence with a word containing the letters $\{a, b, c\}$ by replacing every occurrence of $0$ with $a$, $1$ with $b$, and $2$ with $c$.

Xander Henderson
  • 29,772
  • What you've described isn't quite a bijection. For example, the word abcca maps to $01220_3=1220_3$. Thus, abcca and bcca map to the same natural number, meaning the map isn't one-to-one. – Bob Knighton Dec 05 '17 at 16:40
1

Hint: given a "word," consider constructing a map so that $a$, $b$, and $c$ each represent a different base-10 digit, and interpret the value of the word as the value of the string of digits in base 10. Which assignments of $a$, $b$, and $c$ to single-digit numbers ensures that no two distinct words get mapped to the same number?

Note: This works in base $b$ for $b>3$. This isn't exactly a bijection, but the map is injective, which is enough to prove countability, since the set of words is certainly not finite.

I'll leave you to work out the rest of the details yourself. I hope this helps!

Bob Knighton
  • 434
  • 2
  • 11