Cardinality of the set of all bit strings not containing the bit "0" (i.e. $11$, $111$ ...)

Question

I need to show the cardinality of $S$, the set of all bit strings that don't contain the bit $0$.

I came up with a function that maps $\mathbb{N}$ to $S$ in the following way:

$f(n) = \sum_{i=0}^{n-1} 10^i$.

I think that this is a valid mapping because each natural number $n$ gets mapped to the string that contains exactly $n$ bits.

My question: I am having trouble understanding if this function is bijective.

My attempt:

Injectivity: Well, I'd need to prove that for $f(a) = f(b) \implies a=b$

$$f(a) = \sum_{i=0}^{a-1} 10^i = .f(b) = \sum_{i=0}^{b-1} 10^i$$

$10^0 + 10^1 + ...+ 10^{a-1} = 10^0 + 10^1 + ... + 10^{b-1}$

I'm stuck here. I don't know if I can cancel out all terms except the $10^{a-1}$ and $10^{b-1}$ (mostly because I can't operate on the presumption that $a=b$, that's what I need to prove).

Surjectivity: I don't know how to prove this mathematically.

Can anyone help?

Answer 1

Every positive integer $n$ corresponds $1-1$ with the string $1\cdots 1$ with $n$ ones , so the cardinality is the same as the cadinality of the positive integers , hence $\aleph_0$ , the strings form an infinite countable set.

Answer 2

In fact since $10^i>0$ you can prove strict monotonicity ($a<b\implies f(a)<f(b)$) quite easily hence injectivity.

For surjectivity finding the inverse function directly is also not too complicated.

i.e. $x=34$ then $4=10\times\{\frac x{10}\}$ and $3=(x-4)/10\quad$ (note: $\{x\}$ designate the fractional part)

This can be extended to decompose a number into its digits $d_i$ as below:

$\begin{cases}d_0=0\\x_0=x\end{cases}\ $ and $\ \begin{cases}d_{i+1}=10\times\{\frac {x_i}{10}\}\\x_{i+1}=(x_i-d_{i+1})/10\end{cases}$

Therefore as in our case all digits are either $1$ or trailing zeroes then $n=\sum\limits_{i=0}^\infty d_i$

Answer 3

One way to prove that function $f$ defined by $$f(n) = \sum_{i=0}^{n-1} 10^i$$ is a bijection is to guess its inverse function, and prove that that is indeed its inverse function.

Let $g$ be the function defined by $$g(N) = \log_{10}(9N+1).$$

For instance $g(1111) = \log_{10}(9\times1111+1) = \log_{10}(10000) = 4$.

Now all you have to do is prove that for every nonnegative integer $n$, $g(f(n)) = n$, and for every number $N$ which is a string of 1, $f(g(N)) = N$.

Answer 4

First of all, you're mixing up several different concepts. The term "string" refers to digits being considered just a collection of symbols. That is, the "string" 11 refers to two instances of the 49th ASCII character. This is different from 11 being considered as a base ten number, in which it is equal to $2 \times 2 \times 2+2+1$. This is in turn different from it considered as a base two number, in which it is equal to $2+1$.

Now, as for proving that $f(n) = \sum_{i=0}^{n-1}10^i$ is injective, it's clearly strictly increasing, because $f(n+1)-f(n)= 10^n>0$. And strictly increasing functions are injective. The geometric series formula gives you that $f(n) = \frac{r^n-1}{r-1}$. In this case, $r=10$, so that is $\frac{10^n-1}{9}$. $10^n$ is $1$ followed by $n$ zeroes. $10^n-1$ is $n$ nines. $\frac{10^n-1}{9}$ is $n$ ones. So it's possible to get $n$ ones for any $n>0$.

You can also use the geometric series to prove injectivity; if $a \neq b$, then WLOG, $a <b$, so $f(a) = \frac{10^a-1}{9} < \frac{10^b-1}{9}$.