Injection from $\mathbb{N}\to\{0,1\}$ to the set of all monotonic decreasing functions from $\mathbb{N}\to\mathbb{Z}$ I'm trying to think of such an injection, and unfortunately all of those I've thought about are not strictly decreasing. I would love to get some help or clues. Thank you :)
 A: Every element in $\mathbb N\to\{0,1\}$ is basically a sequence of ones and zeroes, i.e. it can be represented as, for example, $0,0,1,0,0,1,0,1,0,1,1,0,0,0,\dots$.
One injection would transform that sequence into $-3,-6,-8,-10,-11,\dots$ where you simply list where the ones appear (and put a minus sign in front).
I'll leave the details to you.
A: Given a sequence $(x_n)_{n=1}^\infty \in \mathbb{N} \to \{0,1\}$ map it to the strictly decreasing sequence $$\phi\left((x_n)_{n=1}^\infty\right) = \left(-n-\sum_{i=1}^n x_i\right)_{n=1}^\infty \in \mathbb{N} \to \mathbb{Z}$$
The map $\phi$ is well-defined since every partial sum is indeed an integer and it is strictly decreasing since $x_i \ge 0$: $$-n - \sum_{i=1}^n x_i > -(n+1) - \sum_{i=1}^{n+1}x_i$$
$\phi$ is injective:
Assume $(x_n)_{n=1}^\infty, (y_n)_{n=1}^\infty \in \mathbb{N} \to \{0,1\}$ are sequences such that $\phi\left((x_n)_{n=1}^\infty\right) = \phi\left((y_n)_{n=1}^\infty\right)$.
Inductively we obtain:
$$-1 - x_1 = -1 - y_1 \implies x_1 = y_1$$
$$-2 - x_1 - x_2 = -2 - y_1 - y_2 \implies x_2 = y_2$$
$$\vdots$$
$$-n - x_1 - x_2 - \ldots - x_n = -n - y_1 - y_2 - \ldots - y_n \implies x_n = y_n$$
$$\vdots$$
$$\implies (x_n)_{n=1}^\infty = (y_n)_{n=1}^\infty$$
