Show function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ defined by $f(m, n) = 2^{m}(2n + 1)$ is a bijection 
Let $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \ \{0\}$ be the map given by $f(m, n) = 2^{m}(2n + 1)$ for all $(m, n) \in \mathbb{N} \times \mathbb{N}$.  Show that $f$ is a bijection.

The above seems quite unintuitive since there needs to be a one to one correspondence. It has to be bijective but I don't know how I can prove that.
My thought process was that the first part of the function is always even and the second part $(2n+1)$ is even for odd $n$ and odd for even $n$.
This means that the result can be both even and odd. How do I show that there is no value that is hit twice?
 A: Your $f$ is not a bijection.
There are two cases to consider because different ideas what $\Bbb N$ is exist:
a) $0\in \Bbb N$. In that case, there is no $(m,n)$ with $f(m,n)=0$, because we always have $2^m\ne 0$ and $2n+1\ne0$.
b) $0\notin \Bbb N$. In that case,  there is no $(m,n)$ with $f(m,n)=1$, because we always have that $2^m\ge2$ and even, making $f(m,n)$ even.
In both cases, $f$ fails to be surjective, hence cannot be bijective.
A: While Hagen's answer addresses the mistake in your question and why in that form it is not a bijection, this is a typical example of bijection if corrected. However, the form depends on whether you define natural numbers with $0$ or without. To avoid confusion, let's write $\mathbb{Z}_{\geq 0}$ and $\mathbb{Z}_{>0}$ for non-negative and positive integers respectively.
For $f:\mathbb{Z}_{> 0} \times \mathbb{Z}_{> 0} \to \mathbb{Z}_{> 0}$, we can show that $f(m,n)=2^{m-1}(2n-1)$ is a bijection. The result follows from fundamental theorem of arithmetic (unique factorization theorem), since for every positive integer $a$ there exists (surjectivity) unique (injectivity) representation of $a$ in form $a=2^{e_1}(p_2^{e_2}\cdots p_k^{e_k})$ where $p_i$ is $i$-th prime number and $e_i \geq 0$. Then you can choose $m-1=e_1$ (since $e_1 \geq 0$ we have $m$ a positive integer) and $2n-1=p_2^{e_2}\cdots p_k^{e_k}$ (since the primes on the right side are odd, their product is also odd and so $n$ is a positive integer).
For $g:\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}$, we cannot invoke the unique factorization theorem directly because it does not apply for $0$, but we can use our previous result. If we shift $(m,n)$ to $(m+1,n+1)$ in $f$, we have a bijection $f':\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{> 0}$ given $f'(m,n)=2^{m}(2n+1)$. Now if we shift the resulting value by $-1$ we get a bijection $g:\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}$ given $g(m,n)=2^{m}(2n+1)-1$.
To summarize, your original problem could be any of these bijections:

*

*$f:\mathbb{Z}_{> 0} \times \mathbb{Z}_{> 0} \to \mathbb{Z}_{> 0}$, $f(m,n)=2^{m-1}(2n-1)$

*$f':\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{> 0}, f'(m,n)=2^{m}(2n+1)$

*$f'':\mathbb{Z}_{> 0} \times \mathbb{Z}_{> 0} \to \mathbb{Z}_{\geq 0}$, $f''(m,n)=2^{m-1}(2n-1)-1$ (not discussed above but an easy consequence)

*$g:\mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}$, $g(m,n)=2^{m}(2n+1)-1$
A: Let's change the image of the function, let $f:\mathbb{N}\times\mathbb{N}\rightarrow \mathbb{N}\smallsetminus\{0\}$.
To show that $f$ is injective, suppose that $f(m,n)=f(r,s)$, that is
$$
2^m(2n+1)=2^r(2s+1).
$$
By the fundamental theorem of Arithmetic, you have unique factorisation, so that $m=r$, and so
$$
2n+1=2s+1
$$
which obviously implies that $n=s$. Therefore $(m,n)=(r,s)$ and $f$ is injective.
To prove that $f$ is surjective, if $a$ is a positive integer, let $m$ the highest power of 2 dividing $a$, then
$$
\frac{a}{2^m}
$$
is an odd integer, that you can write as $\frac{a}{2^m}=2^n+1$, for a unique integer $n\in\mathbb{N}$. So $f(m,n)=a$ and $f$ is surjective.
