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?
Asked
Active
Viewed 489 times
4
-
7No. 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! – Nick Peterson Dec 13 '13 at 14:20
5 Answers
16
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.
Nick Peterson
- 32,430
-
4
-
2
-
2Actually the same argument yields $\mathbb{N} \cong \mathbb{N}^\infty := \cup_n \mathbb{N}^n$. – Martin Brandenburg Dec 13 '13 at 15:28
8
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)$$
AlexR
- 24,905
-
Would something like $f=2^x3^y5^z$ also be a correct answer to the question? – user112495 Dec 13 '13 at 14:29
-
1
5
I prefer (assuming that $0\notin\mathbb N$) $$ (x,y,z)\mapsto \left((2x-1)2^{y}-1\right)2^{z-1}$$ (why?)
Hagen von Eitzen
- 374,180
-
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$ ? – Jean-Claude Arbaut Dec 13 '13 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$ – AlexR Dec 13 '13 at 15:19
-
@AlexR I'm always puzzled by theses differences on such basic notations as sets! :-) – Jean-Claude Arbaut Dec 13 '13 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. – AlexR Dec 13 '13 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. – Ben Millwood Dec 15 '13 at 01:07
3
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 }$$
Jean-Claude Arbaut
- 23,277