Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
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! –  Nicholas R. Peterson Dec 13 '13 at 14:20

5 Answers 5

up vote 8 down vote accepted

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

share|improve this answer
    
Would something like $f=2^x3^y5^z$ also be a correct answer to the question? –  user112495 Dec 13 '13 at 14:29
1  
@user112495 Since you only want an injection, yes. –  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.

share|improve this answer
3  
So something like $f=2^x3^y5^z$? –  user112495 Dec 13 '13 at 14:23
1  
@user112495 Exactly what I had in mind. –  Nicholas R. Peterson Dec 13 '13 at 14:43
1  
Actually the same argument yields $\mathbb{N} \cong \mathbb{N}^\infty := \cup_n \mathbb{N}^n$. –  Martin Brandenburg Dec 13 '13 at 15:28

Hint: Use the fact that prime factorisations are unique.

share|improve this answer

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

share|improve this answer
    
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 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 }$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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