Función de emparejamiento

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

Cualquier función de emparejamiento puede utilizarse 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.

{\displaystyle \pi

^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}

Generalización

De forma más general, una función de emparejamiento en un conjunto $A$ es una función que asigna cada par de elementos de $A$ en un elemento de $A$ , de tal manera que pares distintos de elementos de $A$ están asociados con elementos distintos de $A$ , ^{[ 5 ]}^{[ a ]} o una biyección de $A^{2}$ a $A$ . ^{[ 6 ]}

En lugar de abstraerse del dominio, la aridad de la función de emparejamiento también puede generalizarse: existe una función de emparejamiento de Cantor generalizada n -aria en $\mathbb {N}$ . ^{[ 3 ]}

Función de emparejamiento de Cantor

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

{\displaystyle \pi

definido por

\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}={\binom {k_{1}+k_{2}+1}{2}}+k_{2}

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

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

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

La afirmación de que esta es la única función de emparejamiento cuadrática se conoce como el teorema de Fueter-Pólya . ^{[ 8 ]} Si esta es la única función de emparejamiento polinómica sigue siendo una cuestión abierta. Cuando aplicamos la función de emparejamiento a $k 1$ y $k 2,$ a menudo denotamos el número resultante como $⟨ k 1, k 2 ⟩$ . ^{[ 9 ]}

Esta definición puede generalizarse inductivamente a la función de tupla de Cantor.

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

para $n>2$ como

\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: $\pi ^{(2)}(k_{1},k_{2}):=\pi (k_{1},k_{2}).$ ^{[ 10 ]}

Otra generalización de la función de emparejamiento de Cantor a una biyección. $\pi ^{(n)}\colon \mathbb {N} ^{n}\to \mathbb {N}$ es proporcionado por el sistema numérico combinatorio :

\pi ^{(n)}(x_{1},\dots ,x_{n})={\binom {x_{1}+\dots +x_{n}+n-1}{n}}+{\binom {x_{1}+\dots +x_{n-1}+n-2}{n-1}}+\dots +{\binom {x_{1}+x_{2}+1}{2}}+{\binom {x_{1}}{1}}.

Invertir la función de emparejamiento de Cantor

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

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

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

w=x+y\!

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

z=t+y\!

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

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

para $w$ como función de $t$ , obtenemos

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

que es una función estrictamente creciente y continua cuando $t$ es un número real no negativo. Dado que

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

lo entendemos

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

y por lo tanto

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

donde $⌊ ⌋$ es la función piso . Entonces, para calcular $x$ e $y$ a partir de $z$ , hacemos lo siguiente:

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

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

y=z-t\!

x=w-y.\!

Dado que la función de emparejamiento de Cantor es invertible, debe ser biyectiva y sobreyectiva . ^{[ 5 ]}

Ejemplos

Para calcular $π (47, 32)$ :

47 + 32 = 79

,

79 + 1 = 80

,

79 \times 80 = 6320

,

6320 \div 2 = 3160

,

3160 + 32 = 3192

,

entonces $π (47, 32) = 3192$ .

Para hallar $x$ e $y$ tales que $π (x, y) = 1432$ :

8 \times 1432 = 11456

,

11456 + 1 = 11457

,

\sqrt 11457 = 107.037

,

107,037 - 1 = 106,037

,

106,037 \div 2 = 53,019

,

⌊53.019⌋ = 53

,

entonces $w = 53$ ;

53 + 1 = 54

,

53 \times 54 = 2862

,

2862 \div 2 = 1431

,

por lo tanto $t = 1431$ ;

1432 - 1431 = 1

,

entonces $y = 1$ ;

53 - 1 = 52

,

entonces $x = 52$ ; por lo tanto $π (52, 1) = 1432$ .

Derivación

La forma gráfica de la función de emparejamiento de Cantor, una progresión diagonal, es un truco estándar para trabajar con secuencias infinitas y numerabilidad . ^{[ b ]} Las reglas algebraicas de esta función diagonal pueden verificar su validez para una serie de polinomios, de los cuales un polinomio cuadrático resultará ser el más simple, utilizando el método de inducción . De hecho, esta misma técnica también puede seguirse para intentar derivar cualquier número de otras funciones para cualquier variedad de esquemas de enumeración del plano.

Una función de emparejamiento generalmente se puede definir inductivamente; 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

\pi (x,y)+1=\pi (x-1,y+1)

.

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

\pi (0,k)+1=\pi (k+1,0)

.

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

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

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

.

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

bk^{2}+ek+1=a(k+1)^{2}+d(k+1)

,

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

b = a

d = 1- a

e = 1 + a

.

Así pues, cada parámetro puede escribirse en términos de $a,$ excepto $c$ , y tenemos una ecuación final, nuestro paso diagonal, que los relacionará:

