Función invertible$\mathbb{N} \times \mathbb{N} \to \mathbb{N}$

Question

Estoy tratando de averiguar si es posible crear una función invertible a partir de$\mathbb{N} \times \mathbb{N} \to \mathbb{N}$?

¿Me puedes ayudar? ¿Donde debería empezar? ¿Está relacionado con la función de emparejamiento de Cantor?

Answer 1

La siguiente función, utilizada para producir un orden total en$\mathbf N^*$ diferente del orden habitual, es una biyección: \begin{align*} \mathbf N\times\mathbf N&\longrightarrow\mathbf N^*\\ (n,p)&\longmapsto 2^n(2p+1) \end {align *} Por lo tanto, la función$$f(n,p)= 2^n(2p+1)-1$ $ satisface los requisitos.

Answer 2

El Cantor función de emparejamiento es exactamente un ejemplo de una función invertible $\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$, por lo que necesitará sólo muestran que es invertible. La página de wikipedia sobre la función de Cantor emparejamiento proporciona tan una inversa, pero es probablemente un buen ejercicio para ver si usted puede encontrar usted mismo primero.

(Que se dice, hay muchas funciones invertible de $\mathbb{N}\times \mathbb{N}$ a $\mathbb{N}$.)

Answer 3

piense en lo siguiente, deje$f$ map$(0,0) \to 0, (0,1)\to 1, (1,0) \to 2, (2,0) \to 3, (1,1) \to 4$ etc. Continúe siguiendo estos caminos diagonales hasta cubrir el$\mathbb{N}^2$% completo. $f$ es una biyección ...