# Injection $\mathbb N \times \mathbb N \times \mathbb N \to \mathbb N$

I have to give an example of an injection $\mathbb N \times \mathbb N \times \mathbb N \to \mathbb N$.

Would something like $f(x)=x^3$ be an answer to this question?

• No. An injection $\mathbb{N}\times\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ must, first and foremost, be a function $\mathbb{N}\times\mathbb{N}\times\mathbb{N}\to\mathbb{N}$. Your function should have three variables! Dec 13, 2013 at 14:20

Hint: It might be helpful to think about the fact that prime factorizations are unique -- so that any function which yields different prime factorizations for every input will definitely be an injection.

• So something like $f=2^x3^y5^z$? Dec 13, 2013 at 14:23
• @user112495 Exactly what I had in mind. Dec 13, 2013 at 14:43
• Actually the same argument yields $\mathbb{N} \cong \mathbb{N}^\infty := \cup_n \mathbb{N}^n$. Dec 13, 2013 at 15:28

Let $a_n(k)$ be the $n$-th digit of $k$ counted from the least significant and starting at $0$, i.e. $$a_n(k) = \lfloor 10^{-n} \cdot k \rfloor \text{ mod } 10$$ Then $$f(n_1, n_2, n_3) := \sum_{j=0}^{\infty} a_j(n_1) \cdot 10^{3j} + a_j(n_2) \cdot 10^{3j+1} + a_j(n_3) \cdot 10^{3j+3}$$ does the trick. This can be considered "mingling" the digits:

$$f(12,34,56) = 531642$$

The "advantage" over the prime-factorisation is that $f$ is also surjective with inverse. $$f^{-1}(n) = \left(\sum_{j=0}^\infty a_{3j}(n) 10^j, \sum_{j=0}^\infty a_{3j+1} 10^j, \sum_{j=0}^\infty a_{3j+2}(n) 10^j\right)$$

• Would something like $f=2^x3^y5^z$ also be a correct answer to the question? Dec 13, 2013 at 14:29
• @user112495 Since you only want an injection, yes. Dec 13, 2013 at 14:33

Hint: Use the fact that prime factorisations are unique.

I prefer (assuming that $0\notin\mathbb N$) $$(x,y,z)\mapsto \left((2x-1)2^{y}-1\right)2^{z-1}$$ (why?)

• And if, as usual, $0 \in \Bbb N$, I suppose it would be $(x,y,z) \to ((2x+1)2^{y+1}-1)2^z-1$ ? Dec 13, 2013 at 15:03
• @arbautjc "As usual" cannot be said here. I see $0\notin \mathbb N$ much more often and $\mathbb N_0 := \mathbb N \cup \{0\}$. This prevents many "special cases" in theorems involving $\mathbb N$ Dec 13, 2013 at 15:19
• @AlexR I'm always puzzled by theses differences on such basic notations as sets! :-) Dec 13, 2013 at 15:22
• @arbautjc That's why most of the time an author makes note of his convention before using it. A simple reference as to why I assume $0\notin \mathbb N$ is that then, $(\mathbb Z, +)$ is the "completion" of $\mathbb N$ by adding both, additive inverse and neutral element and $(\mathbb N, +)$ doesn't have any element with additive inverse. Dec 13, 2013 at 15:28
• On the other hand, if $0 \in \mathbb N$ then $\mathbb N$ is precisely the set of finite sizes, which seems somehow a neater description than "positive integers" or whatever. I think this is essentially a question for which the algebraist's answer is different from the logician's. Dec 15, 2013 at 1:07

Given a bijection $\varphi : \Bbb N \times \Bbb N \to \Bbb N$, simply use the bijection

$$(x,y,z) \to \varphi(\varphi(x,y),z)$$

For $\varphi$, you can use for example:

$$\varphi_1(x,y)=(2x+1)2^y-1$$

Or

$$\varphi_2(x,y)=\frac 1 2 (x+y)(x+y+1)+y$$

To give an idea of $\varphi_2$, here is an array with entries $a_{ij}=\varphi_2(i,j)$ (indices starting at $0$):

$$\pmatrix{ 0&2&5&9&14&20\cr 1&4&8&13&19&26\cr 3&7&12&18&25&33\cr 6&11 &17&24&32&41\cr 10&16&23&31&40&50\cr 15&22&30&39&49&60\cr }$$

And with $\varphi_1$:

$$\pmatrix{0&1&3&7&15&31\cr 2&5&11&23&47&95\cr 4&9&19&39&79&159\cr 6& 13&27&55&111&223\cr 8&17&35&71&143&287\cr 10&21&43&87&175&351\cr }$$