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.

  • 1
    $\begingroup$ What do you mean by represent? Do you mean, find some well-known or understandably constructed set that is bijective with the set of finite-length binary strings? $\endgroup$ – Isky Mathews May 5 '18 at 19:58
  • 1
    $\begingroup$ If so, how does $2^\omega$ work for you? $\endgroup$ – Isky Mathews May 5 '18 at 19:58
  • 1
    $\begingroup$ Perhaps an extension to a subset of $\Bbb Q$, something like $\frac n{(n+1)^k}$ for a number $n$ with $k$ leading zeroes? $\endgroup$ – abiessu May 5 '18 at 19:59
  • 2
    $\begingroup$ A notation for it is $\{0,1\}^*,$ where the star means Klein star. Which is $$\bigcup _{i = 0}^{\infty}\{0,1\}^i,$$ and $\{0,1\}^i$ are i ordered tuples of elements from $\{0,1\}$ $\endgroup$ – Phicar May 5 '18 at 19:59
  • 3
    $\begingroup$ @IskyMathews "$2^\omega$" denotes the set of infinite binary strings. $\endgroup$ – Noah Schweber May 5 '18 at 20:06

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.


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.