injection $(\mathbb{N}\to\{0,1,2\})\to\ (\mathbb{N}\to\{0,1\})$ It is also possible to find a surjection in the other direction - I am trying to prove the cardinality of $$\mathbb{N}\to\{0,1,2\}$$ is less than or equal to $$\mathbb{N}\to\{0,1\}$$
 A: Hint: Write a function $\mathbb{N}\to\{0,1,2\}$ as a string of digits $0,1,2$. Now encode this string in binary, mapping $0 \mapsto 00$, $1 \mapsto 01$, $2 \mapsto 10$. This gives a function $\mathbb{N}\to\{0,1\}$ from which you can recover the original function.
A: For a sequence $f : \mathbb{N} \to \{0, 1, 2\}$ define a sequence mapping the digits as $0 \mapsto 1$, $1 \mapsto 10$, $2 \mapsto 100$.
For example:
$$(1,2,1,0,2, \ldots ) \mapsto (1,0,1,0,0,1,0,1,1,0,0, \ldots)$$
This map is clearly injective since the number of zeros after each $1$ determines which was the digit of the original sequence.
A: For $f \colon \mathbb N \to \{0,1,2\}$ and $n \in \mathbb N$ let
$$
f^*(3n) = \begin{cases}
1 & \text{, if } f(n) = 0 \\
0 & \text{, otherwise}
\end{cases}
$$
$$
f^*(3n+1) = \begin{cases}
1 & \text{, if } f(n) = 1 \\
0 & \text{, otherwise}
\end{cases}
$$
$$
f^*(3n+2) = \begin{cases}
1 & \text{, if } f(n) = 2 \\
0 & \text{, otherwise}
\end{cases}
$$
Then
$$
\pi \colon (\mathbb N \to \{0,1,2\}) \to (\mathbb N \to \{0,1\}), \ f \mapsto f^*
$$
is an injection.
A: You can encode the functions of $\mathbb N \to \{0, 1, 2\}$ into $\mathbb N \to \{0, 1\}$ as follows:
given a function $f : \mathbb N \to \{0, 1, 2\}$, 


*

*let $g(2n) = f(n)$ if $f(n) \in \{0, 1\}$, and $g(2n) = 0$ otherwise, 

*and let $g(2n+1) = 1$ if $f(n) = 2$, and $g(2n+1) = 0$ otherwise.

