TITLE: How to show that set of strings of odd length in $\{a,b,c\}^*$ is countable?
QUESTION [1 upvotes]: Through diagonalization method, can I show that set of strings of odd length in $\{a,b,c\}^*$ is countable?

REPLY [0 votes]: Let $S_{2n+1}$ denote the set of string of length exactly $2n+1$. Since this set is finite, there is a mapping $f_n:S_{2n+1} \to |S_{2n+1}|$ (where |S| denotes the cardinality of $S$)which lists all elements in $S_{2n+1}$. Now consider the function $f:\cup_{n \in \mathbb{N}}S_{2n+1} \to \mathbb{N}$ defined by 
$$f(x)=\sum_{k=0}^{\nu-1}|S_{2k+1}|+f_{\nu}(x),$$
where $\nu$ is such that $x$ has length $2\nu+1$. Now let $x,y$ such that $f(x)=f(y)$, there exists $\nu_x,\nu_y$ such that $x \in S_{2\nu_x+1},y \in S_{2\nu_y+1}$. If $\nu_x < \nu_y$ then 
$$\sum_{k=0}^{\nu_x-1}|S_{2k+1}| <\sum_{k=0}^{\nu_y-1}|S_{2k+1}|,$$
and since $f_{\nu_x}(z)\leq |S_{2\nu_x+1}|$ for every $z\in S_{2\nu_x+1}$ we must have $f(x)<f(y)$ which is a contradiction. If $\nu_x = \nu_y$ then $f(x)=f(y)$ implies that $f_{\nu_x}(x)=f_{\nu_x}(y)$ and since $f_{\nu_x}$ is a bijection, we must have $x=y$. This shows that $f$ is injective. Now let $m \in \mathbb{N}$, and let $\nu$ be such that
$$\tilde m :=\sum_{k=0}^{\nu}|S_{2k+1}| < m\leq\sum_{k=0}^{\nu+1}|S_{2k+1}|,$$
then we must have $1\leq m-\tilde m \leq |S_{2\nu+1}|$ and since $f_\nu:S_{2\nu+1}\to |S_{2\nu+1}|$ is a bijection, there exists some $x \in S_{2\nu+1}$ such that $f_\nu(x)=m-\tilde m$. We finally get $f(x) = \tilde m + m-\tilde m = m$, which shows that $f$ is surjective. Thus $f$ is bijective and $\cup_{n \in \mathbb{N}}S_{2n+1} $ is countable.
{"set_name": "stack_exchange", "score": 1, "question_id": 911137}