Biyección simple $\mathbb N_0 \times \mathbb N_0 \to \mathbb N_0$

Question

Estoy buscando un 'simple' bijection $$ \pi \colon \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0, $$

donde "simple" en este contexto significa que debería ser tan fácil como sea posible para definir y debe ser auto-evidente que dicha función es de hecho un bijection. Es una búsqueda de la comodidad - no mínimo de complejidad en cualquier sentido riguroso.

Aquí hay un par de ejemplos que se me ocurrió - ninguno de los que satisfacer ambos requisitos:

1. Deje $\pi(m,n) = c(2^m3^{n+1})$ donde $c \colon \{2^m3^{n+1} \mid m,n \in \mathbb N_0 \}\to \mathbb N_0$ es el fin de isomorfismo (o, de hecho, el colapso de Mostowski) de su dominio bajo los naturales de pedido,
2. Deje $\pi(m,n) = \langle n,m \rangle$ - Gödel de la función de sincronización,
3. Deje $\pi(m,n) = m \oplus n$ - el número que resulta de 'riffling' $m,n$ (donde imaginamos que ambos, $m$ $n$ como en infinidad de mazos de cartas cuyas $i$th elemento tiene una etiqueta con su respectivo $i$th dígitos).
4. ...

Answer 1

$$\pi(n,m)=2^n(2m+1)-1$$

Romper cada número natural a una máxima incluso y un extraño. $-1$ Está allí para obtener $0$ al redil.

Answer 2

En la siguiente imagen (fea, lo siento) muestra el mapa deseado.

Answer 3

No estoy seguro si esto se ajusta, pero es una fórmula aritmética explícita. Se llama el Cantor función de emparejamiento:

$$C(m,n)=\frac{(m+n)(m+n+1)}{2}+m$$

No resulta sin embargo evidente que funciona. Pero usted puede encontrar una prueba aquí.

Answer 4

Asaf estaba interesado en ver una fórmula explícita para user469689 la foto de respuesta. Se puede hacer siguiendo el algoritmo descrito en el teorema 1 en el Cantor de la Función de sincronización (ver aquí), pero sería desordenado con "par/impar" casos ya que la imagen describe un "conectado ruta de acceso'. Así que elegimos un camino ligeramente diferente, pero uno que pone de relieve el mismo 'geometría':

$(0,0) \to$
$(1,0) \to (1,1) \to (0,1) \to $
$(2,0) \to (2,1) \to (2,2) \to (1,2) \to (0,2) \to $
$(3,0) \to (3,1) \to (3,2) \to (3,3) \to (2,3) \to (1,3) \to (0,3) \to $
$\text{etc.} \qquad \text{Figure 1}$

Aquí está la asignación:

$$ \pi(m,n) = \left\{\begin{array}{lr} n^2+2n-m, & \text{for } m \le n\\ m^2+n, & \text{for } m \gt n \end{array}\right\} $$

Como comprobación, se aplican $\pi$ a de la Figura 1:

$\pi(0,0) = 0$
$\pi(1,0)=1 \; \; \pi (1,1)=2 \; \; \pi (0,1)=3$
$\pi(2,0)=4 \; \; \pi (2,1)=5 \; \; \pi (2,2)=6 \; \; \pi (1,2)=7 \; \; \pi (0,2)=8 $
$\pi(3,0)=9 \; \; \pi (3,1)=10 \; \; \pi (3,2)=11 \; \; \pi (3,3)=12 \; \; \pi (2,3) =13 \; \; \pi (1,3) =14 \; \; \pi (0,3)=15 $
$\text{etc.} \qquad \pi\text{(Figure 1)}$

Answer 5

WLOG, estamos buscando un mapeo $\pi \colon \mathbb N^* \times \mathbb N^* \to \mathbb N^*$ donde $\mathbb N^*$ denota el conjunto de los enteros positivos.

Esta idea es sencilla y tiene una forma geométrica/atractivo visual. Usted tiene un infinito de cuadrícula, pero cuando se mira en el finito $n \times n$ inicial a la plaza de los segmentos, razón por la que, para empezar, siempre quiere mapa de pares de coordenadas desde el producto de la diagonal de la siguiente manera:

$\quad \pi(d,d) = d^2$

Ahora usted tiene que 'de relleno', por lo que el $\pi$ mapas de estos $d \times d$ plazas bijectively en el entero del intervalo de $[1,d^2]$.

Intuitivamente, se podría pensar que si usted está en 'cerrar' a la diagonal principal, puede empezar por el cuadrado de la más grande de coordenadas y, a continuación, encontrar una "suave" de ajuste. Los ajustes de conseguir más 'mano dura' a medida que se aleja de la diagonal.

Aquí está la asignación:

$$ \pi(m,n) = \left\{\begin{array}{lr} m^2-2(m-n) , & \text{for } m \ge n\\ n^2-2(n-m)+ 1, & \text{for } m \lt n \end{array}\right\} $$

Así,
$\quad \pi(5,3) = 25 - 4 = 21$
$\quad \pi(1,6) = 36 - 10 + 1 = 27$

He utilizado hojas de cálculo de google para verificar; aquí es visual:

El uso de la inducción en el $n \times n$ plazas, usted puede terminar con esto.

Ejercicio: Demostrar que $\pi$ es bijective.

Nota: El google de la hoja de la imagen está fuera de la $(m,n) = (5,4)$ celular; la entrada correcta es $\pi(5,4) = 23$.