Equinumerosity of strings and natural numbers

Question

so I'm trying to show that there exists a bijection from the infinite set of finite strings composed of elements from $\{a, b\}$ to $\mathbb{N}$. So I was thinking about showing that $\mathbb{N}$ and the infinite set of finite binary sequences are equinumerous (each have a unique representation), and then constructing a bijection between $\{a, b\}$ and $\{0, 1\}$. Then by the transitive property of equinumerosity, I would be done with my goal.

However, when you're writing something in binary, like 00001 (which would be equivalent to aaaab), and so I think this proof would exclude some cases? How else can I go about this?

Answer 1

Order the strings first by length and then alphabetically. So that the empty string corresponds to $0$, "a" corresponds to $1$, $b$ to 2, $aa$ to 3, and so on.

Answer 2

You could use the shortlex order as in saulspatz's answer, but you could also adapt your trick with binary numbers.

Do you agree that the map $u \to bu$ defines a bijection from $\{a,b\}^*$ to $b\{a,b\}^*$? Now use your bijection $a \to 0$, $b \to 1$ to get a bijection from $b\{a,b\}^*$ to $1\{0,1\}^*$. Then $1\{0,1\}^*$ is the set of all positive integers written in binary. If you want to include zero, just consider the bijection $\Bbb N-\{0\} \to \Bbb N$ defined by $n \to n-1$.

Answer 3

If your alphabet is $\{0, 1\}$, a simple way to describe the bijection with $\mathbb{N} = \{1, 2, \dotsc\}$ is to stick an 1 in front of the string, and read the result as a binary number. To go the other way around, write the number in binary and chop off the first digit.

The general case for an arbitrary alphabet is called bijective numeration