Q:

Prove that $f(m,n) = 2^m(2n +1 ) -1 $ is a bijection

Basically this proves that set of natural numbers is equinumerous to its cartesian product with itself.
f
I have tried proving injectivity and surjectivity.Here is what I have done so far.
To prove injectivity I have assumed that $f(a,b)=f(c,d)$ then I proved contradiction when $a=b$ and $c\neq d$,as well as when $a\neq b$ and $c=d$.I have managed to get contradiction for those cases but I did not manage to get a contradiction when both $a\neq b$ and $c\neq d$
For surjectivity I tried using the fact that if some sets(namely range of function and set of natural numbers) are subsets of each other then they are equal.That has led me nowhere
Any help would be appreciated

A:

You may have overcomplicated the proof of injectivity: if we assume $f(a,b) = f(c,d)$, we have that:
$$2^a(2b+1) = 2^c(2d+1)$$
By the Fundamental Theorem of Arithmetic (unique factorization), since $2b+1$ and $2d+1$ are odd, we must have $a = c$. This is because the highest power of $2$ dividing both sides must be the same, and $2$ certainly does not divide $2b+1$ and $2d+1$. Hence $a =b$, and it follows that $b = d$, so $f$ is injective.
Surjectivity follows from the Fundamental Theorem as well: if $x \in \mathbb{N}$ we can factorise $x-1$ into primes, and letting $k$ be the product of all of the odd prime factors of $x-1$, have $x -1 = 2^mk $ for some $m \in \mathbb{N}$, $k$ is certainly odd so $k = 2n+1$ for some $n \in \mathbb{N}$, so $x =2^m(2n+1) + 1 = f(m,n)$, so $f$ is surjective. 

