Asombro

Yo los vi. Ahí vivían, en esos edificios tan orgánicos e increíblemente altos. Me invitaron a pasar; no pude de tanto asombro: frente a las edificaciones, permanecí catatónico hasta la muerte.<sup>1

1</sup>Foto de Elena Marini Silvestri

Una forma abstracta del teorema de incompletez1 de Gödel2

Cada uno de los lenguajes $\mathcal{L}$ a los que se les puede aplicar el argumento de Gödel contiene al menos los siguientes elementos:

1. Un conjunto numerable $\mathcal{E}$ cuyos elementos llamaremos las expresiones de $\mathcal{L}$.
2. Un subconjunto $\mathcal{P}$ de $\mathcal{E}$ cuyos elementos llamaremos las proposiciones de $\mathcal{L}$.
3. Un subconjunto $\mathcal{D}$ de $\mathcal{P}$ que llamaremos las proposiciones demostrables de $\mathcal{L}$.
4. Un subconjunto $\mathcal{R}$ de $\mathcal{P}$ que llamaremos las proposiciones refutables de $\mathcal{L}$.
5. Un conjunto $\mathcal{H}$ de expresiones cuyos elementos llamaremos los predicados de $\mathcal{L}$. [Estos fueron llamados nombres de clase en la introducción de Gödel. Informalmente, se está pensando que cada predicado H es el nombre de un conjunto de números naturales].
6. Una función Φ que asigna a cada expresión E y a cada número natural n una expresión E(n). Se requiere que la función cumpla la condición de que para cada predicado H y cada número natural n, la expresión H(n) sea una proposición. [Informalmente, la proposición H(n) expresa la proposición de que el número n pertenece al conjunto nombrado por H].
   
   En la primera demostración de incompletez que daremos para un sistema particular $\mathcal{L}$, usaremos un concepto básico precisado por Alfred Tarski [1936] —a saber, la noción de proposición verdadera (definida de manera muy diferente que la de proposición demostrable de un sistema)—.
7. Un conjunto $\mathcal{V}$ de proposiciones cuyos elementos llamaremos las proposiciones verdaderas de $\mathcal{L}$.

Esto concluye nuestra descripción abstracta del tipo de sistemas que estudiaremos en los siguientes capítulos.

Expresabilidad en $\mathcal{L}$. La noción de expresabilidad en $\mathcal{L}$, la cual estamos por definir, se relaciona con el conjunto de verdad $\mathcal{V}$ pero no con los conjuntos $\mathcal{D}$ o $\mathcal{R}$.

     La palabra número querrá decir número natural para el resto de este volumen. Diremos que un predicado H es verdadero para un número n o que n satisface H si H(n) es una proposición verdadera (es decir, si es un elemento de $\mathcal{V}$). Con el conjunto expresado por H, querremos decir el conjunto de todos los n que satisfacen H. Así, para cualquier conjunto A de números, H expresa A si y sólo si para todo número n

H(n)∈$\mathcal{V}$ ↔ n∈A.

Definición. Un conjunto A se dice que es expresable o nombrable en $\mathcal{L}$ si A es expresado por algún predicado de $\mathcal{L}$.

     Puesto que sólo hay una cantidad numerable de expresiones de $\mathcal{L}$, sólo hay una cantidad finita o numerable de predicados de $\mathcal{L}$. Pero por el bien conocido teorema de Cantor, hay una cantidad no-numerable de conjuntos de números naturales. Por lo tanto, no todo conjunto de números es expresable en $\mathcal{L}$.

Definición. Se dice que el sistema $\mathcal{L}$ es correcto si toda proposición demostrable es verdadera y toda proposición refutable es falsa (no verdadera). Esto significa que $\mathcal{D}$ es un subconjunto de $\mathcal{V}$ y que $\mathcal{R}$ es disjunto de $\mathcal{V}$. Ahora estamos interesados en las condiciones suficientes, si $\mathcal{L}$ es correcto, para que $\mathcal{L}$ contenga una proposicón verdadera no demostrable en $\mathcal{L}$.

Numeración de Gödel y Diagonalización. Sea g una función uno-a-uno que asigna a cada expresión E un número natural g(E), el cual llamaremos el número de Gödel de E. La función g será constante para el resto de este capítulo. [En los sistemas concretos que estudiaremos en capítulos posteriores, se dará una numeración de Gödel específica. Sin embargo, nuestro presente tratamiento puramente abstracto se puede aplicar a una numeración de Gödel arbitraria]. Será conveniente técnicamente suponer que todo número es el número de Gödel de una expresión. [La numeración original de Gödel no tenía esta propiedad, pero la numeración de Gödel que usaremos en capítulos posteriores sí la tendrá. Sin embargo, los resultados de este capítulo se pueden demostras, con modificaciones menores, sin esta restricción (Vea Ex. 5)]. Suponiendo que todo número es el número de Gödel de una expresión única, hagamos que E_n sea la expresión cuyo número de Gödel es n. Así, g(E_n)=n.

     Con la diagonalización de E_n, querremos decir la expresión E_n(n). Si E_n es un predicado, entonces su diagonalización es, por supuesto, una proposición; esta proposición es verdadera si y sólo si el predicado E_n es satisfecho por su propio número de Gödel n. [Escribimos “ssi” para querer decir si y sólo si; usamos “↔” de igual manera].
     Para cualquier n, sea d(n) el número de Gödel de E_n(n). La función d(x) juega un papel clave en todo lo que sigue; la llamaremos la función diagonal del sistema.
     Usaremos el término conjunto de números para querer decir conjunto de números naturales. Para cualquier conjunto de números A, con A^∗ querremos decir el conjunto de todos los números n tales que d(n)∈A. Así, para cualquier número n, la equivalencia

