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 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.
Definición
Una función de emparejamiento es una biyección computable
Función de emparejamiento de Cantor
La función de emparejamiento de Cantor es una función de emparejamiento recursiva primitiva
definido por
También es estrictamente monótono con cada argumento, es decir, , Si , luego ; de manera similar, si, luego .
La afirmación de que esta es la única función de emparejamiento cuadrático se conoce como teorema de Fueter-Pólya . Si esta es la única función de emparejamiento polinomial sigue siendo una pregunta abierta. Cuando aplicamos la función de emparejamiento para k 1 y k 2 que a menudo indican el número resultante como ⟨ k 1 , k 2 ⟩ .
Esta definición se puede generalizar inductivamente a la función tupla de Cantor
por como
con el caso base definido anteriormente para un par:
Invertir la función de emparejamiento de Cantor
Dejar ser un número natural arbitrario. Mostraremos que existen valores únicos tal que
y por tanto, π es invertible. Es útil definir algunos valores intermedios en el cálculo:
donde t es el número de triángulo de w . Si resolvemos la ecuación cuadrática
para w en función de t , obtenemos
que es una función estrictamente creciente y continua cuando t es real no negativo. Desde
lo conseguimos
y por lo tanto
donde ⌊ ⌋ es la función de piso . Así que para calcular x e y de z , que hacemos:
Dado que la función de emparejamiento de Cantor es invertible, debe ser uno a uno y sobre .
Ejemplos de
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 x e y tales que π ( x , y ) = 1432 :
- 8 × 1.432 = 11.456 ,
- 11456 + 1 = 11457 ,
- √ 11.457 = 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 .
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 contabilidad . [a] Las reglas algebraicas de esta función en forma de diagonal pueden verificar su validez para un rango de polinomios, de los cuales una cuadrática resultará ser la más simple, usando 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.
Por lo general, una función de emparejamiento se puede definir inductivamente, es decir, dado el par n , ¿cuál es el par ( n +1) ? La forma en que la función de Cantor progresa diagonalmente a través del plano se puede expresar como
- .
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 restablece al eje x para reanudar su progresión diagonal un paso más allá, o algebraicamente:
- .
También necesitamos definir el punto de partida, cuál será el paso inicial en nuestro método de inducción: π (0, 0) = 0 .
Suponga que hay un polinomio cuadrático bidimensional que puede ajustarse a estas condiciones (si no las hubiera, se podría repetir simplemente probando un polinomio de mayor grado). La forma general es entonces
- .
Conecte nuestras condiciones iniciales y de contorno para obtener f = 0 y:
- ,
para que podamos hacer coincidir nuestros k términos para obtener
- b = a
- d = 1- una
- e = 1+ a .
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á:
Ampliar y combinar términos de nuevo para obtener valores fijos para una y C , y por lo tanto todos los parámetros:
- a =1/2= b = d
- c = 1
- e = 3/2
- f = 0 .
Por lo tanto
es la función de emparejamiento de Cantor, y también demostramos mediante la derivación que satisface todas las condiciones de inducción.
Notas
- ^ El término "argumento diagonal" se utiliza a veces para referirse a este tipo de enumeración, pero se no directamente relacionado con el argumento diagonal de Cantor .
Referencias
enlaces externos
- Steven Pigeon. "Función de emparejamiento" . MathWorld .
- Una elegante función de emparejamiento