How do I use prove this function is bijective?

Question

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.

Answer 1

Hint:

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.

Answer 2

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.