Función de emparejamiento

Función que asigna de forma única dos números a un solo número

En matemáticas , una función de emparejamiento es un proceso para codificar de forma única dos números naturales en un único número natural. ^[1]

Cualquier función de emparejamiento se puede utilizar en la teoría de conjuntos para demostrar que los números enteros y racionales tienen la misma cardinalidad que los números naturales. ^[1]

Definición

Una función de emparejamiento es una biyección ^{[ se necesita verificación ]}

${\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}$^[1]

De manera más general, una función de emparejamiento en un conjunto A es una función que asigna cada par de elementos de A a un elemento de A , de modo que dos pares cualesquiera de elementos de A estén asociados con diferentes elementos de A, ^[2] o una biyección. de a A.​ ^[3] ${\displaystyle A^{2}}$

Función de emparejamiento de Hopcroft y Ullman

Hopcroft y Ullman (1979) definen la siguiente función de emparejamiento: , donde . ^[1] Esto es lo mismo que la función de emparejamiento de Cantor a continuación, desplazada para excluir 0 (es decir, , y ). ${\displaystyle \langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i}$ ${\displaystyle i,j\in \{1,2,3,\dots \}}$ ${\displaystyle i=k_{2}+1}$ ${\displaystyle j=k_{1}+1}$ ${\displaystyle \langle i,j\rangle -1=\pi (k_{2},k_{1})}$

Función de emparejamiento de Cantor

La función de emparejamiento de Cantor asigna un número natural a cada par de números naturales

Gráfica de la función de emparejamiento de Cantor

La función de emparejamiento de Cantor es una función de emparejamiento recursiva primitiva.

${\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} }$

definido por

${\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}}$^{[1] [ se necesita verificación ]}

dónde . ^[1] ${\displaystyle k_{1},k_{2}\in \{0,1,2,3,\dots \}}$

También se puede expresar como . ^[2] ${\displaystyle \pi (x,y):={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}}$

También es estrictamente monótono con respecto a cada argumento, es decir, para todos , si , entonces ; de manera similar, si , entonces . ^{[ cita necesaria ]} ${\displaystyle k_{1},k_{1}',k_{2},k_{2}'\in \mathbb {N} }$ ${\displaystyle k_{1}<k_{1}'}$ ${\displaystyle \pi (k_{1},k_{2})<\pi (k_{1}',k_{2})}$ ${\displaystyle k_{2}<k_{2}'}$ ${\displaystyle \pi (k_{1},k_{2})<\pi (k_{1},k_{2}')}$

La afirmación de que ésta es la única función de emparejamiento cuadrático se conoce como teorema de Fueter-Pólya . ^{[1] [ se necesita verificación ]} Si esta es la única función de emparejamiento polinómico sigue siendo una cuestión abierta. Cuando aplicamos la función de emparejamiento a k ₁ y k _2, a menudo denotamos el número resultante como ⟨ k ₁ , k ₂ ⟩ . ^{[ cita necesaria ]}

Esta definición se puede generalizar inductivamente a la función tupla de Cantor ^{[ cita necesaria ]}

${\displaystyle \pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N} }$

por como ${\displaystyle n>2}$

${\displaystyle \pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})}$

con el caso base definido anteriormente para un par: ^[1] ${\displaystyle \pi ^{(2)}(k_{1},k_{2}):=\pi (k_{1},k_{2}).}$

Invertir la función de emparejamiento de Cantor

Sea un número natural arbitrario. Demostraremos que existen valores únicos tales que ${\displaystyle z\in \mathbb {N} }$ ${\displaystyle x,y\in \mathbb {N} }$

${\displaystyle z=\pi (x,y)={\frac {(x+y+1)(x+y)}{2}}+y}$

y por tanto que la función π(x, y) es invertible. Es útil definir algunos valores intermedios en el cálculo:

${\displaystyle w=x+y\!}$

${\displaystyle t={\frac {1}{2}}w(w+1)={\frac {w^{2}+w}{2}}}$

${\displaystyle z=t+y\!}$

donde t es el número triangular de w . Si resolvemos la ecuación cuadrática

${\displaystyle w^{2}+w-2t=0\!}$

para w en función de t , obtenemos

${\displaystyle w={\frac {{\sqrt {8t+1}}-1}{2}}}$

que es una función estrictamente creciente y continua cuando t es real no negativo. Desde

${\displaystyle t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}}$

entendemos eso

${\displaystyle w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1}$

y por lo tanto

${\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .}$

donde ⌊ ⌋ es la función suelo . Entonces , para calcular xey a partir de z , hacemos:

${\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor }$

${\displaystyle t={\frac {w^{2}+w}{2}}}$

