Inverse of a function - Set Theory

Question

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$

Answer 1

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.

Answer 2

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$$

Answer 3

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:

1. Add one
2. factor the result into a power of two times an odd number $2^mq$
3. $m$ is the exponent of two in this factorization and $n = \frac{q-1}{2}$
4. Return the ordered pair $(m,n)$.

Answer 4

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