11
$\begingroup$

Today a friend of mine told me a nice fact, but we couldn't prove it. The fact is that there is an injection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ defined by the fomula $(m,n)\mapsto (m+n)^{\max\{m,n\}}$, where $\mathbb{N}$ denotes the natural numbers.

How to prove that this map is injective? It should be elementary. We might be overlooking something trivial.

Thanks!

Edit As it was pointed out, it is not an injection by easy reasons. Thanks a lot! I was just overcomplicating things. But what if we restrict the map to the set of pairs $(m,n)$ such that $m>n$?

$\endgroup$
  • $\begingroup$ GitGud and Antonio, thanks for your comments! I've edited the question. $\endgroup$ – Sasha Patotski Jul 24 '13 at 0:12
  • 5
    $\begingroup$ The restriction of the function to $\{(m,n)\in\mathbb N^2:m\le n\}$ seems to be injective. Perhaps you can post a separate question. $\endgroup$ – user714630 Jul 24 '13 at 0:20
  • 1
    $\begingroup$ If $m > n$, then $\max\{m, n\}=m$, so the map is just $(m, n) \mapsto (m + n)^m$. $\endgroup$ – asmeurer Jul 24 '13 at 1:04
  • $\begingroup$ For anyone else who was looking for it, here's a newer question asking if it is injective restricted to $m \le n$. $\endgroup$ – 6005 May 1 '14 at 17:22
13
$\begingroup$

It is not an injection since $m+n=n+m$ and $\max(m,n)=\max(n,m)$.

$\endgroup$
4
$\begingroup$

Is not. For example $(3,2)$ and $(2,3)$ are both mapped to $5^3$.

$\endgroup$
1
$\begingroup$

A simple injection is given by $(m,n) \mapsto 2^m 3^n$.

$\endgroup$
  • $\begingroup$ The OP never asked for an injection. $\endgroup$ – Git Gud Jul 24 '13 at 0:15
  • 1
    $\begingroup$ A theoretical downvote for your comment, @GitGud $\endgroup$ – The Chaz 2.0 Jul 24 '13 at 0:27
  • $\begingroup$ @TheChaz2.0 ^_^ $\endgroup$ – Git Gud Jul 24 '13 at 0:28
0
$\begingroup$

As mentioned, this is not injective because we can freely swap $m$ and $n$ in your map and we get the same answer. However, try a map along the lines of $(m,n)\rightarrow 2^m\times 3^n$, are you okay with showing that this is injective?

$\endgroup$
  • $\begingroup$ The OP never asked for an injection. $\endgroup$ – Git Gud Jul 24 '13 at 0:17
  • 4
    $\begingroup$ @GitGud That doesn't mean this is not an useful answer, though. $\endgroup$ – Pedro Tamaroff Jul 24 '13 at 0:46
  • $\begingroup$ @PeterTamaroff Should I go give 'useful' answers unrelated to the questions? $\endgroup$ – Git Gud Jul 24 '13 at 0:49
  • 1
    $\begingroup$ Just lol at people upvoting the comment above. $\endgroup$ – Git Gud Jul 24 '13 at 6:40

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.