Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?

  • $\begingroup$ What is a "group" of all finite strings? $\endgroup$ – fade2black Oct 30 '17 at 18:25
  • $\begingroup$ I think by "group" the OP means "set" $\endgroup$ – Faheel Ahmad Oct 30 '17 at 18:26
  • $\begingroup$ @ahmed edited with your phrase correction $\endgroup$ – Joezer Oct 30 '17 at 18:27

If the alphabet is uncountable then the set of all possible finite strings is uncountable. If you allow infinite length strings then by the diagonalization argument the set is also uncountable.

Assume the alphabet is countable and strings have finite length. Let's assign to each alphabet symbol a natural number, i.e., each symbol corresponds to a natural number and denote a string by a sequence of numbers. For example, if $a$ corresponds to $2$, $b$ to $5$, and $c$ to $11$ then $aabcb$ would be denoted by $2 \ 2 \ 5 \ 11 \ 5$ (I separate them by a single space to avoid confusion). We will prove that the set of all strings is countable.

We group every string of length $n$ whose individual symbols sum to $k$ into the set $C_{n,k}$. For example $000 \in C_{3,0}$, $1192 \in C_{4,13}$, and $1\ 13 \ 3 \ 1 \in C_{4,18}$. For each pair $\langle n,k \rangle$, $C_{n,k}$ is clearly finite and hence is countable. Furthermore, any string $a_1\dots a_n$ does belong to $C_{n,k}$, where $k=a_1+\dots +a_n$ which means every string is included in some set $C_{n,k}$. Since the set of all possible pairs $\langle n,k \rangle$ is countable the union of all possible $C_{n,k}$, i.e, $\bigcup_{\langle n,k \rangle \in N\times N}{C_{n,k}}$ is also countable.

  • $\begingroup$ About the last step of the union - is it a rule that a union of any infinite set of countable sets is countable too? $\endgroup$ – Joezer Nov 1 '17 at 6:23
  • $\begingroup$ @Joezer in fact it is union of countably infinite number of countable sets. Yes this is a fact. You can find a proof in a textbook on set theory or somewhere on the Web. $\endgroup$ – fade2black Nov 1 '17 at 7:56
  • $\begingroup$ @Joezer If we take union of uncountably many sets or at least one set in this union is uncountale then the resulting set is also uncountable. $\endgroup$ – fade2black Nov 1 '17 at 12:18

Another way: If $\Sigma=\{\mathbb{a_0, a_1,a_2,...}\}$ is countable, then to show that $\Sigma^*$ is countable we need only produce an injection $f: \Sigma^*\to\mathbb{N}$. But this is easy; e.g., just let $f([\mathbb{a_{i_1},a_{i_2},...,a_{i_n}}])$ be the number whose hexadecimal (or any base $>10$) representation is $\tt{Ai_1Ai_2...Ai_n}$, where $\tt{i_k}$ is the decimal representation of $i_k$. E.g., $f([\mathbb{a_0,a_{12},a_7}]) = \tt{A0A12A7}_{hex}=168432295_{dec}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.