How do I represent the set of all finite bit strings?

Question

At first I thought I could just represent them with the set of natural numbers, because each bit string represents some natural number. However doing this would mean the strings '010' and '00010' are the same, which they are not.

Answer 1

Here's one easy way to biject the finite binary strings to the natural numbers (let's say we're thinking of the natural numbers as not including zero):

• Step $1$: put a "$1$" on the left.

• Step $2$: view the resulting string as a number in binary as usual.

E.g. "$010$" turns into "$1010$," which is ten. The empty string meanwhile turns into the string $1$, which then turns into the number one.

---

If we want to get $0$ in the mix too, we can just add "Step $3$: subtract $1$" to the above.