Inverse of a function - Set Theory Please help me with this exercise...
I already showed that the function is bijective, and I do not know how to find the inverse of the function...
Be the function $f : \mathbb{N} \times  \mathbb{N}  \rightarrow \mathbb{N}$ defined by $f(m,n) = 2^m (2n+1) - 1$
 A: Let $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ be given by
$$(m,n)\mapsto 2^m(2n+1)-1.$$
We know that $f$ is bijective. Let's construct the inverse.

Given an integer $M$, by the fundamental theorem of arithmetic, $M+1$ can be written in a unique power of prime numbers, namely 
$$M+1=2^m\cdot \prod_{\substack{p_i\geq 3\\p_i\text{ prime}}}p_i^{s_i}=2^m q.$$
But, $q$ is an odd number, which means it can be written uniquely as $q=2n+1$. We thus have $M+1=2^m(2n+1)$ with $m,n$ unique by constuction. Define your inverse map to be 
$$M\mapsto (m,n)$$
as defined above. This answers your question.
A: Given $q\in \mathbb N $,
we look for integers $m,n $ such that
$$2^m (2n+1)=q+1$$
we write $q+1$ as a product of powers of prime numbers as
$$q+1=2^a.3^b.5^c... $$
$=2^a\times$ an odd integer which has the form $2p+1$.
thus $m=a,n=p $.
For example, $q=59$.
then
$$q+1=60=2^2.3.5=2^2 (2.7+1) $$
hence
$$f (2,7)=2^2 (2.7+1)-1=59$$
A: The reason it's bijective is cause every number can be written as a unique product of a power of two and an odd number. 
So the inverse function is the function that takes in a natural number and follows these instructions:


*

*Add one

*factor the result into a power of two times an odd number $2^mq$

*$m$ is the exponent of two in this factorization and $n = \frac{q-1}{2}$

*Return the ordered pair $(m,n)$.

A: The other answers do a good job explaining that if $p=f(m,n)$ then $2^m$ is the greatest power of two that divides $p+1$. However, so far all the inverse functions are described in words. If you want a formula for the inverse function, first define $\mathrm{Ruler}(q)$ to be the exponent of the highest power of two that divides $q$. This is a common function in number theory, although if you search for it you may find the same-named but different Thomae's function on the real numbers. Python code for $\mathrm{Ruler}()$ is given at the end of this answer though in theoretical mathematics it would be defined by recursion. Given that function, $m$ is easy to find as $\mathrm{Ruler}(p+1)$ and the hard part is showing a formula for $n$. Here are three expressions for your inverse function with the result given as an ordered pair $(m,n)$.
In MathJax:
$$f^{-1}(p)=\left(\mathrm{Ruler}(p+1),\ \frac{\dfrac{p+1}{2^{\mathrm{Ruler}(p+1)}}-1}2\right)$$
In an inline expression (using two asterisks for exponentiation rather than the caret since I can't figure out how to escape the caret character in MathJax):
$$f^{-1}(p)=(\mathrm{Ruler}(p+1), ((p+1)/2\mathrm{**}\mathrm{Ruler}(p+1)-1)/2)$$
As a Python code line:
(Ruler(p+1), ((p+1) // 2**Ruler(p+1) - 1) // 2)
And here is my Python code for the ruler function:
def ruler(n):
    """Return the exponent of the highest power of 2 dividing n.  This
    is also the number of trailing zeros in the binary expansion of n,
    or the number of trailing ones in the binary expansion of n - 1.
    A graph of this resembles the markings of fractions of an inch on a
    ruler. See sequence A007814 at oeis.org."""
    n = int(n)
    if not n:
        raise ValueError('ruler(0) is undefined')
    result = 0
    while not (n & 1):
        n >>= 1
        result += 1
    return result