${\displaystyle y=z-t\!}$

${\displaystyle x=w-y.\!}$

Dado que la función de emparejamiento de Cantor es invertible, debe ser uno a uno y sobre . ^{[2] [ se necesitan citas adicionales ]}

Ejemplos

Para calcular π (47, 32) :

47 + 32 = 79 ,

79 + 1 = 80 ,

79 × 80 = 6320 ,

6320 ÷ 2 = 3160 ,

3160 + 32 = 3192 ,

entonces π (47, 32) = 3192 .

Para encontrar xey tales que π ( x , y ) = 1432 :

8 × 1432 = 11456 ,

11456 + 1 = 11457 ,

√ 11457 = 107,037 ,

107,037 - 1 = 106,037 ,

106,037 ÷ 2 = 53,019 ,

⌊53.019⌋ = 53 ,

entonces w = 53 ;

53 + 1 = 54 ,

53 × 54 = 2862 ,

2862 ÷ 2 = 1431 ,

entonces t = 1431 ;

1432 − 1431 = 1 ,

entonces y = 1 ;

53 - 1 = 52 ,

entonces x = 52 ; por tanto π (52, 1) = 1432 . ^{[ cita necesaria ]}

Derivación

A menudo se utiliza una función "serpiente" que se incrementa diagonalmente, basada en los mismos principios que la función de emparejamiento de Cantor, para demostrar la contabilidad de los números racionales.

La forma gráfica de la función de emparejamiento de Cantor, una progresión diagonal, es un truco estándar al trabajar con secuencias infinitas y contabilidad . ^[a] Las reglas algebraicas de esta función de forma diagonal pueden verificar su validez para un rango de polinomios, de los cuales una cuadrática resultará ser la más simple, utilizando el método de inducción . De hecho, esta misma técnica también se puede seguir para intentar derivar cualquier número de otras funciones para cualquier variedad de esquemas para enumerar el plano.

Una función de emparejamiento generalmente se puede definir de manera inductiva, es decir, dado el n- ésimo par, ¿cuál es el ( n +1) -ésimo par? La forma en que la función de Cantor progresa diagonalmente a través del plano se puede expresar como

${\displaystyle \pi (x,y)+1=\pi (x-1,y+1)}$.

La función también debe definir qué hacer cuando llega a los límites del primer cuadrante: la función de emparejamiento de Cantor se reinicia en el eje x para reanudar su progresión diagonal un paso más allá, o algebraicamente:

${\displaystyle \pi (0,k)+1=\pi (k+1,0)}$.

También necesitamos definir el punto de partida, cuál será el paso inicial en nuestro método de inducción: π (0, 0) = 0 .

Supongamos que existe un polinomio cuadrático bidimensional que puede cumplir estas condiciones (si no lo hubiera, se podría repetir probando con un polinomio de mayor grado). La forma general es entonces

${\displaystyle \pi (x,y)=ax^{2}+by^{2}+cxy+dx+ey+f}$.

Sustituya nuestras condiciones iniciales y de contorno para obtener f = 0 y:

${\displaystyle bk^{2}+ek+1=a(k+1)^{2}+d(k+1)}$,

para que podamos hacer coincidir nuestros k términos para obtener

segundo = un

re = 1- un

mi = 1+ un .

Entonces, cada parámetro se puede escribir en términos de a excepto c , y tenemos una ecuación final, nuestro paso diagonal, que los relacionará:

${\displaystyle {\begin{aligned}\pi (x,y)+1&=a(x^{2}+y^{2})+cxy+(1-a)x+(1+a)y+1\\&=a((x-1)^{2}+(y+1)^{2})+c(x-1)(y+1)+(1-a)(x-1)+(1+a)(y+1).\end{aligned}}}$

Expanda y haga coincidir los términos nuevamente para obtener valores fijos para a y c y, por lo tanto, todos los parámetros:

un =1/2= b = d

c = 1

mi =3/2

f = 0 .

Por lo tanto

${\displaystyle {\begin{aligned}\pi (x,y)&={\frac {1}{2}}(x^{2}+y^{2})+xy+{\frac {1}{2}}x+{\frac {3}{2}}y\\&={\frac {1}{2}}(x+y)(x+y+1)+y,\end{aligned}}}$

es la función de emparejamiento de Cantor, y también demostramos mediante la derivación que satisface todas las condiciones de inducción. ^{[ cita necesaria ]}

Otras funciones de emparejamiento

La función es una función de emparejamiento. ${\displaystyle P_{2}(x,y):=2^{x}(2y+1)-1}$

