Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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

share|cite|improve this question
GitGud and Antonio, thanks for your comments! I've edited the question. – Sasha Patotski Jul 24 '13 at 0:12
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. – Karl Kronenfeld Jul 24 '13 at 0:20
If $m > n$, then $\max\{m, n\}=m$, so the map is just $(m, n) \mapsto (m + n)^m$. – asmeurer Jul 24 '13 at 1:04
For anyone else who was looking for it, here's a newer question asking if it is injective restricted to $m \le n$. – 6005 May 1 '14 at 17:22
up vote 12 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
The OP never asked for an injection. – Git Gud Jul 24 '13 at 0:15
A theoretical downvote for your comment, @GitGud – The Chaz 2.0 Jul 24 '13 at 0:27
@TheChaz2.0 ^_^ – Git Gud Jul 24 '13 at 0:28

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?

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

Your Answer


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.