4.4: Funciones y códigos de emparejamiento

Template:MathJaxZach

El método zig-zag de Cantor hace evidente\(\Nat^n\) visualmente la enumerabilidad de. Pero centrémonos en nuestra matriz que representa\(\Nat^2\). Siguiendo la línea en zig-zag en la matriz y contando los lugares, podemos verificar que\(\tuple{1,2}\) esté asociada con el número\(7\). No obstante, sería bueno que pudiéramos computar esto de manera más directa. Es decir, sería bueno tener a mano la inversa de la enumeración en zig-zag,\(g\colon \Nat^2 \to \Nat\), de tal manera que\[g(\tuple{0,0}) = 0, \; g(\tuple{0,1}) = 1, \; g(\tuple{1,0}) = 2, \; \dots, g(\tuple{1,2}) = 7, \; \dots\nonumber\] Esto permitiría calcular exactamente dónde\(\tuple{n, m}\) ocurrirá en nuestra enumeración.

De hecho, podemos definir\(g\) directamente haciendo dos observaciones. Primero: si la\(n\) fila y la columna\(m\) th contienen valor\(v\), entonces la fila\((n+1)\) st y la columna\((m-1)\) st contienen valor\(v + 1\). Segundo: la primera fila de nuestra enumeración consiste en los números triangulares\(0\), empezando por\(1\)\(3\),\(5\),,, etc.\(k\) El número triangular es la suma de los números naturales\(< k\), que se puede computar como\(k(k+1)/2\). Al juntar estas dos observaciones, considera esta función:\[g(n,m) = \frac{(n+m+1)(n+m)}{2} + n\nonumber\] A menudo solo escribimos\(g(n, m)\) más bien eso\(g(\tuple{n, m})\), ya que es más fácil para los ojos. Esto le dice primero determinar el número del\((n+m)^\text{th}\) triángulo, y luego\(n\) restarlo. Y puebla la matriz exactamente de la manera que nos gustaría. Entonces en particular, el par\(\tuple{1, 2}\) es enviado a\(\frac{4 \times 3}{2} + 1 = 7\).

Esta función\(g\) es la inversa de una enumeración de un conjunto de pares. Tales funciones se llaman funciones de emparejamiento.

Definición\(\PageIndex{1}\): Pairing function

Una función\(f\colon A \times B \to \Nat\) es una función de emparejamiento aritmético si\(f\) es inyectiva. También decimos que\(f\) codifica\(A \times B\), y ese\(f(x,y)\) es el código para\(\tuple{x,y}\).

Podemos usar funciones de emparejamiento codificar, por ejemplo, pares de números naturales; o, en otras palabras, podemos representar cada par de elementos usando un solo número. Usando la inversa de la función de emparejamiento, podemos decodificar el número, es decir, averiguar qué par representa.

Problema\(\PageIndex{1}\)

Dar una enumeración del conjunto de todos los números racionales no negativos.

Problema\(\PageIndex{2}\)

Demostrar que\(\Rat\) es contable. Recordemos que cualquier número racional se puede escribir como una fracción\(z/m\) con\(z \in \Int\),\(m \in \Nat^+\).

Problema\(\PageIndex{3}\)

Definir una enumeración de\(\Bin^*\).

Problema\(\PageIndex{4}\)

Recuerda de tu curso de lógica introductoria que cada tabla de verdad posible expresa una función de verdad. En otras palabras, las funciones de verdad son todas funciones de\(\Bin^k \to \Bin\) para algunos\(k\). Demostrar que el conjunto de todas las funciones de verdad es enumerable.

Problema\(\PageIndex{5}\)

Mostrar que el conjunto de todos los subconjuntos finitos de un conjunto contable infinito arbitrario es contable.

Problema\(\PageIndex{6}\)

Un subconjunto de\(\Nat\) se dice que es cofinito si es el complemento de un conjunto finito\(\Nat\); es decir,\(A \subseteq \Nat\) es cofinito iff\(\Nat\setminus A\) es finito. Dejar\(I\) ser el conjunto cuyos elementos son exactamente los subconjuntos finitos y cofinitos de\(\Nat\). Demostrar que\(I\) es contable.

Problema\(\PageIndex{7}\)

Demostrar que la unión contable de conjuntos contables es contable. Es decir, siempre que\(A_1\)\(A_2\),,... son conjuntos, y cada uno\(A_i\) es contable, entonces la unión\(\bigcup_{i=1}^\infty A_i\) de todos ellos también es contable. [NB: ¡esto es duro!]

Problema\(\PageIndex{8}\)

Let\(f \colon A \times B \to \Nat\) Ser una función de emparejamiento arbitrario. Mostrar que la inversa de\(f\) es una enumeración de\(A \times B\).

Problema\(\PageIndex{9}\)

Especifique una función que codifique\(\Nat^3\).