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?

  • 7
    $\begingroup$ 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! $\endgroup$ – Nick Peterson Dec 13 '13 at 14:20

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

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

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.

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

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

  • $\begingroup$ 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$ ? $\endgroup$ – Jean-Claude Arbaut Dec 13 '13 at 15:03
  • $\begingroup$ @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$ $\endgroup$ – AlexR Dec 13 '13 at 15:19
  • $\begingroup$ @AlexR I'm always puzzled by theses differences on such basic notations as sets! :-) $\endgroup$ – Jean-Claude Arbaut Dec 13 '13 at 15:22
  • $\begingroup$ @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. $\endgroup$ – AlexR Dec 13 '13 at 15:28
  • $\begingroup$ 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. $\endgroup$ – Ben Millwood Dec 15 '13 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_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 }$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.