Gödel y Turing (Parte 11)

(A la parte 10 - A la parte 12)

¿Qué es lo que no dice el Teorema de Gödel?

Suele decirse en los textos de divulgación que el Teorema de Gödel (1) asegura que todo sistema axiomático que sea suficientemente amplio como para contener a la Aritmética (2) tiene necesariamente enunciados indecidibles, es decir, enunciados que no pueden ser demostrados ni refutados a partir de los axiomas (3).

Pues bien, debo decirles que esto que los textos de divulgación dicen casi unánimemente y que, a causa de ello, ha siso repetido tantas veces por aquí y por allí, no es verdad. El Teorema de Gödel no afirma lo que dijimos más arriba. Más aún, no solamente el Teorema de Gödel no afirma eso, sino que, además, lo que dijimos en el párrafo anterior es, de hecho, falso. Es decir, no es cierto que todo sistema axiomático lo suficientemente amplio como para contener a la Aritmética, deba tener necesariamente enunciados indecidibles.

Tomemos por ejemplo el siguiente sistema de axiomas para la suma y producto de números enteros positivos (4) y que, de hecho, contiene a la Aritmética, en el sentido de que permite demostrar todas las propiedades básicas de la suma y el producto.

En estos axiomas se mencionan como elementos primitivos (5) al conjunto N de todos los enteros positivos, al número 1, a la función Sig(x) (que a cada número x le hace corresponder su siguiente en la secuencia de los números naturales) y a las operaciones de suma y producto:

Ax.1: Si x = y entonces Sig(x) = Sig(y).
Ax.2: Si Sig(x) = Sig(y) entonces x = y.
Ax.3: Para ningún x sucede que 1 = Sig(x).
Ax.4: Para todo x vale que x + 1 = Sig(x).
Ax.5: Para todo x e y vale que x + Sig(y) = Sig(x + y).
Ax.6: Para todo x vale que x.1 = x.
Ax.7: Para todo x e y vale que x.Sig(y) = x.y + Sig(y).
Ax.8: Si A es un conjunto tal que 1 es elemento de A y tal que para todo x vale que si x es elemento de A entonces Sig(x) también lo es, entonces A = N.

Pues bien, puede demostrarse (6) que todo afirmación aritmética puede, o bien probarse, o bien refutarse a partir de estos axiomas. No hay en este sistema axiomático afirmaciones indecidibles. Este ejemplo muestra que aquello que, según los textos de divulgación afirma el Teorema de Gödel, es falso.

¿Qué dice entonces realmente el Teorema de Gödel? Recordemos que en la primera parte (hace ya mucho tiempo) dijimos que el Teorema de Gödel afirma que en cualquier sistema axiomático que contenga a la Aritmética y que respete ciertas restricciones formales (que en aquél momento no especifiqué) existen necesariamente enunciados indecidibles. Es evidente entonces que los axiomas indicado más arriba no respetan esas restricciones formales ¿Cuáles son entonces esas restricciones y cuál es su interés? Eso es precisamente lo que empezaremos a estudiar en la próxima entrada.

Notas:

(1) Con más precisión el Primer Teorema de Incompletitud de Gödel.

(2) La Aritmética, o Teoría Elemental de Números, es la teoría que habla de las propiedades de la suma y el producto de números enteros. A los efectos que nos interesa es suficiente hablar solamente de enteros positivos.

(3) Un enunciado P es indecidible si no es posible demostrar P a partir de los axiomas del sistema, pero tampoco es posible demostrar la negación de P.

(4) Estos axiomas son una ligera variante de los Axiomas de Peano, propuestos por el matemático italiano Giusepe Peano a fines del siglo XIX.

(5) Todo sistema axiomático tiene símbolos primitivos o no definidos. A estos símbolos se les puede asignar cualquier significado, siempre que sea coherente con lo enunciado en los axiomas.

(6) Véase G.S.Boolos & R.C.Jefrrey, Computability and Logic, Cambridge University
Press, 1980. En particular, si la Conjetura de Goldbach fuese verdadera, existiría uan demostración de ella a partir de estos axiomas, esto refuta buena parte del argumento de la novela El Tío Petros y la Conjetura de Goldbach.

Addenda:

Dentro del contexto de los Axiomas de Peano definamos 2 = Sig(1), 3 = Sig(2) y 4 = Sig(3). Ésta es una demostración de que 2 + 2 = 4:

2 + 2 = 2 + Sig(1) = Sig(2 + 1) = Sig(Sig(2)) = Sig(3) = 4

(A la parte 10 - A la parte 12)