4.5: Una función de emparejamiento alternativa

Template:MathJaxZach

Hay otras enumeraciones de\(\Nat^2\) eso que hacen que sea más fácil averiguar cuáles son sus inversas. Aquí hay uno. En lugar de visualizar la enumeración en una matriz, comience con la lista de enteros positivos asociados con (inicialmente) espacios vacíos. Imagínese llenar estos espacios sucesivamente con pares de la\(\tuple{n,m}\) siguiente manera. Comenzando con los pares que tienen\(0\) en primer lugar (es decir, pares\(\tuple{0,m}\)), poner el primero (i.e.,\(\tuple{0,0}\)) en el primer lugar vacío, luego omita un espacio vacío, coloca el segundo (i.e.,\(\tuple{0,2}\)) en el siguiente lugar vacío, salta uno de nuevo, y así cuarto. El comienzo (incompleto) de nuestra enumeración ahora se ve así\[\small \begin{array}{@{}c c c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,1} & & \tuple{0,2} & & \tuple{0,3} & & \tuple{0,4} & & \tuple{0,5} & & \dots \\ \end{array}\nonumber\] Repita esto con pares\(\tuple{1,m}\) para los lugares que aún permanecen vacíos, saltándose de nuevo cada otro lugar vacío:\[\small \begin{array}{@{}c c c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & & \tuple{0,2} & \tuple{1,1} & \tuple{0,3} & & \tuple{0,4} & \tuple{1,2} & \dots \\ \end{array}\nonumber\] Ingresa pares\(\tuple{2,m}\),\(\tuple{2,m}\), etc., de la misma manera. Nuestra enumeración completada comienza así:\[\small \begin{array}{@{}cc c c c c c c c c c@{}} \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 & \mathbf 9 & \mathbf{10} & \dots \\ \\ \tuple{0,0} & \tuple{1,0} & \tuple{0,1} & \tuple{2,0} & \tuple{0,2} & \tuple{1,1} & \tuple{0,3} & \tuple{3,0} & \tuple{0,4} & \tuple{1,2} & \dots \\ \end{array}\nonumber\] Si numeramos las celdas en la matriz anterior de acuerdo con esta enumeración, no encontraremos una línea ordenada en zig-zag, sino esta disposición:\[\begin{array}{ c | c | c | c | c | c | c | c } & \mathbf 0 & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \dots \\ \hline \mathbf 0 & 1 & 3 & 5 & 7 & 9 & 11 & \dots \\ \hline \mathbf 1 & 2 & 6 & 10 & 14 & 18 & \dots & \dots \\ \hline \mathbf 2 & 4 & 12 & 20 & 28 & \dots & \dots & \dots \\ \hline \mathbf 3 & 8 & 24 & 40 & \dots & \dots & \dots & \dots \\ \hline \mathbf 4 & 16 & 48 & \dots & \dots & \dots & \dots & \dots \\ \hline \mathbf 5 & 32 & \dots & \dots & \dots & \dots & \dots & \dots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}\nonumber\] Podemos ver que los pares en fila\(0\) están en el impar lugares numerados de nuestra enumeración, es decir, par\(\tuple{0,m}\) está en su lugar\(2m+1\); pares en la segunda fila\(\tuple{1,m}\),, están en lugares cuyo número es el doble de un número impar, específicamente,\(2 \cdot (2m+1)\); pares en la tercera fila,\(\tuple{2,m}\), están en lugares cuyo número es cuatro veces un número impar,\(4 \cdot (2m+1)\); y así sucesivamente. Los factores de\((2m+1)\) para cada fila,\(1\),\(2\),\(4\),\(8\),..., son exactamente los poderes de\(2\):\(1= 2^0\),\(2 = 2^1\),\(4 = 2^2\), \(8 = 2^3\),... De hecho, el exponente relevante es siempre el primer miembro de la pareja en cuestión. Así, para par\(\tuple{n,m}\) el factor es\(2^n\). Esto nos da la fórmula general:\(2^n \cdot (2m+1)\). Sin embargo, se trata de un mapeo de pares a enteros positivos, es decir,\(\tuple{0,0}\) tiene posición\(1\). Si queremos comenzar en posición\(0\) debemos restar\(1\) del resultado. Esto nos da:

Ejemplo\(\PageIndex{1}\)

La función\(h\colon \Nat^2 \to \Nat\) dada por\[h(n,m) = 2^n (2m+1) - 1\nonumber\] es una función de emparejamiento para el conjunto de pares de números naturales\(\Nat^2\).

En consecuencia, en nuestra segunda enumeración de\(\Nat^2\), el par\(\tuple{0,0}\) tiene código\(h(0,0) = 2^0(2\cdot 0+1) - 1 = 0\);\(\tuple{1,2}\) tiene código\(2^{1} \cdot (2 \cdot 2 + 1) - 1 = 2 \cdot 5 - 1 = 9\);\(\tuple{2,6}\) tiene código\(2^{2} \cdot (2 \cdot 6 + 1) - 1 = 51\).

En ocasiones basta con codificar pares de números naturales\(\Nat^2\) sin requerir que la codificación sea suryectiva. Tales codificaciones tienen inversos que son sólo funciones parciales.

Ejemplo\(\PageIndex{2}\)

La función\(j\colon \Nat^2 \to \Nat^+\) dada por\[j(n,m) = 2^n3^m\nonumber\] es una función de inyección\(\Nat^2 \to \Nat\).