Let $D$ be the set of all functions $f:\Bbb Z_+\to\Bbb Z_+$.
Let $E$ be the set of all functions $f:\Bbb Z_+\to\{0,1\}$.
Show that $D$ and $E$ have the same cardinality.
My thoughts:
Obviously there is a bijection between $E$ and the set $F$ of all infinite sequence of 0's and 1's. There is a bijection between the set $D$ and the the set $G$ of all infinite sequence of natural numbers.
Thus we only need to show $F$ and $G$ have the same cardinality. And obviously $F\subset G$. Then we can use the following lemma:
If $B\subset A$ and if there is an injection $f:A\to B$, then $A$ and $B$ have the same cardinality.
Thus we only need to find an injection from $G$ to $F$. I have trouble here. I have the idea of using the binary notation. But how many bits to use is a problem. For example, I can map the sequence 3, 3, 3, … to 1, 1, 1, 1, …. But in this way, 7, 7, 7, … is also mapped to 1, 1, 1, …. The bits must be able to hold the biggest number and the same number of bits must be used for all numbers. Then, how to map 1, 2, 3, 4, 5, … to 0, 1 sequence? In this case, there is no biggest number.
With a little different view, I seem to be fine. For example, consider the sequence 1, 2, 3, 4, 5, … as the decimal number of 0.12345… Then I can absolutely change this 0.12345… into its binary form. Then removing the 0. I can get the mapping of 0's and 1's.
Are my thoughts correct? If not, what is wrong? Hints of another way to prove same cardinality is welcomed.
Best Answer
Hint: To a sequence $a_n$ of natural numbers assign $$(\overbrace{1,\dots, 1}^{a_1}, 0, \overbrace{1,\dots, 1}^{a_2},0, \overbrace{1,\dots, 1}^{a_3},0,\dots) $$