Suppose I have the following function $e : \mathbb{N} \times \mathbb{N} \to \mathbb{N}_1$, where $\mathbb{N}_1$ is the set of natural numbers starting from 1 instead of 0:

$$e(m,n) = 2^m (2n+1)\ \ \ \forall m,n \in \mathbb{N}$$

I want to show that the map $e$ is bijective.

So I have to show it is both injective and surjective. To show that it's injective, here are my thoughts:

  1. Show for all $m,n$, we have $2^m$ and $2n+1$ being strictly increasing, and so the function is also a strictly increasing one.

  2. Since it is strictly increase, there can only be a one-to-one input to output mapping, and so the function is injective trivially.

Now surjection will be harder to prove.

My thoughts are:

  1. This problem has actually 2 arguments instead of the standard 1 argument function, so I suppose I would need to prove individually for each $m$ and $n$. Since they are natural numbers, induction come into mind.
  2. I should try to prove that for $\forall m$, starting from $e(0,n)$ and proving the inductive hypothesis, that $2^m$ is surjective. (is this true? A brief idea of Cantor's diagonalization argument makes me think this might be false).

  3. Then I try to prove for all $2n+1$ it is surjective. This can be done quite easily since if we keep $m$ constant, then the image $2n+1$ is essentially enumerable. In fact, can we use this argument to prove that $e(m,n)$ is enumerable for all $m$ we vary and $n$ is constant?

  4. Finally, having proven that for both cases where $m$ varies and $n$ is constant (and vice versa) they are injective, we can see that the resultant function is surjective as it is closed under multiplication. Is this the right way to define it?

That is the most reasonable shot I can give so far but I've no idea whether this is correct.

Note: the goal is to prove this without using the fundamental theorem of arithmetic.

  • $\begingroup$ Your reasoning for the injectivity of $e$ is flawed: Consider for example $f(x,y) = x+y$. $f$ is strictly increasing in each component but not injective since $f(1,2) = f(2,1)$. Your approach for the surjectivity also won't work. You need to consider the function in its entirety -- not component-wise. $\endgroup$ – Stefan Mesken Jun 5 '18 at 22:17
  • 2
    $\begingroup$ As written, your title (the ""this set is bijective" part, specifically) makes no sense. To talk of "bijective" you need two sets. Rather you need to ask about "these two sets are in bijection" or "this set is bijective with that one" or some such. $\endgroup$ – Andrés E. Caicedo Jun 5 '18 at 22:17
  • $\begingroup$ As for the function you describe... it helps to remember the fundamental theorem of arithmetic, that every number can be uniquely decomposed into a product of primes. It follows then that every number can be uniquely expressed as a power of two times an odd number. $\endgroup$ – JMoravitz Jun 5 '18 at 22:24
  • $\begingroup$ @AndrésE.Caicedo Thanks for pointing it out, I mean the function actually but wrote wrongly unfortunately. $\endgroup$ – winnie99 Jun 5 '18 at 22:27
  • $\begingroup$ Is there a way to prove it without using the fundamental theorem of arithmetic? I'm told there is a way to do so but I don't see how we can. Also, for the injectivity part, I don't think $f(2,1) = f(1,2)$. The former gives 12 but the latter gives 10. $\endgroup$ – winnie99 Jun 5 '18 at 22:29


Injectivity: Suppose $e(m,n) = e(m',n').$ Then, first deduce that $m = m'$ by arguing by contradiction and then it immediately follows $n =n'.$

Surjectivity: If you insist on not invoking the Fundamental Theorem of Arithmethic, then use a strong induction. Note that Fundamental Theorem of Arithmetic is an overkill for proving surjectivity anyway, because a big appeal of the theorem is the unique factorization which isn't needed at all for proving the surjectivity of your function.

  • $\begingroup$ The perplexing part is how can one use strong induction for 2 varying arguments? So far I've only seen cases proving for 1 argument but not two, unfortunately. $\endgroup$ – winnie99 Jun 5 '18 at 22:42
  • $\begingroup$ @winnie99 not necessary. Use the induction on the positive integer $N$ in the range of your function, for which you are trying prove that there is $m,n$ such that $e(m,n) = N.$ Not on the arguments $m,n.$ $\endgroup$ – dezdichado Jun 5 '18 at 22:44
  • $\begingroup$ However, $N$ on the right hand side is dependent on both $m$ and $n$. If this is the case, how should i form the induction hypothesis? $\endgroup$ – winnie99 Jun 5 '18 at 22:53
  • $\begingroup$ I don't understand your confusion. First prove the base case for $N = 2,4$.Then, assume the hypothesis for $N = 2,4,...,2M-2$ - strong induction. Now prove the claim for $N = 2M.$ If $M$ is already odd, $M = 2m+1$ then there is nothing to prove as $N = 2M = e(1,m).$ If $M = 2m$ is even, then now use the induction hypothesis assumption. $\endgroup$ – dezdichado Jun 5 '18 at 23:09

Your function is $ e(m,n)= 2^m(2n+1)$ and you want to show that it is both injective and surjective.

For injectivity you have to show $$ 2^{m_1}(2n_1+1)=2^{m_2}(2n_2+1) \implies m_1 =m_2 \text { and } n_1 =n_2 $$ Your proof is not valid because strictly increasing on each component does not imply injectivity.

For surjectivity you have to show that for any natural number k, there are non-negative integers $m$ and $n$ such that $2^m(2n+1)=k$

Your proof does not cover that either.

Apparently you are making the problem more complicated than it is by thinking componentwise increasing and somehow componentwise surjectivity.

  • $\begingroup$ Is there a way to show that a strictly increasing function is not injective? The problem is a bit complex since I'm not sure how I can make use of both $m$ and $n$ to prove that any natural number $k$ will exist. I think it is possible to show for all $n$ and $m$ the equation gives a natural number, but I don't know how to show it can cover all of the image, unfortunately. $\endgroup$ – winnie99 Jun 5 '18 at 22:55
  • $\begingroup$ I might have seen something, not sure if this is right: $2^m$ seems to show even numbers, while $2n+1$ seems to show odd number. Can I use this to show that thus $k$ can be any odd or even number? $\endgroup$ – winnie99 Jun 5 '18 at 22:56
  • $\begingroup$ For the injectivity, start canceling 2 's from both sides. Eventually you go out of 2 in one side which means one side will be odd. The other side must be also odd, so $m_1=m_2$. and $2n_1+1=2m_2+1.$ For surjectivity, each natural number is either odd in which case $m=0,$ or it is even which you divide by $2$, $m$ - times until you get an odd number. $\endgroup$ – Mohammad Riazi-Kermani Jun 5 '18 at 23:03

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