n∈A^∗ ↔ d(n)∈A

se cumple por definición de A^∗. [A^∗ también podría escribirse como d^-1(A), ya que es la imagen inversa de A bajo la función diagonal d(x)].

Una Forma Abstracta del Teorema de Gödel. Sea D el conjunto de los números de Gödel de todas las proposiciones demostrables. Para cualquier conjunto de números A, con su complemento ∼A, queremos decir el complemento de A respecto del conjunto de números naturales N —∼A es el conjunto de los números naturales que no están en A—.

Teorema (GT) —por Gödel, con matices de Tarski—. Si el conjunto (∼D)^∗ es expresable en $\mathcal{L}$ y $\mathcal{L}$ es correcto, entonces hay una proposicón verdadera de $\mathcal{L}$ no demostrable en $\mathcal{L}$.

Demostración. Supóngase que $\mathcal{L}$ y que (∼D)^∗ es expresable en $\mathcal{L}$. Sea H un predicado que expresa a (∼D)^∗ en $\mathcal{L}$, y sea h el número de Gödel de H. Sea G la diagonalización de H (es decir, la proposición H(h)). Mostraremos que G es verdadera pero no demostrable en $\mathcal{L}$.
     Puesto que H expresa a (∼D)^∗ en $\mathcal{L}$, para cualquier número n, H(n) es verdadera ↔ n∈(∼D)^∗. Ya que esta equivalencia se cumple para todo n, se cumple en particular para n el número h. Así que tomamos h como n (y esta es la parte del argumento llamada diagonalización) y tenemos la equivalencia H(h) es verdadera ↔ h∈(∼D)^∗. Ahora,

h∈(∼D)^∗ ↔ d(h)∈∼D ↔ d(h)∉D.

Pero d(h) es el número de Gödel de H(h) (puesto que h es el número de Gödel de H), así que d(h)∈D ↔ H(h) es demostrable en $\mathcal{L}$ y d(h)∉D ↔ H(h) no es demostrable en $\mathcal{L}$. Así que tenemos

1. Esto significa o que H(h) es verdadera y no demostrable en $\mathcal{L}$ o que es falsa pero demostrable en $\mathcal{L}$. La última alternativa viola la hipótesis de que $\mathcal{L}$ es correcto. De aquí, se tiene que tener que H(h) es verdadera pero no demostrable en $\mathcal{L}$.

     Cuando se trate de los lenguajes particulares $\mathcal{L}$ que estudiaremos, verificaremos la hipótesis de que (∼D)^∗ es expresable en $\mathcal{L}$ al verificar separadamente las siguientes tres condiciones.

G₁: para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto A^∗ es expresable en $\mathcal{L}$.
G₂: para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto ∼A es expresable en $\mathcal{L}$.
G₃: el conjunto D es expresable en $\mathcal{L}$.

     Las condiciones G₁ y G₂ implican, por supuesto, que para cualquier conjunto A expresable en $\mathcal{L}$, el conjunto (∼A)^∗ es expresable en $\mathcal{L}$. De aquí, si D es expresable en $\mathcal{L}$, entonces también lo es (∼D)^∗.
     Podríamos notar que la verificación de G₁ resultará ser relativamente simple; la verificación de G₂ será completamente trivial; pero la verificación de G₃ resultará ser extremadamente elaborada.



¹La palabra que seguiría la norma sería ‘incompleción’, como bien nos pueden sugerir ‘discreción’ para ‘discreto’, ‘concreción’ para ‘concreto’, ‘abstracción’ para ‘abstracto’; sin embargo, a la mayoría de los matemáticos de habla hispana no les interesa mucho la norma del idioma español y, en consecuencia, se ponen en uso barbarismos horribles como ‘incompletez’.

²Esta es una traducción libre de un fragmento del libro Gödel's Incompleteness Theorems de Raymond Merrill Smullyan y corresponde precisamente a una generalización del teorema de incompletez de Gödel. La publico porque me parece importante que dicha generalización se conozca.

La música, el otro

La música hace pequeñas olas en mi interior.
Los sonidos con apariencia articulada me hacen creer que hay otro.

Miré esa estrella, esa luz verde e intermitente. Primero hizo olas, y luego música. Bailé toda la noche.
Ese pájaro emitió su canto. Hay otros. Hablé con él largamente, y con los otros también.


© Enrique Ruiz Hernández