Inversa de una función - la Teoría de conjuntos

Question

Por favor me ayudan con este ejercicio...

Yo ya mostró que la función es bijective, y no sé cómo encontrar la inversa de la función...

Ser la función de $f : \mathbb{N} \times \mathbb{N}  \rightarrow \mathbb{N}$ definido por $f(m,n) = 2^m (2n+1) - 1$

Answer 1

Deje $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ ser dada por $$(m,n)\mapsto 2^m(2n+1)-1.$$ Sabemos que $f$ es bijective. Vamos a construir la inversa.

---

Dado un entero $M$, por el teorema fundamental de la aritmética, $M+1$ puede ser escrito en un único poder de los números primos, es decir, $$M+1=2^m\cdot \prod_{\substack{p_i\geq 3\\p_i\text{ prime}}}p_i^{s_i}=2^m q.$$ Pero, $q$ es un número impar, lo que significa que puede escribirse de forma única como $q=2n+1$. Por lo tanto tenemos a $M+1=2^m(2n+1)$ $m,n$ único por construcción. Definir su inversa mapa $$M\mapsto (m,n)$$ como se definió anteriormente. Esto contesta a tu pregunta.

Answer 2

Dado $q\in \mathbb N $, buscamos enteros $m,n $ tal que

$$2^m (2n+1)=q+1$$

escribimos $q+1$ como un producto de potencias de números primos como

$$q+1=2^a.3^b.5^c... $$ $=2^a\times$ un entero impar que tiene la forma $2p+1$.

por lo tanto $m=a,n=p $.

Por ejemplo, $q=59$.

entonces $$q+1=60=2^2.3.5=2^2 (2.7+1) $$

por lo tanto $$f (2,7)=2^2 (2.7+1)-1=59$$

Answer 3

La razón es bijective es la causa de cada número se puede escribir como un producto único de una potencia de dos y un número impar.

Así, la función inversa es la función que toma un número natural y sigue estas instrucciones:

1. Agregar uno
2. factor el resultado en una potencia de dos veces un número impar $2^mq$
3. $m$ es el exponente de dos en esta factorización y $n = \frac{q-1}{2}$
4. Devolver el par ordenado $(m,n)$.

Answer 4

Las otras respuestas, hacer un buen trabajo de explicar que si $p=f(m,n)$ $2^m$ es la mayor potencia de dos que divide $p+1$. Sin embargo, hasta el momento todas las funciones inversas se describe en las palabras. Si desea una fórmula para la inversa de la función, en primer lugar, defina $\mathrm{Ruler}(q)$ a ser el exponente de la potencia más alto de los dos que divide $q$. Esta es una función común en la teoría de los números, aunque si se busca se puede encontrar el mismo nombre pero diferentes Thomae de la función en los números reales. El código de Python para $\mathrm{Ruler}()$ se da al final de esta respuesta, aunque en matemática teórica sería definido por la recursividad. Dado que la función, $m$ es fácil de encontrar como $\mathrm{Ruler}(p+1)$ y la parte dura está mostrando una fórmula para $n$. Aquí son tres expresiones de su función inversa con el resultado dado como un par ordenado $(m,n)$.

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

Como un código de Python en línea:

(Ruler(p+1), ((p+1) // 2**Ruler(p+1) - 1) // 2)

Y aquí está mi código de Python para la regla de la función:

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