En 1990, Regan propuso la primera función de emparejamiento conocida que es computable en tiempo lineal y con espacio constante (ya que los ejemplos previamente conocidos sólo se pueden calcular en tiempo lineal si y sólo la multiplicación puede serlo , lo cual es dudoso). ^[4] De hecho, tanto esta función de emparejamiento como su inversa se pueden calcular con transductores de estado finito que funcionan en tiempo real. ^{[4] [ se necesita aclaración ]} En el mismo artículo, el autor propuso dos funciones de emparejamiento monótonas más que se pueden calcular en línea en tiempo lineal y con espacio logarítmico ; el primero también se puede calcular fuera de línea con espacio cero. ^{[4] [ se necesita aclaración ]}

En 2001, Pigeon propuso una función de emparejamiento basada en entrelazado de bits , definida de forma recursiva como:

${\displaystyle \langle i,j\rangle _{P}={\begin{cases}T&{\text{if}}\ i=j=0;\\\langle \lfloor i/2\rfloor ,\lfloor j/2\rfloor \rangle _{P}:i_{0}:j_{0}&{\text{otherwise,}}\end{cases}}}$

donde y son los bits menos significativos de i y j respectivamente. ^{[1] [ se necesita verificación ]} ${\displaystyle i_{0}}$ ${\displaystyle j_{0}}$

En 2006, Szudzik propuso una función de emparejamiento "más elegante" definida por la expresión:

${\displaystyle \operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x<y,\\x^{2}+x+y&{\text{if}}\ x\geq y.\\\end{cases}}}$

Que se puede desemparejar usando la expresión:

${\displaystyle \operatorname {ElegantUnpair} [z]:={\begin{cases}\left\{z-\lfloor {\sqrt {z}}\rfloor ^{2},\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}<\lfloor {\sqrt {z}}\rfloor ,\\\left\{\lfloor {\sqrt {z}}\rfloor ,z-\lfloor {\sqrt {z}}\rfloor ^{2}-\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}\geq \lfloor {\sqrt {z}}\rfloor .\end{cases}}}$

(Cualitativamente, asigna números consecutivos a pares a lo largo de los bordes de los cuadrados). Esta función de emparejamiento ordena las expresiones de cálculo del combinador SK por profundidad. ^{[2] [ se necesita aclaración ]} Este método es la mera aplicación de la idea, que se encuentra en la mayoría de los libros de texto sobre teoría de conjuntos, ^[5] utilizada para establecer cualquier cardinal infinito en ZFC . Definir en la relación binaria. ${\displaystyle \mathbb {N} }$ ${\displaystyle \kappa ^{2}=\kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \times \kappa }$

${\displaystyle (\alpha ,\beta )\preccurlyeq (\gamma ,\delta ){\text{ if either }}{\begin{cases}(\alpha ,\beta )=(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )<\max(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha <\gamma ,{\text{ or}}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha =\gamma \ {\text{and}}\ \beta <\delta .\end{cases}}}$

${\displaystyle \preccurlyeq }$Luego se demuestra que tiene un buen orden tal que cada elemento tiene predecesores, lo que implica que . De ello se deduce que es isomorfa y la función de emparejamiento anterior no es más que la enumeración de pares de enteros en orden creciente. (Ver también Charla: Teorema de Tarski sobre la elección#Prueba de lo contrario ). ${\displaystyle {}<\kappa }$ ${\displaystyle \kappa ^{2}=\kappa }$ ${\displaystyle (\mathbb {N} \times \mathbb {N} ,\preccurlyeq )}$ ${\displaystyle (\mathbb {N} ,\leqslant )}$

Notas

1. no está directamente relacionado con el argumento diagonal de Cantor . ^{[ cita necesaria ]}

Referencias

1. Steven Paloma. "Función de emparejamiento". MundoMatemático . Consultado el 16 de agosto de 2021 .
2. Szudzik, Mateo (2006). "Una función de emparejamiento elegante" (PDF) . szudzik.com . Archivado (PDF) desde el original el 25 de noviembre de 2011 . Consultado el 16 de agosto de 2021 .
3. Szudzik, Matthew P. (1 de junio de 2017). "La función de emparejamiento Rosenberg-Strong". arXiv : 1706.04129 [cs.DM].
4. Regan, Kenneth W. (1 de diciembre de 1992). "Funciones de emparejamiento de mínima complejidad". Revista de Ciencias de la Computación y de Sistemas . 45 (3): 285–295. doi : 10.1016/0022-0000(92)90027-G . ISSN  0022-0000.
5. Véase, por ejemplo, Thomas, Jech (2006). Teoría de conjuntos: la edición del tercer milenio . Monografías de Springer en Matemáticas. Springer-Verlag. pag. 30.doi : 10.1007 /3-540-44761-X. ISBN 3-540-44085-2.