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?
$\begingroup$
$\endgroup$
1
-
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 PetersonDec 13, 2013 at 14:20
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
3
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.
answered Dec 13, 2013 at 14:21
-
4
-
2$\begingroup$ @user112495 Exactly what I had in mind. $\endgroup$ Dec 13, 2013 at 14:43
-
2$\begingroup$ Actually the same argument yields $\mathbb{N} \cong \mathbb{N}^\infty := \cup_n \mathbb{N}^n$. $\endgroup$ Dec 13, 2013 at 15:28
$\begingroup$
$\endgroup$
2
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$ Dec 13, 2013 at 14:29
-
1$\begingroup$ @user112495 Since you only want an injection, yes. $\endgroup$– AlexRDec 13, 2013 at 14:33
$\begingroup$
$\endgroup$
Hint: Use the fact that prime factorisations are unique.
answered Dec 13, 2013 at 14:21
$\begingroup$
$\endgroup$
5
I prefer (assuming that $0\notin\mathbb N$) $$ (x,y,z)\mapsto \left((2x-1)2^{y}-1\right)2^{z-1}$$ (why?)
answered Dec 13, 2013 at 14:49
-
$\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$ Dec 13, 2013 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$– AlexRDec 13, 2013 at 15:19
-
$\begingroup$ @AlexR I'm always puzzled by theses differences on such basic notations as sets! :-) $\endgroup$ Dec 13, 2013 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$– AlexRDec 13, 2013 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$ Dec 15, 2013 at 1:07
$\begingroup$
$\endgroup$
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 }$$
answered Dec 13, 2013 at 15:05