1

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 :)

Noy
  • 777

2 Answers2

2

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.

5xum
  • 123,496
  • 6
  • 128
  • 204
  • Thank you for your answer. It's a good concept, I thought of similar concepts, the problem is that those are hard to translate into Lambda functions. I must define the function as $\lambda$g$\in\mathbb{N}\to{0,1}$.$\lambda$n$\in\mathbb{N}$.[function here]- therefore define an image for all n in N. if n$\in$g^{-1}[0] then I have to ignore it and then it won't be a function. – Noy Dec 22 '17 at 10:23
1

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$$

mechanodroid
  • 46,490