Suppose that $A$ is the set of all finite binary strings. We need to show an injection $A \rightarrow \mathbb{N}$ and $\mathbb{N} \rightarrow A$.
- $\mathbb{N} \rightarrow A$
Each number in the decimal system has its own unique representation in the binary system, which makes this an injective function.
- $A \rightarrow \mathbb{N}$
We first put a "1" at the beginning of every binary string, so that for example $0001$ becomes $10001$. This is to avoid $0001$ and $001$ being mapped to the same element. Then, we convert the number in the binary system to the decimal system.
My question is: Even though I intuitively know that each number in the decimal system has its own unique representation in the binary system, since I don't have an explicit $f(n)= ..., n \in \mathbb{N}$ formula, I don't know how to prove it. Do I need to prove it further, or is what I said above sufficient?
The same goes for the second injective function. Intuitively, it seems fine, but since I don't have an explicit formula I don't know how to show injectivity.
Can anyone help?
Consider this alternate proof.
Map each binary sequence $b=(a_1, a_2,..., a_n)$ where the $a_i$ are the digits from right to left, as in that $a_1$ is the first digit from the right $a_2$ the second and so on to the natural number $$N(b) = \prod_{i=1}^{n}p_i^{a_i}$$ Where $p_i$ is the $i^{\text{th}}$ smallest prime. It should be easy to see that this is an injection of $A$ into $\mathbb N$.
This shows that $A$ has the same cardinality as some subset of $\mathbb N$. Realizing that every infinite subset of $\mathbb N$ has the same cardinality as that of $\mathbb N$ and proving that $A$ is infinite will complete the proof.
Although this is different from the proof you are proposing, I hope it is still of help as this one only constructs 1 injection (saving you the trouble of having to come up with a second) and even that with an explicit formula.