{\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 para todos los parámetros:

a = 1 / 2 = b = d ​ ​

c = 1

e = 3 / 2 ​ ​

f = 0

.

Por lo tanto

{\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 a través de la derivación que esta satisface todas las condiciones de inducción.

Función de emparejamiento de Cantor desplazada

La siguiente función de emparejamiento: ${\displaystyle \langle i,j\rangle$ , donde $i,j\in \{1,2,3,\dots \}$ . ^{[ 11 ]} es lo mismo que la función de emparejamiento de Cantor, pero desplazada para excluir 0 (es decir, $i=k_{2}+1$ , $j=k_{1}+1$ , y $\langle i,j\rangle -1=\pi (k_{2},k_{1})$ ). ^{[ 7 ]} Se utilizó en el popular libro de texto de informática de Hopcroft y Ullman (1979).

Para números ordinales

Existe una función de emparejamiento "canónica" para números ordinales que es simultáneamente una función de emparejamiento para cada número aleph (es decir, el ordinal inicial de cada número cardinal infinito bien ordenable ). Está inducida por el siguiente buen ordenamiento de pares de números ordinales: ^{[ 12 ]}

(\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}}

La idea básica es que $\max(\alpha ,\beta )$ ⁠ se utiliza como clave de ordenación principal . Por lo tanto, para cada ordinal ⁠ $\alpha$ ⁠ , todos los pares con ambas entradas menores que ⁠ $\alpha$ ⁠ precede a todos los demás pares; en otras palabras, el producto cartesiano ⁠ $\alpha \times \alpha$ ⁠ se asigna a un segmento inicial de este nuevo ordenamiento, con el tipo de ordenamiento del segmento inicial denotado por ⁠ $\gamma (\alpha )$ .

Desde $\gamma (\alpha )$ es una secuencia ordinal estrictamente creciente , $\gamma (\alpha )\geq \alpha$ ⁠ . También es continuo , ya que para el ordinal límite ⁠ $\lambda$ Tenemos $\lambda \times \lambda =\bigcup _{\alpha <\lambda }(\alpha \times \alpha )$ ⁠ . Ahora para todos los números alef ⁠ $\alpha$ , $\gamma (\alpha )=\alpha$ ⁠ se puede demostrar por inducción transfinita :^{[ 13 ]}

Si $\alpha =\omega$ ⁠ , entonces ⁠ $\gamma (\alpha )=\omega$ ⁠ por continuidad ya que ⁠ $\gamma (n)=n^{2}$ es un número natural para cada número natural $n$ .
Si $\alpha >\omega$ ⁠ es un ordinal inicial, entonces ⁠ $\gamma (\alpha )=\alpha$ ⁠ por continuidad ya que ⁠ $\vert \gamma (\delta )\vert =\vert \delta \times \delta \vert =\vert \delta \vert ^{2}=\vert \delta \vert <\vert \alpha \vert$ para todo infinito $\delta <\alpha$ , donde $\vert \delta \vert ^{2}=\vert \delta \vert$ ⁠ se puede demostrar aplicando la hipótesis inductiva al ordinal inicial de ⁠ $\delta$ .

Una implicación importante de esta función de emparejamiento es que $\kappa ^{2}=\kappa$ para todo número cardinal infinito bien ordenable $\kappa$ ⁠ . En particular, en ZFC cada número cardinal es bien ordenable, por lo que ⁠ $\kappa ^{2}=\kappa$ Se cumple para todos los cardinales infinitos . $\kappa$ ⁠ . Por el contrario, la afirmación " ⁠ $\kappa ^{2}=\kappa$ Se cumple para todos los cardinales infinitos . $\kappa$ ⁠ " implica el axioma de elección ; este resultado se conoce como el teorema de Tarski sobre la elección .

Restricción a los números naturales

Restricción de la función de emparejamiento "canónica" para números ordinales al conjunto de números naturales . $\mathbb {N} \equiv \omega$ ⁠ produce una función de emparejamiento diferente de la función de emparejamiento de Cantor, que Szudzik consideraba "más elegante".^{[ 5 ]} La expresión explícita que define esta función de emparejamiento es:

\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:

\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).

Una ventaja de esta función de emparejamiento se manifiesta al usar una función de emparejamiento para representar una estructura similar a un árbol binario , donde el primero $c$ Los números naturales representan distintos tipos de hojas, y $\operatorname {Pair} [x,y]+c$ ⁠ representa un árbol binario con subárboles izquierdo y derecho representados por ⁠ $x$ y $y$ respectivamente. Esta función de emparejamiento garantiza que todos los árboles binarios estén ordenados por profundidad. Un ejemplo concreto de dicha estructura similar a un árbol binario es una expresión de cálculo de combinadores SK .^{[ 5 ]}

Otras funciones de emparejamiento

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

En 1990, Regan propuso la primera función de emparejamiento conocida que se puede calcular en tiempo lineal y con espacio constante (ya que los ejemplos conocidos anteriormente solo se pueden calcular en tiempo lineal si la multiplicación también se puede calcular , lo cual es dudoso). De hecho, tanto esta función de emparejamiento como su inversa se pueden calcular con transductores de estados finitos . 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 ; la primera también se puede calcular fuera de línea con espacio constante. ^{[ 4 ]}

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

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

dónde $i_{0}$ y $j_{0}$ son los bits menos significativos de i y j respectivamente. ^{[ 14 ]}

Citas

Notas

↑ Es decir, una inyección de $A^{2}\rightarrow A$ .
↑ El término "argumento diagonal" se usa a veces para referirse a este tipo de enumeración, pero no estádirectamente relacionado con el argumento diagonal de Cantor .

Notas a pie de página

↑ Paloma :
"Las funciones de emparejamiento surgen naturalmente en la demostración de que las cardinalidades de los racionales $\mathbb {Q}$ y los enteros no negativos $\mathbb {Z} _{\geq 0}$ son lo mismo, es decir, $|\mathbb {Q} |=|\mathbb {Z} _{\geq 0}|=\aleph _{0}$ , originalmente debido a Cantor."
↑ Paloma .
1 2 Lisi 2007 .
1 2 Regan 1992 .
1 2 3 4 5 Szudzik 2006 .
↑ Szudzik 2017 .
1 2 Paloma , Ecuación 8.
↑ Stein (1999 , pp. 448–452) citado en Pigeon .
↑ Rogers, Hartley (1 de enero de 1967). Teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. pág. 64. ISBN 978-0262680523.{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )
↑ Paloma , Ecuaciones 13-7.
↑ Hopcroft y Ullman (1979 , p. 169) citados en ( Pigeon , Ecuaciones 2, 3) .
↑ Jech 2006 , Definición 3.12.
↑ Jech 2006 , Teorema 3.5.
↑ Paloma , ecuación 12.

Referencias

Steven Pigeon. "Función de emparejamiento" . MathWorld .
Lisi, Meri (2007). "Algunas observaciones sobre la función de emparejamiento de Cantor" . Le Matematiche . LXII : 55–65 .
Regan, Kenneth W. (diciembre de 1992). "Funciones de emparejamiento de complejidad mínima" . Journal of Computer and System Sciences . 45 (3): 285– 295. doi : 10.1016/0022-0000(92)90027-G . ISSN 0022-0000 .
Szudzik, Matthew (2006). "Una elegante función de emparejamiento" (PDF) . szudzik.com . Archivado (PDF) del original el 25 de noviembre de 2011. Recuperado el 16 de agosto de 2021 .
Szudzik, Matthew P. (1 de junio de 2017). "La función de emparejamiento fuerte de Rosenberg". arXiv : 1706.04129 [ cs.DM ].
Jech, Thomas (2006). Teoría de conjuntos . Monografías de Springer en matemáticas (Edición del tercer milenio ). Springer-Verlag. doi : 10.1007/3-540-44761-X . ISBN 3-540-44085-2.
Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-02988-X.
Stein, Sherman K. (1999). Matemáticas: El universo creado por el hombre (3.ª ed.). Dover. ISBN 9780486404509.

[6] Es decir, una inyección de $A^{2}\rightarrow A$ .

[12] El término "argumento diagonal" se usa a veces para referirse a este tipo de enumeración, pero no estádirectamente relacionado con el argumento diagonal de Cantor .

[1] Paloma :
"Las funciones de emparejamiento surgen naturalmente en la demostración de que las cardinalidades de los racionales $\mathbb {Q}$ y los enteros no negativos $\mathbb {Z} _{\geq 0}$ son lo mismo, es decir, $|\mathbb {Q} |=|\mathbb {Z} _{\geq 0}|=\aleph _{0}$ , originalmente debido a Cantor."

[FOOTNOTEPigeon-2] Paloma .

[FOOTNOTELisi2007-3] 1 2 Lisi 2007 .

[FOOTNOTERegan1992-4] 1 2 Regan 1992 .

[FOOTNOTESzudzik2006-5] 1 2 3 4 5 Szudzik 2006 .

[FOOTNOTESzudzik2017-7] Szudzik 2017 .

[FOOTNOTEPigeonEquation_8-8] 1 2 Paloma , Ecuación 8.

[9] Stein (1999 , pp. 448–452) citado en Pigeon .

[10] Rogers, Hartley (1 de enero de 1967). Teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. pág. 64. ISBN 978-0262680523.{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )

[FOOTNOTEPigeonEquations_13-7-11] Paloma , Ecuaciones 13-7.

[13] Hopcroft y Ullman (1979 , p. 169) citados en ( Pigeon , Ecuaciones 2, 3) .

[FOOTNOTEJech2006Definition_3.12-14] Jech 2006 , Definición 3.12.

[FOOTNOTEJech2006Theorem_3.5-15] Jech 2006 , Teorema 3.5.

[FOOTNOTEPigeonEquation_12-16] Paloma , ecuación 12.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ b ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]