La lógica como sistema formal axiomático: los límites de los sistemas formales axiomáticos

Tema 7: La lógica como sistema formal axiomático: los límites de los sistemas formales axiomáticos

Introducción 1. La lógica como sistema formal axiomático 1.1. El método axiomático 1.2. Origen del método axiomático 1.3. La lógica como sistema axiomático 1.4. La aritmética como sistema axiomático 2. Los límites de los sistemas formales axiomáticos 2.1. Propiedades de un sistema axiomático 2.2. El programa de Hilbert 2.3. Teoremas de limitación de Gödel Conclusión Bibliografía y webgrafía Guión-resumen Cuestionario

Introducción El objeto de este tema son las limitaciones que pueden padecer tanto los sistemas axiomáticos de la lógica como las teorías matemáticas que son axiomatizadas mediante esos sistemas. De las teorías destaca por su importancia histórica la aritmética, que desde finales del XIX recibe un tratamiento axiomático sólo comparable al que ya había recibido la geometría en tiempos de Euclides. Y centrándonos en la aritmética, la segunda parte de este tema puede verse como una pregunta seguida de una respuesta. La pregunta, planteada por Hilbert en 1900, podría formularse de este modo: ¿podemos axiomatizar la aritmética de tal modo que se atrapen todas sus verdades? La respuesta fue dada por Gödel en 1931. Se trata de una respuesta negativa que ha tenido una enorme influencia en la filosofía de la matemática del siglo XX. En la primera parte contextualizamos los sistemas axiomáticos de la lógica dentro de la tradición axiomática. También explicamos cómo axiomatizar una teoría matemática con ayuda de alguno de aquellos sistemas. En la segunda parte exponemos tres cosas. Primero se habla de los límites de los sistemas axiomáticos. Después se expone el programa de Hilbert, donde se propone la hipótesis de que es posible construir sistemas axiomáticos que generen toda la matemática. Finalmente se exponen y comentan los famosos teoremas de incompletud de Gödel, que generalmente se interpretan como argumentos en contra del programa de Hilbert. Escribimos “sii” para “si y solamente si”. El resto de terminología y simbolismo son los habituales. ENLACE: En este tema se dan por supuestas las nociones de lógica explicadas en el tema 6. También es recomendable haber leído antes el tema 5 sobre historia de la lógica. Por otro lado, existe cierto solapamiento con el tema 8 sobre la verdad en matemáticas y en ciencias empíricas.

1. La lógica como sistema formal axiomático En la primera parte de este tema vamos a exponer la lógica desde el punto de vista de su presentación axiomática. Subrayaremos que la lógica no es sólo una de las muchas teorías que pueden ser axiomatizadas. Sus teoremas, por ser universalmente válidos, están incluidos en cualquier otra teoría; además, su lenguaje y su cálculo son un instrumento con el cual axiomatizar otras teorías científicas. Así pues, cada teoría axiomatizada T contendrá todas las verdades de la lógica más todas las afirmaciones que se sigan lógicamente de los axiomas de T. 1.1. El método axiomático No hay una única caracterización del método axiomático, pero podemos destacar tres actividades que siempre se mencionan en sus definiciones habituales: (i) proceso por el cual se axiomatiza una teoría, (ii) estudio de la teoría axiomatizada, (iii) utilización de dicha teoría. El primer proceso es una búsqueda intelectual no sujeta a reglas predeterminadas, que se lleva a cabo por especialistas de la teoría en cuestión; los otros dos procesos interesan solamente a los lógicos y a aquellos filósofos que teorizan sobre la ciencia. En cualquier caso, la definición más común dice que el método axiomático consiste en la axiomatización de teorías. Veamos, pues, qué es una teoría y qué se entiende por axiomatización de una teoría. Una teoría es un conjunto de afirmaciones que está cerrado bajo la relación de consecuencia (esta es la definición lógica de teoría). Las afirmaciones son fórmulas de algún lenguaje, generalmente el de predicados. Que la teoría esté cerrada bajo la relación de consecuencia significa que cualquier consecuencia de una o más afirmaciones de la teoría forma parte de la misma. Formalmente: dado un lenguaje L, si T es un conjunto de fórmulas, A es una fórmula y T ├ A significa que A es consecuencia lógica de T, entonces T es una teoría sii T ├ A implica A ∈ T para cualquier A. Así pues, una teoría está formada no sólo por cuanto decimos sobre un determinado asunto, sino también por las consecuencias de todo eso que hemos dicho. Las fórmulas de una teoría son generalmente interpretadas como afirmaciones acerca de algún universo, que puede ser empírico (bienes y precios, partículas en movimiento, elementos químicos, células, especies biológicas, fonemas...) o abstracto (números, funciones, superficies, ecuaciones...), lo que da lugar a la división correspondiente entre teorías empíricas y teorías matemáticas. Las últimas son las que más nos interesan en este tema. Y en relación a ellas debe tenerse en cuenta que la definición de teoría que hemos dado más arriba no contempla la interpretación de las fórmulas. En la práctica, toda teoría es una teoría acerca de algo; ahora bien, el método axiomático se caracteriza –entre otras cosas– por ser capaz de estudiar las teorías desde un punto de vista puramente sintáctico, prescindiendo en un primer momento de la interpretación semántica de sus fórmulas. Esto no supone renunciar por completo a la semántica. Más bien se trata de una maniobra: desconectando las fórmulas de un lenguaje de sus interpretaciones supuestamente más adecuadas o intuitivas se deja vía libre a interpretaciones distintas para esas mismas fórmulas. Axiomatizar una teoría es convertirla en la teoría de un sistema axiomático. Y un sistema axiomático, como veremos a continuación, puede ser visto como un mecanismo capaz de generar una teoría. Lo más común es axiomatizar teorías matemáticas; teorías empíricas suficientemente desarrolladas también han sido axiomatizadas, si bien esto conlleva más dificultades (Díez y Moulines, 2008: 281-323).

Un sistema axiomático, a veces llamado sistema formal o cálculo axiomático, consta de un lenguaje formal, unos axiomas y unas reglas de inferencia. Ni el lenguaje tiene por qué ser un lenguaje lógico, ni las reglas de inferencia tienen por qué formalizar la relación de consecuencia lógica; sin embargo, cuando hablemos de sistema axiomático en este tema estaremos dando por supuesto esas dos condiciones. Sólo así podemos relacionar la noción de teoría con la noción de sistema axiomático, así como utilizar esta última noción para destacar el aspecto puramente sintáctico de nuestro conocimiento acerca de un determinado ámbito. Definición: Un sistema axiomático S = (L, X, R) es una construcción matemática formada por los siguientes elementos: 1. Un lenguaje formal L o conjunto de cadenas de símbolos (las fórmulas) generadas desde un alfabeto y una gramática. 2. Un conjunto X de fórmulas de L, que son los axiomas. 3. Un conjunto R de reglas de inferencia, que permiten generar una nueva fórmula a partir de una o más fórmulas dadas. Los axiomas pueden verse como afirmaciones que el sistema acepta como punto de partida. Las reglas servirían entonces para generar nuevas afirmaciones, llamadas “teoremas”, a partir de los axiomas. Formalmente: un teorema de S es cualquier fórmula de L que aparece como último elemento de una derivación de S, mientras que una derivación de S es una secuencia finita de fórmulas tal que cada una de ellas o bien es un axioma de X o bien es resultado de aplicar una regla de R a fórmulas que han aparecido previamente en la derivación. El conjunto de todos los teoremas de S es algo así como el conjunto de todas las afirmaciones que encierra potencialmente el sistema. Lo denotamos mediante Th(S) y lo llamamos teoría de S. Por abuso del lenguaje, muy frecuentemente se llama “teoría” tanto al sistema S como a su correspondiente teoría Th(S). Nosotros intentaremos ser rigurosos en el uso de estos dos conceptos. Dada una teoría T, si existe un sistema S con Th(S) = T, decimos que S axiomatiza o es una axiomatización de T. Luego T es axiomatizada por S sii las afirmaciones de T son los teoremas generados por S. Puede ocurrir que para cierta T no exista ninguna axiomatización; en ese caso decimos que T no es axiomatizable. También puede ocurrir que dos sistemas diferentes S1 y S2 generen la misma teoría T, es decir, que T = Th(S1) = Th(S2), en cuyo caso decimos que S1 y S2 son axiomatizaciones alternativas de T. Lo que acabamos de esbozar es muy abstracto y deja de lado ciertos detalles. Por ejemplo, no hemos señalado que al considerar un lenguaje formal L es habitual partir de un conjunto inicial de “símbolos primitivos” que sirven para denotar los objetos y propiedades del universo sobre el cual se quiere hablar, y que sirven también para definir con rigor (mediante reglas de definición) todos aquellos símbolos extralógicos que pueden aparecer en los teoremas generados por el sistema. Más tarde lo veremos. De momento hemos querido subrayar que las expresiones de un sistema no reciben desde el sistema ningún significado, ni tampoco pueden ser interpretadas como verdaderas o falsas respecto de ningún modelo. De hecho, con la definición de sistema axiomático que hemos dado podríamos diseñar un sistema que sirva para generar aleatoriamente contraseñas de seguridad sin significado alguno. PREGUNTA-CLAVE: Explica la diferencia entre teoría, teoría axiomática y sistema axiomático. ¿Puede axiomatizarse siempre una teoría? ¿Puede axiomatizarse de distintas maneras una teoría?

1.2. Origen del método axiomático Tanto el método axiomático como sus eventuales realizaciones, los sistemas axiomáticos, han tenido gran predicamento en la historia intelectual de Occidente. En la Grecia clásica, la silogística de Aristóteles (384-322 a.C.) en sus Analíticos primeros, la geometría de Euclides (fl. 300 a.C.) en sus Elementos y –en menor medida– la mecánica de Arquímedes (mediados del III a.C.) eran teorías axiomáticas. Se aproximaban mucho al ideal de una ciencia en la cual a partir de un reducido grupo de verdades iniciales (los axiomas) se derivan todas las verdades de esa ciencia (los teoremas). De forma un poco menos explícita, también se buscaba que a partir de unos pocos conceptos primitivos se pudieran definir todos los demás. Según este ideal, para desarrollar una ciencia bastaba en principio con tener sus axiomas. Más importante aún, para penetrar en el significado último de una ciencia todo lo que había que hacer era examinar uno a uno sus axiomas, razón por la cual tales axiomas eran objeto de especial reverencia. ¿Pero qué son los axiomas? El sustantivo castellano “axioma” viene del latín axiōma, a su vez una trascripción del sustantivo griego a1xíwma (axíōma), que viene del verbo a1xiów (axióō). Este verbo significa estimar, apreciar, honrar, valorar; también significa tener por merecedor de algo, estimar verdadero o apropiado. Luego el sustantivo puede significar o bien algo tan abstracto como dignidad, honor, consideración, estimación, o bien algo particular que se tiene por correcto, verdadero, estimable, apropiado. En suma, el término a1xíwma significaba unas veces estimación y otras veces lo estimado, dándose por sabido en este segundo caso de qué se estaba hablando. En cuanto a su significado técnico, los matemáticos y filósofos griegos consideraban que un axioma era una proposición autoevidente y necesariamente verdadera; asimismo, consideraban que ciertos conjuntos de axiomas podían contener una ciencia entera en el sentido de que podían demostrarse todas sus verdades a partir de los axiomas y siguiendo razonamientos lógicos. Aunque nos quedamos con la caracterización anterior, advertimos que los matices y los problemas interpretativos son muchos. Aristóteles, en Analíticos segundos, I, 10, tras aclarar que cada ciencia habla sobre su propio género de entidades, distingue entre los principios peculiares de una ciencia (que a su vez pueden ser hipótesis o definiciones) y los principios que son comunes a todas las ciencias. Estos últimos son los axiomas, aquéllos las tesis. Pero los axiomas no tienen una misma formulación para todas las ciencias: dice de ellos que son principios “comunes por analogía”, de modo que por un lado trascienden a cada ciencia y por otro lado se integran en ella. Aparte de tesis y axiomas, se desprende de Analíticos segundos, I, 2, 72a15, que estarían los principios metafísicos como el de no-contradicción. El mismo Aristóteles, en Analíticos primeros, organiza la lógica de acuerdo al método axiomático, derivando todos los silogismos válidos a partir de los cuatro silogismos de la primera figura, que cumplen la función de axiomas; es cierto que no sigue al pie de la letra todas las prescripciones de sus Analíticos segundos, mas ello se debe a que no consideraba que la lógica fuera una ciencia, sino una herramienta de la razón para todas las demás ciencias, conque no había motivos para aplicar allí todas las recomendaciones metodológicas de los Analíticos segundos. Más fiel a dicha metodología es Euclides en Elementos, libro I, donde distingue principios de dos tipos. Sus postulados parecen ejemplificar en geometría lo que Aristóteles llamaba hipótesis, ejemplo: “puede prolongarse continuamente una recta finita en línea recta”, sus definiciones se ajustan a las definiciones aristotélicas, ejemplo: “punto es lo que no tiene partes”, mientras que sus nociones comunes parecen adaptar al caso geométrico lo que Aristóteles llamaba axiomas, ejemplo: “si de dos cosas iguales se quitan cosas iguales, los restos son iguales”.

Tendríamos en Aristóteles y Euclides el siguiente esquema: metafísicos principios

axiomas científicos

hipótesis tesis definiciones

Los siglos XVII y XVIII no ven grandes avances en la axiomatización de teorías científicas, si bien se consolida entre los filósofos la convicción de que el método axiomático es el más alto ideal a que puede aspirar un sistema de ideas. Obras como los Principios matemáticos de filosofía natural (1687) de Isaac Newton (1643-1727) o la fascinante Ética (1677) de Baruch Spinoza (1632-1677) siguen el método axiomático sólo en apariencia; sin embargo, evidencian la importancia que se daba en ciencia y filosofía a la exhibición de unas pocas afirmaciones y conceptos primitivos como “resumen” o “compendio” de la ciencia en cuestión. El siglo XIX será testigo de nuevas axiomatizaciones científicas, sobre todo en geometría, pero también en diferentes ramas de la física matemática. Ya en el siglo XX se axiomatizan teorías sobre la probabilidad, los conjuntos, los fenómenos físicos, la economía de mercado, la evolución, etcétera, si bien hay que reconocer que la llevan a cabo lógicos y filósofos interesados en la estructura profunda de las respectivas ciencias; los científicos hoy día no suelen dar mucho crédito al método axiomático, pues requiere mucho esfuerzo y pocas veces contribuye al avance de la ciencia que está siendo axiomatizada. Hasta finales del XIX, el establecimiento de unos pocos axiomas se veía como la mejor solución al problema de la fundamentación de una ciencia. En efecto, si todas las verdades de una ciencia requiriesen ser demostradas, entonces habría que elegir entre dos opciones igualmente malas: o bien se admite una cadena infinita de premisas detrás de cada afirmación, o bien se admite que existen demostraciones circulares. Para solucionar todo esto se establece que existen unas pocas afirmaciones indemostrables más allá de las cuales no podemos retroceder en nuestra búsqueda de fundamentos. Y lo mismo vale para los conceptos primitivos de una teoría, a partir de los cuales se definen todos los demás conceptos. Ahora bien, aunque la existencia de axiomas y conceptos primitivos soluciona el problema de la fundamentación de una ciencia, se abre otro problema: ¿de dónde viene la verdad de los axiomas y la evidencia de los conceptos primitivos? Aristóteles y los filósofos racionalistas hablaban de intuición intelectual, mientras que los empiristas tendían a considerar los axiomas como generalizaciones empíricas y los conceptos primitivos como sensaciones especialmente claras. A finales del XIX, como veremos más adelante, se adoptará una postura convencionalista con respecto de los axiomas y de los conceptos primitivos; no tanto por la vía de la argumentación filosófica como por la constatación de que para una misma teoría existen diferentes axiomatizaciones, cada una de ellas equipada con un conjunto distinto de axiomas y conceptos primitivos. Este hecho restará importancia a la diferencia entre axiomas y teoremas, así como a la diferencia entre conceptos primitivos y conceptos derivados. La nueva preocupación será la exactitud del lenguaje, la explicitación de las reglas de inferencia, las diferentes interpretaciones semánticas que pueden darse a los axiomas, y las propiedades abstractas de los sistemas axiomáticos en tanto que objetos matemáticos. PREGUNTA-CLAVE: Etimología y sentido precientífico de “axioma”. Características de los axiomas desde Aristóteles hasta finales del XIX.

1.3. La lógica como sistema axiomático Como ya se ha dicho, la lógica fue de las primeras disciplinas en adoptar el método axiomático. La silogística de Aristóteles y la lógica proposicional del estoico Crisipo (mediados del III a.C.) presentan ya, hasta cierto grado de perfección, la forma de sistemas axiomáticos. El uso de un lenguaje semiformalizado era común a esas dos tradiciones: Aristóteles representaba cualidades mediante letras mayúsculas; Crisipo representaba enunciados delarativos simples mediante “lo primero”, “lo segundo”, etc. En cuanto al cálculo, parece que los dos autores distinguían hasta cierto punto entre axiomas y reglas, explicitando las reglas menos evidentes; además manejaban con maestría axiomas y reglas en la derivación de teoremas. No es raro, pues, que también el padre de la lógica simbólica contemporánea, el matemático alemán Gottlob Frege (1848-1925), dispusiera en su Conceptografía (1879) la nueva lógica bajo la forma de una teoría axiomática, esta vez con un lenguaje y un cálculo muy precisos. Pasamos a describir el sistema LP, que llamamos así por “lógica de predicados” y que es uno de los posibles sistemas axiomáticos con los cuales puede axiomatizarse la teoría lógica correspondiente al lenguaje de predicados. Con otras palabras, como el cálculo de LP es correto y completo con respecto de la semántica estándar, Th(LP) es el conjunto de todas las fórmulas válidas de la lógica de predicados. LP consta del lenguaje formal de predicados, el símbolo de igualdad, seis axiomas, dos reglas y cuatro definiciones. El lenguaje formal ya lo conocemos por el tema 6. Dicho lenguaje es capaz de distinguir entre términos (que refieren a entidades) y fórmulas (que se utilizan para hacer afirmaciones). Los axiomas que presentamos más abajo son en realidad esquemas de axioma; así, por A1 son axiomas p→(q∧p→p), p→ (p→p), etc. Las reglas se llaman “modus ponens” y “generalización”. Las definiciones pueden verse como un tipo particular de reglas. Esquemas de axioma del sistema LP A1

A→(B→A)

A2

[A→(B→C)]→[(A→B)→(A→C)]

A3

(¬A→¬B)→(B→A)

A4

∀xA(x)→A(t)

A5

∀x(x = x)

A6

∀xy[x = y→[A(x)→A(y)]]

Reglas de inferencia del sistema LP MP

De A y A→B se sigue B

GEN De A→B(x) se sigue A→∀xB(x) donde x no está libre en A Definiciones del sistema LP A∧B

se define mediante ¬(A→¬B)

A∨B

se define mediante ¬A→B

A↔B se define mediante (A→B)∧(B→A) ∃xA

se define mediante ¬∀x¬A

Recordemos que una derivación es una secuencia finita de fórmulas tal que cada una de ellas o bien es un axioma o bien resulta de aplicar las reglas de inferencia MP, GEN y acaso las definiciones a las fórmulas previas. Un teorema, por otro lado, es una fórmula que aparece al final de alguna derivación. Formalmente: A es teorema sii existe una derivación donde A aparece en último lugar. Escribimos entonces ├ A. Veamos cómo se deriva el teorema A∨¬A en este sistema, lo que equivale a probar A∨¬A ∈ Th(LP). En la columna del centro va la secuencia de fórmulas, a la izquierda las numeramos, a la derecha explicamos de dónde sale cada una de ellas. Ejemplo: Demostración de ├ A∨¬A 1.

(¬¬A→((A→¬¬A)→¬¬A))→((¬¬A→(A→¬¬A))→(¬¬A→¬¬A))

A2

2.

¬¬A→((A→¬¬A)→¬¬A)

A1

3.

(¬¬A→(A→¬¬A))→(¬¬A→¬¬A)

MP 1, 2

4.

¬¬A→(A→¬¬A)

Α1

5.

¬¬A→¬¬A

MP 3, 4

6.

(¬¬A→¬¬A)→(¬A→¬A)

A3

7.

¬A→¬A

MP 5, 6

8.

A∨¬A

Df.(∨) 7

Como se ve fácilmente, el nivel de abstracción en las derivaciones de este cálculo es mayor que en el cálculo de deducción natural. En el caso proposicional, al contar solamente con la regla MP para llevar a cabo derivaciones, toda estrategia descansa en buscar pares de fórmulas M y M→N tales que N sea la fórmula buscada en cada momento. También pueden aplicarse definiciones, como se aprecia en el último paso de la derivación que hemos puesto de ejemplo. Ahora bien, ¿qué tipo de teoría es Th(LP)? Decíamos al comienzo que toda teoría, pese a que pueda ser abordada en su aspecto sintáctico, debería en principio hablarnos acerca de algo. Como el cálculo de LP es correcto y completo con respecto de la semántica estándar de la lógica de predicados, tenemos que el conjunto de teoremas Th(LP) es el conjunto de verdades lógicas expresables en el lenguaje de predicados. Pero entonces, ¿de qué nos hablan las fórmulas de Th(LP)? Para la pregunta que acabamos de formular no hay una respuesta que satisfaga a todo el mundo. Las verdades lógicas hablan acerca de todo y de nada, pues son verdaderas acerca de cualquier estructura; la fórmula A∨¬A, por ejemplo, será verdadera con independencia de cómo interpretemos A. Algunos filósofos dicen que tales verdades reflejan, de algún modo, las estructuras más generales e indubitables de la realidad; otros, menos optimistas, prefieren decir que reflejan estructuras del pensamiento a través de las cuales organizamos nuestro conocimiento sobre el mundo; en tercer lugar, y teniendo en cuenta la existencia de diferentes lenguajes y cálculos lógicos, hay quienes rebajan la importancia de Th(LP) para decir que sus fórmulas nos hablan simplemente de un modo posible en que pueden comportarse sus símbolos lógicos (conectivas, cuantificadores, símbolo de igualdad). Sea como fuere, lo que nos interesa saber desde la perspectiva de este tema es lo siguiente: dado que cualquier teoría axiomatizada en el lenguaje de predicados presupone los axiomas y reglas de LP,

tenemos que Th(LP) ⊆ Th(S) para cualquier sistema S, es decir, que la teoría de cualquier sistema axiomático contiene como mínimo las verdades lógicas generadas por el sistema LP. Esto habría que matizarlo un poco más, pues el lenguaje puro de LP admite infinitas variables de predicado en tanto que el lenguaje de una teoría particular suele tener un número limitado; sin embargo, la idea intuitiva por la cual todas las verdades de la lógica subyacen a toda teoría matemática es cierta. Como consecuencia metodológica, estudiar LP antes de ponerse a axiomatizar una teoría particular es muy ventajoso porque supone (entre otras cosas) estudiar aquello que tienen en común todas las teorías axiomatizadas. Por último, ¿cómo puede servir de soporte LP a la axiomatización de teorías matemáticas? Muy sencillo. Primero se delimita en el lenguaje del sistema un conjunto de constantes y letras de predicado que nos vayan a ser de utilidad para hablar del universo que nos interese. Ese lenguaje puede enriquecerse con algunas definiciones. Después viene lo complicado: añadir axiomas que representen la información de partida que deseamos manejar. Algunas veces, aunque no muy frecuentemente, pueden añadirse reglas de inferencia adicionales. PREGUNTA-CLAVE: ¿En qué sentido son equivalente el cálculo axiomático de este tema y el cálculo de deducción natural del tema 6? Explica acerca de qué nos hablan los teoremas de Th(LP) y cuál es su relación con los teoremas de Th(S) para un sistema axiomático S cualquiera.

1.4. La aritmética como sistema axiomático En este apartado presentamos un sistema axiomático basado en los recursos de LP que sirve para representar nuestro conocimiento acerca de la aritmética, esto es, acerca de todos los hechos relativos al conjunto N = {0, 1, 2, 3...} de números naturales y a la interacción de tales números mediante las operaciones de suma y producto. Es un ejemplo de sistema que axiomatiza una teoría, la teoría de la aritmética en este caso; además, nos va a servir para entender mejor los teoremas de Gödel que comentamos al final del tema. El sistema AP está formulado en lógica de predicados. Su lenguaje, aparte del símbolo de identidad y los símbolos lógicos habituales, contiene la constante “0” para el cero, así como tres nombres de función “s”, “+”, “·” para denotar la función unaria de sucesión, la función binaria de suma y la función binaria de producto. Sus axiomas y reglas incluyen los de LP. Los axiomas propios de AP son los siguientes: Axiomas del sistema AP P1 ∀x ( s(x) ≠ 0 ) P2 ∀xy ( s(x) = s(y) → x = y ) P3 ∀x ( x + 0 = x ) P4 ∀xy ( x + s(y) = s(x + y) ) P5 ∀x ( x · 0 = 0 ) P6 ∀xy ( x · s(y) = x + (x · y) ) Esquema de axioma del sistema AP P7 Para toda fórmula F(x) con x como única variable libre: F(0) ∧ ∀x [ F(x) → F(s(x)) ] → ∀x F(x)

El axioma P1 dice que el 0 es el primer elemento de los naturales, pues no es sucesor de ningún otro número. P2 informa de que dos números distintos no pueden compartir un mismo sucesor. Tomados conjuntamente, P1 y P2 caracterizan la forma en que se distribuyen los naturales a lo largo de una sucesión que tiene al 0 como primer elemento, que crece linealmente y que no tiene último elemento. Los axiomas P3 y P4 definen recursivamente la suma; P5 y P6 hacen lo mismo con el producto. El esquema P7, llamado frecuentemente “axioma de inducción” o “principio de inducción”, merece un comentario aparte. Que sea un esquema de axioma en vez de un axioma quiere decir que AP admite como axiomas las infinitas fórmulas de la lógica de predicados que, partiendo del vocabulario propio de AP, se ajustan al esquema de P7. Así pues, AP tiene un número infinito de axiomas. ¿Es esto un problema? Aunque parezca extraño, no lo es. El motivo es que ante cualquier fórmula A podemos decidir, en un número finito de pasos y sin equivocarnos, si A pertenece o no al conjunto de axiomas de AP. Como veremos más adelante, es preferible un sistema axiomático con infinitos axiomas pero basado en el lenguaje de predicados, que un sistema axiomático en lógica de segundo orden con un número finito de axiomas. Con las nociones primitivas de AP podemos definir el resto de nociones de la aritmética. Por ejemplo, mediante ∀xy [ x < y ↔ ∃z (z ≠ 0 ∧ x + z = y) ] definimos la relación de “ser estrictamente menor que”. Con los axiomas y reglas propios de LP, que AP también tiene como suyos, podemos demostrar muchas verdades aritméticas. Pero es gracias a P7 que podemos demostrar ciertos teoremas relativos a un número infinito de naturales. En efecto, P7 nos dice que para demostrar que todos los naturales cumplen cierta propiedad F basta demostrar dos cosas: primero, que la cumple el 0; segundo, que si un número arbitrario la cumple entonces la cumple el siguiente. Con esas dos premisas, P7 y modus ponens deducimos que todo natural cumple F. AP es también llamado “aritmética de Peano” en honor al matemático italiano Giuseppe Peano (1858-1932), quien propuso el primer sistema universalmente aceptado para axiomatizar la aritmética en su obra Los principios de la aritmética (1889), donde se perfecciona la axiomatización de Richard Dedekind (1831-1916) en ¿Qué son y para qué sirven los números? (1888). El sistema original de Peano era algo más complejo que AP. Algunos de sus axiomas servían para separar los números naturales del resto de entidades posibles, mientras que en AP se asume que los naturales son justamente las entidades sobre las que se habla; por otro lado, Peano formulaba P7 como un solo axioma de la lógica de segundo orden. Lo importante, empero, es que tanto el sistema original de Peano como su versión AP en lógica de predicados eran considerados como sistemas capaces de generar toda la aritmética. PREGUNTA-CLAVE: Expresa con tus propias palabras, uno a uno, los axiomas del sistema AP. ¿Qué significa que P7 es un esquema de axioma y no un axioma concreto?

2. Los límites de los sistemas formales axiomáticos Hablar de límites de un sistema axiomático es en realidad ponerse a interpretar filosóficamente dicho sistema, pues no existe una definición matemática de “limitación” o de “teorema de limitación”. De vez en cuando se reconoce con claridad que lo expresado por un teorema acerca de un sistema indica ciertas limitaciones de este último. Tal ocurre con los teoremas de incompletud de Gödel de 1931 que exponemos al final de este tema, tras una amplia contextualización.

2.1. Propiedades de un sistema axiomático Vamos a exponer y comentar cuatro propiedades que puede cumplir o dejar de cumplir un sistema axiomático S = (L, X, R). Dichas propiedades, de no ser cumplidas, pueden verse como limitaciones del sistema. Las dos primeras hacen referencia a la teoría Th(S) generada por el sistema. La segunda puede hacer referencia tanto a Th(S) como al conjunto de axiomas X. La tercera hace referencia exclusivamente a X. 1. Consistencia. Un sistema S es consistente sii no hay ninguna fórmula A tal que tanto A como ¬A forman parte de Th(S). Será inconsistente sii hay alguna fórmula A tal que tanto A como ¬A forman parte de Th(S). 2. Completud. Un sistema S es completo sii para toda fórmula A se cumple que o bien A o bien ¬A forman parte de Th(S). Será incompleto sii hay al menos una fórmula A tal que ni A ni ¬A forman parte de Th(S), en cuyo caso se dice que A es indecidible respecto de S. 3. Decidibilidad. Un sistema S es decidible sii existe un algoritmo (conjunto de reglas) con el cual puede decidirse, de forma mecánica y en un número finito de pasos, si una fórmula cualquiera A pertenece o no pertenece a Th(S). Será indecidible en caso contrario. Análogamente, su conjunto de axiomas X es decidible sii existe un algoritmo con el cual puede decidirse, de forma mecánica y en un número finito de pasos, si una fórmula cualquiera A pertenece o no pertenece a X. Será indecidible en caso contrario. 4. Independencia. Un conjunto de axiomas X es independiente sii ninguno de sus axiomas es derivable a partir de los demás, en cuyo caso decimos que todo axioma es independiente del resto de axiomas. Naturalmente, es deseable que todo sistema axiomático S tenga un conjunto de axiomas X decidible e independiente, asi como una teoría Th(S) consistente, completa y decidible. Pensemos que si la matemática entera fuera un sistema axiomático decidible, y además conociéramos el algoritmo correspondiente, entonces la tarea de comprobar si una afirmación matemática es cierta se convertiría en un trabajo rutinario que cualquier ordenador sería capaz de ejecutar por sí mismo. Si un sistema S es consistente, entonces podemos estar seguros de que a partir de él no vamos a derivar afirmaciones contradictorias entre sí. Que además de consistente sea completo supone que para toda afirmación existe una derivación para ella o para su negación. Visto de otro modo, apreciamos un sistema consistente y completo porque con él es posible derivar, con respecto de toda afirmación expresable en su lenguaje, o bien su afirmación o bien su negación, peor no ambas cosas a la vez. Queremos además que Th(S) sea verdadera, pero esta es ya una cuestión semántica que debe ser valorada desde fuera del sistema. ¿Por qué es inaceptable que un sistema S sea inconsistente? Porque si en Th(S) tenemos una fórmula y su negación, de ahí se sigue que cualquier otra fórmula pertenecerá a Th(S), con lo cual no se discrimina entre verdades y falsedades en la medida en que acepta la verdad de absolutamente todo. De hecho, Th(S) ni siquiera tiene el valor de ser una teoría absurda pero con cierta individualidad, ya que cualquier otra teoría inconsistente sería equivalente a ella por contener exactamente las mismas afirmaciones, que es tanto como decir que ambas contienen todas las afirmaciones. Este hecho se conocía ya desde Duns Scoto (1266-1308) como ex contradictione quodlibet sequitur, “de la contradicción se sigue cualquier cosa”.

La decidibilidad no ha de confundirse con la completud. Ambas propiedades dicen cosas muy parecidas, por lo que no es raro que históricamente se haya confundido una con otra, o incluso se vieran como equivalentes. En lo que sigue nos referiremos a la decidibilidad de teorías, no de conjuntos de axiomas. Mientras la completud nos habla de la existencia de derivaciones (de teoremas), la decidibilidad nos habla de la existencia de cierto tipo de algoritmos. Tradicionalmente, se llama Entscheidungsproblem, “problema de la decisión”, al problema de encontrar un algoritmo de decisión adecuado para la teoría de un sistema axiomático. dado un sistema S, podemos ver un algoritmo de decisión FS como una función tal que asigna 1 a las fórmulas de S que son teoremas y 0 a las que no lo son. Por ejemplo, tomando como S el sistema axiomático de la lógica proposicional, FS(p∨¬p) = 1, FS(p∨¬q) = 0, etcétera. Ahora bien, ¿existe un algoritmo semejante para la lógica de proposiciones? La respuesta es afirmativa; de hecho, las tablas de verdad son ya un algoritmo de decisón para el conjunto de tautologías de la lógica proposicional. Para la lógica de predicados, por desgracia, no existe un algoritmo así, por lo que decimos que es indecidible. Un conjunto X de axiomas es independiente sii no hay A ∈ X tal que X–{A}├A. En términos coloquiales, X es independiente cuando en él no sobra ninguna fórmula, es decir, cuando no pueden quitarse fórmulas sin eliminar al mismo tiempo algunas de las consecuencias de X. Por ejemplo {p, p∨q} no es independiente porque le sobra p∨q, que es deducible de p, mientras que {p, p→q} sí es independiente. La utilidad de este concepto es evidente. Si un conjunto de axiomas es independiente, podemos tratar de sustituir alguno de sus axiomas por su negación para obtener un nuevo sistema que es diferente del inicial y que podría ser consistente. PREGUNTA-CLAVE: Define las propiedades de consistencia, completud, decidibilidad e independencia. Relaciona los dos conceptos de decidibilidad?.

2.2. El programa de Hilbert El “programa de Hilbert” es un programa de investigación en el cual se pretende aprovechar la lógica para axiomatizar cualquier teoría matemática; dicha axiomatización debe ir siempre seguida, cuando menos, de una demostración por la cual esa teoría recién axiomatizada es consistente. Se trata de un programa de fundamentación de las matemáticas que aprovecha las mismas herramientas lógicas del logicismo, pero tiene en cuenta la crítica del intuicionismo a los razonamientos acerca de conjuntos infinitos. Sus principales tesis: 1. Axiomatización. Hay que axiomatizar la matemática clásica con los recursos de la lógica. Esto supone axiomatizar las distintas ramas de la matemática, iniciando así un estudio meta-matemático de cada una de ellas mediante el estudio de los respectivos sistemas axiomáticos que las axiomatizan. 2. Consistencia. Debe comprobarse, mediante métodos finitarios, que dicha axiomatización es consistente. Habrá pruebas de consistencia relativa, donde se demuestre que un sistema es consistente si lo es otro sistema, pero en algún momento habrá que dar también pruebas de consistencia absoluta. Los dos puntos que acabamos de esbozar son tan sólo el denominador común de una serie de propuestas, no siempre coincidentes entre sí, que se iban desarrollando en conferencias, notas de clase y artículos que elaboraba el matemático alemán David Hilbert (1862-1943) en la década de 1920. Otras versiones más fuertes del programa

exigían que todas las axiomatizaciones fueran consistentes, completas y decidibles. También se exigía (sobre todo a finales de aquella década) conectar la derivabilidad formal de los sistemas axiomáticos con la noción semántica de consecuencia.

David Hilbert (1862-1943)

Hilbert pretendía con su programa ofrecer una nueva fundamentación de la matemática que, evitando paradojas y organizando todo lo que se sabía hasta la fecha, aprovechase lo mejor de la matemática de los conjuntos infinitos y lo mejor de la matemática finitaria de los intuicionistas. ¿Cómo? permitiendo que los sistemas axiomáticos hablasen acerca de tales conjuntos, pero prescindiendo de ellos en las demostraciones acerca de esos mismos sistemas. En cuanto a la axiomatización de “la” matemática, en singular, el programa de Hilbert no sugiere que haya de construirse un solo sistema axiomático con el cual generar deductivamente la matemática entera (tal y como propugnaban los logicistas). Basta, dice Hilbert, con encontrar axiomatizaciones adecuadas para cada una de las principales teorías matemáticas, de entre las cuales sobresalen el análisis matemático y la geometría. Ahora bien, ¿por qué molestarse en axiomatizar una teoría? Hay respuestas diversas, pero la que realmente dio impulso al programa de Hilbert es la siguiente: una teoría axiomatizada puede estudiarse mejor que una teoría sin axiomatizar porque en el primer caso basta con estudiar el lenguaje en que está formulada, sus axiomas característicos y sus reglas de inferencia. En un primer momento, Hilbert puso el acento en los axiomas; más adelante, según se fue familiarizando con la lógica, empezó a dar la debida importancia a la explicitación del lenguaje y de las reglas de inferencia. Hacia el final de la década de 1920, como se constata en el capítulo III, 10, de Elementos de lógica teórica (1928) escritos junto a su colaborador Wilhelm Ackermann (1896-1962), Hilbert tenía ya muy clara la diferencia entre un sistema axiomático de la lógica y una teoría axiomatizada mediante las herramientas de la lógica. En cuanto a la consistencia, Hilbert se pregunta si es consistente la teoría Th(AP), es decir, la teoría generada por los axiomas de Peano. Esta pregunta es en realidad el segundo de los 23 problemas que expuso oralmente en el Congreso Internacional de Matemáticos celebrado en París en 1900. Su ponencia Mathematische Probleme, “Problemas matemáticos”, ha tenido una influencia enorme en el curso de la investigación matemática del siglo XX. Y el problema segundo es uno de los problemas considerados más importantes. ¿Por qué? Para entenderlo hay que ver dicho problema en el contexto de las pruebas de consistencia relativa llevadas a cabo en la segunda

mitad del siglo XIX. En este sentido, Hilbert no hizo sino sacar las últimas consecuencias de un proceso que ya estaba en marcha. Karl Weiertrass (1815-1897) y Richard Dedekind (1831-1916) habían demostrado que la consistencia del análisis matemático dependía de la consistencia de la aritmética. Eugenio Beltrami (1835-1899) había demostrado en 1868 que la geometría hiperbólica es consistente si lo es la geometría euclídea. Y el propio Hilbert, en sus Fundamentos de la geometría (1899), había demostrado que la consistencia de esa geometría euclídea dependía de la consistencia de la aritmética. Luego la consistencia de la matemática, si por tal se entiende la geometría y el análisis, depende en última instancia de la consistencia de la artimética; de ahí la importancia de la pregunta formulada. Las pruebas de consistencia relativa se basaban en la búsqueda de una estructura que hiciera verdaderos a todos los axiomas del sistema bajo estudio. Probar la consistencia de T era encontrar una estructura que hiciera vedaderos a sus axiomas. Pero la construcción de tal estructura se hacía siempre desde una segunda teoría U, con lo cual solamente se podía concluir que T era consistente si U también lo era. Como la aritmética era la teoría desde la cual se construían aquellas estructuras al demostrarse la consistencia relativa de la geometría, el análisis, etcétera, Hilbert llegó a la conclusión de que para demostrar la consistencia de la matemática había que encontrar una prueba absoluta de la consistencia de la aritmética. Para ello debía estudiarse la aritmética como puro sistema formal de axiomas y reglas, sin recurrir a interpretaciones semánticas. Muchos han exagerado la dimensión sintáctica o formal del programa de Hilbert, llamándolo “programa formalista” y subrayando los aspectos que lo enfrentan al logicismo de Frege o al intuicionismo de Brouwer. Según este enfoque, el programa de Hilbert asume que hacer matemáticas es jugar con un montón de símbolos carentes de significado; las reglas del juego serían las reglas de inferencia, únicas fuentes de legitimidad en el uso de los símbolos. Y aunque algunas afirmaciones un tanto exageradas del propio Hilbert dan pie a esta interpretación, sus trabajos matemáticos y filosóficos no la justifican. Era su insistencia en el problema de la consistencia de la aritmética lo que a veces le hacía parecer demasiado formalista. En esas ocasiones parecía querer decir que la consistencia de un sistema axiomático es el único criterio desde el cual se puede juzgar la verdad de una afirmación matemática, que sería verdadera en la medida en que no entrase en contradicción con su correspondiente sistema axiomático. Pero esto contradice no sólo su aceptación de que existe una verdad semántica, sino también el hecho puramente formal de que pueden existir afirmaciones independientes con respecto de una teoría. PREGUNTA-CLAVE: ¿Qué es el programa de Hilbert? ¿Jugaba algún papel la lógica dentro de ese programa? ¿Y la aritmética? Explica por qué era tan importante demostrar la consistencia de una teoría aparentemente sencilla como es la aritmética.

2.3. Teoremas de limitación de Gödel Kurt Gödel ha sido el lógico más grande del siglo XX. Nace en 1906 en Brünn (actual Brno), que entonces era parte del Imperio Austro-Húngaro y hoy día pertenece a la República Checa. Se trataba de una persona inquisitiva, sensible y extremadamente meticulosa, que encontró en la lógica la única ciencia que colmaba sus aspiraciones de transparencia y precisión. Los cambios de residencia, de nacionalidad y de intereses intelectuales fueron una constante en su vida. Aunque a los 12 años, con la disolución del Imperio tras la Primera Guerra Mundial, es nacionalizado automáticamente checo, su origen familiar y su lengua materna eran alemanes. Se sentía austriaco, por lo que se nacionaliza como tal a la edad de 23. Por aquel entonces cursaba estudios de física,

matemáticas y filosofía en la Universidad de Viena. Allí realiza, entre 1929 y 1939, importantes contribuciones a la lógica y a la teoría de conjuntos. Con la anexión de 1938 se le vuelve a imponer una nacionalidad que no había elegido, esta vez alemana. Y dos años más tarde, en 1940, se ve forzado a emigrar a los Estados Unidos, donde se nacionaliza dos años más tarde norteamericano. Trabajaba para el Institute of Advanced Studies de Princeton, un centro de investigación donde se congregaban algunos de los más grandes científicos eurpeos en el exilio. Comenzará allí a interesarse allí por la filosofía de la matemática, sobre la cual reflexionó mucho pero apenas publicó nada. Muere en Princeton en 1978.

Kurt Gödel (1906-1978)

Teoremas de Gödel. Sus célebres teoremas de limitación aparecen en el artículo “Sobre proposiciones formalmente indecidibles en los Principia Mathematica y sistemas afines” (1931), publicado cuando Gödel tenía 25 años. No nos hablan de sistemas de lógica pura como LP, sino del sistema AP. Primer teorema de Gödel: Si AP es consistente, es incompleto. Segundo teorema de Gödel: Si AP es consistente, entonces no se puede demostrar el teorema, expresable dentro del propio lenguaje de AP, que afirma la consistencia de AP. Estos dos teoremas, tal y como los hemos formulado, se mantienen dentro del campo de conceptos que veníamos manejando hasta ahora. Pero Gödel en realidad no hablaba de consistencia, sino de ω-consistencia, una propiedad que implica consistencia sin ser implicada por ella. La ω-consistencia es un concepto algo técnico en el que no vamos a detenernos, pues John Barkley Rosser (1907-1989) demostró en 1936 que los teoremas de Gödel son válidos también para la consistencia. Otro matiz importante es que los teoremas pueden generalizarse desde AP hasta cualquier sistema que contenga los axiomas de AP. Para ver la importancia de esto, supongamos que alguien dice, ante la formulación de más arriba, “de acuerdo, si hay fórmulas F1, ..., Fn que deberían estar en Th(AP) pero no son derivables desde los axiomas de AP, añadamos tales fórmulas a AP como nuevos axiomas, obteniendo un nuevo sistema AP2 cuya teoría Th(AP2) será lo que buscamos”. A esto se puede replicar

que AP2 adolece del mismo problema que AP una vez le aplicamos la versión generalizada de los teoremas de Gödel. Y lo mismo valdría para nuevos sistemas AP 3, AP4, etcétera, contruidos como el anterior. Esquema de prueba. Para demostrar el primer teorema, Gödel tuvo que inventar lo que hoy se conoce como “codificación de Gödel”, por la cual se pueden codificar tanto fórmulas como secuencias de fórmulas mediante números naturales. A nivel sintáctico, cada fórmula A tiene asignado un único numeral [A]. Si entonces tomamos x como código de una secuencia de fórmulas e y como código de una fórmula, podemos escribir P(x, y) para expresar que x es el código de una derivación en AP donde se demuestra la fórmula codificada por y. Por ser P un predicado decidible, la relación expresada por P también lo es. Tomando Pi, xi, yi como las interpretaciones respectivas del predicado P y de los numerales x, y, tenemos: Si (xi, yi) ∈ Pi, entonces AP ├ P(x, y) Si (xi, yi) ∉ Pi, entonces AP ├ ¬P(x, y) Gödel define a continuación un predicado monario, esta vez indecidible, que expresa la propiedad de ser un teorema de AP. Prov(x) sii ∃y P(y, x) Ahora se puede construir una fórmula G autorreferente que dice de sí misma que no es un teorema de AP. G ↔ ¬Prov([G]) Hecho esto, Gödel demuestra que ni G ni su negación ¬G son teoremas de AP. El razonamiento es similar al de la paradoja del metiroso; sin embargo, no se llega a una contradicción dentro de una teoría, en este caso Th(AP), sino al hecho de que existe una fórmula tal que ni ella ni su negación pertenecen a la teoría. Con ello no sólo se demuestra que AP es incompleta (bajo el supuesto de que sea consistente), sino que la propia naturaleza de G impide que pueda añadirse como nuevo axioma al sistema AP. El paso del primer teorema al segundo se realiza mediante la definición de un predicado autorreferente Con(AP) que expresa la idea de que AP es consistente. Se considera entonces el condicional Con(AP) → ¬Prov([G]) Se trata de un teorema de AP. Pero entonces, por la definición de G, llegamos a una contradicción, lo que invalida el antecedente del condicional. Con ello queda demostrado que AP no puede demostrar su propia consistencia. Implicaciones filosóficas. El primer teorema contradice algo que Hilbert, aun sin afirmar explícitamente, parecía dar por verdadero. Nos referimos a la completud de AP. De todos modos, esto no es tan alarmante si se tiene en cuenta que la fórmula G de Gödel no es seguramente el tipo de afirmación en la cual están interesados quienes cultivan la aritmética. Más peligroso para el programa de Hilbert es el segundo teorema, que literalmente afirma la imposibilidad de probar dentro de AP la consistencia de AP,

lo cual puede ser interpretado como una prueba de que no es posible demostrar la consistencia de AP mediante métodos finitarios. Ninguno de los teoremas de Gödel nos dice si AP es consistente o inconsistente, que a fin de cuentas era la pregunta que subyace al reto planteado por Hilbert: demostrar la consistencia absoluta de AP. Pero esto no significa que los teoremas de Gödel no tengan que ver con el programa de Hilbert. Aunque Gödel no responde de una manera directa a la pregunta de Hilbert, asume de forma hipotética la respuesta más plausible y de allí extrae consecuencias que desmontan algunos de los supuestos desde los que se formuló la pregunta. Se trata de un cambio en el objeto de la discusión. Partiendo de la hipótesis de que AP es consistente, lo cual es plausible, Gödel demuestra dos cosas que debilitan la confianza inicial que estaba implícita en el programa de Hilbert. Primero demuestra que AP no genera todas las verdades de la aritmética. Esto es como responder negativamente la pregunta de si AP es completa, una pregunta que Hilbert no se planteaba por la simple razón de que parecía dar por buena la respuesta positiva. En segundo lugar, Gödel demuestra que la consistencia de AP no es demostrable mediante los métodos finitarios suministrados por un cálculo axiomático, lo cual no refuta que la consistencia de AP sea demostrable mediante otros métodos finitarios, mas lo hace altamente improbable. Una consecuencia filosófica es el “realismo matemático” que parece desprenderse de los teoremas. En efecto, si la existencia de proposiciones indecidibles nos fuerza a distinguir entre afirmaciones verdaderas y afirmaciones demostrables, un corolario que toma fuerza dice que tal vez lo que existe es una sola realidad matemática objetiva, que el investigador descubre, y no infinidad de teorías posibles que el investigador inventa a su antojo. Esta parece haber sido la postura del propio Gödel, quien concede a las entidades matemáticas el rasgo de ser eternas y perfectas, es decir, no afectadas por el cambio y susceptibles de ser definidas con exactitud. Lo que no está tan claro es si en Gödel este realismo era un principio heurístico, un corolario de sus teoremas de limitación o una convicción anterior a dichos teoremas. En cualquier caso, la verdad matemática sería una variedad de verdad como correspondencia. Otra consecuencia del teorema tiene que ver con la filosofía de la mente, donde el argumento de Lucas-Penrose sostiene que no todos los razonamientos matemáticos efectuados por un ser humano pueden ser simulados mediante ordenador, lo cual implicaría que la Inteligencia Artificial en sentido fuerte es imposible. Dicho argumento fue expuesto por el filósofo John Lucas (1929-) en su conferencia “Minds, machines and Gödel” de 1959 –publicada en Philosophy, 1961– ante la Oxford Philosophical Society. Más tarde fue retomado por el físico Roger Penrose (1931-) en su libro The Emperor’s New Mind (1989). El argumento es como sigue. Supongamos que se programa un ordenador para que genere uno a uno todos los teoremas de la aritmética, lo cual es posible debido a la existencia del sistema axiomático AP. Ahora bien, por el primer teorema de Gödel existe una fórmula G que el ordenador es incapaz de generar pero que nosotros como programadores sabemos que es cierta. Esto demostraría que la mente humana sobrepasa la capacidad matemática de cualquier máquina, al ser capaz de alcanzar verdades que la máquina no consigue demostrar. En último término, y si el argumento se generaliza, quedaría demostrado que es imposible la construcción de sistemas que puedan llevar a cabo todas aquellas tareas inteligentes que ejecutan los seres humanos. El problema de este argumento, dicen sus críticos, es que no está claro que un ser humano pueda establecer la verdad absoluta de G. La verdad de dicha fórmula, recordemos, se funda en la hipótesis (indemostrada) de que el sistema AP es consistente. El propio Gödel extrajo consecuencias filosóficas de los teoremas de incompletud

en su conferencia “Algunos teoremas básicos sobre los fundamentos de la matemática y sus implicaciones filosóficas”, dictada en 1951 ante miembros de la American Mathematical Society en la Universidad de Brown. Allí considera un dilema donde uno de sus cuernos es equivalente a la tesis de Lucas-Penrose y el otro supone la existencia de problemas “absolutamente irresolubles” (Gödel, 1994: 155). Se consideran las dos posibilidades, aunque el propio Gödel parece decantarse por la segunda, que implica un realismo matemático extremo donde existen con respecto de la realidad matemática ciertos principios de indeterminación análogos a los principios de indeterminación relativos al mundo cuántico. PREGUNTA-CLAVE: Enuncia los dos teoremas de incompletud de Gödel. ¿Qué relación guardan con el realismo matemático? Expón brevemente el argumento de Lucas-Penrose.

Conclusión Este tema podríamos resumirlo como un diálogo entre dos lógicos. Uno de ellos, Hilbert, pregunta en 1900 si es consistente el sistema axiomático AP, que parece poder generar todas las verdades de la aritmética Responder afirmativamente a la pregunta supondría que toda la matemática es consistente, pues de la consistencia de la aritmética dependen la consistencia del análisis y de la geometría. Desde el punto de vista de la filosofía de la matemática, las consecuencias de una respuesta positiva serían fundamentalmente dos: la existencia de un objeto matemático queda garantizada por que dicha existencia no implique contradicción; las afirmaciones matemáticas dentro de una teoría son verdaderas sii son consistentes con los axiomas de la teoría. Todo esto queda en tela de juicio cuando Gödel, en 1931, proporciona una respuesta inesperada a la pregunta de Hilbert. Su primer teorema de incompletud dice que la aritmética no puede ser a la vez consistente y completa; su segundo teorema dice que la consistencia de la aritmética no puede ser probada dentro de la aritmética misma. Las consecuencias filosóficas que extrae el propio Gödel son dos: los objetos matemáticos tienen una existencia ideal, independiente de la mente humana; la verdad de una proposición matemática está condicionada por la existencia y propiedades de aquellos objetos sobre los que se está pronunciando. Bibliografía y webgrafía Obras de Gödel Gödel, K. (1986-2003). Collected Works. 5 vols. Edición de Solomon Feferman. Oxford: Oxford University Press. [Edición crítica de las obras completas de Gödel. Incluye manuscritos no publicados y abundante correspondencia.] Gödel, K. (1994). Ensayos inéditos. Edición de Francisco Rodríguez-Consuegra. Barcelona: Mondadori. [Dos trabajos de Gödel no publicados en vida y por tanto no recogicos en las Obras completas de Mosterín. Incluye un amplio estudio del editor sobre la filosofía de la matemática de Gödel.] Gödel, K. (2006a). Obras completas. 2ª ed. Edición de Jesús Mosterín. Madrid: Alianza. 1 1981. [Reúne todas las obras publicadas en vida por Gödel. Corresponde a vols. I y II de Collected Works, sin incluir algunas reseñas y notas.] Gödel, K. (2006b). Sobre proposiciones formalmente indecidibles en los Principia Mathematica y sistemas afines. Oviedo: KRK. Original: “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I”, 1931. [Artículo donde se demuestran los teoremas de incompletud.]

Vida y obra de Gödel Alonso, E. (2007). Sócrates en Viena. Una biografía intelectual de Kurt Gödel. Barcelona: Montesinos. [Exposición de la obra de Gödel desde el punto de vista de su contexto intelectual. Dirigido a filósofos.] Dawson, J.W. (1997). Logical Dilemmas. The life and work of Kurt Gödel. Wellesley (Massachusetts, USA): A.K. Peters. [La biografía más extensa y autorizada sobre Gödel, escrita por uno de los editores de Collected Works.] Fresán, J. (2007). Gödel. La lógica de los escépticos. Tres Cantos (Madrid): Nivola. [Buena obra divulgativa sobre la vida y la obra de Gödel.] Goldstein, R. (2006). Gödel. Paradoja y vida. Barcelona: Antonio Bosch. Original: Incompleteness. The Proof and Paradox of Kurt Gödel, 2005. [Trata de enlazar el carácter de Gödel con la significación de sus descubrimientos.] Mosterín, J. (2007). Los lógicos. Madrid: Espasa. 12000. [Introducción a la vida y obra de Cantor, Frege, Russell, Gödel, Von Neumann y Turing.] Wang, H. (1991). Reflexiones sobre Kurt Gödel. Madrid: Alianza. [El autor recoge sus conversaciones con Gödel sobre temas filosóficos.] Teoremas de incompletud de Gödel Franzén, T. (2005). Gödel’s Theorem. An Incomplete Guide to Its Use and Abuse. Wellesley (Massachusetts, USA): A.K. Peters. [Aclara malentendidos implícitos en supuestas “aplicaciones” de los teoremas de incompletud de Gödel.] Hofstadter, D.R. (2005). Gödel, Escher, Bach: un eterno y grácil bucle. Barcelona: Tusquets. 11987. Original: Gödel, Escher, Bach: an eternal golden braid, 1979. [Expone las ideas que subyacen a los teoremas de Gödel, así como ideas afines que están relacionadas con la verdad y la recursividad, a través de ejemplos de la filosofía, la física, la biología, la pintura y la música.] Nagel, E., Newman, J.R. (2007). El teorema de Gödel. 3ª ed. Madrid: Tecnos. 11970. Original: Gödel’s Proof, 1958. [Quizás la obra que más ha contribuido a popularizar los resultados de incompletud de Gödel. Breve y fácil de entender, aunque contiene especulaciones que han dado origen a malentendidos. Los capítulos iniciales discuten la consistencia y completud en geometría y lógica.] Smith, P. (2008). An Introduction to Gödel’s Theorems. Cambridge: Cambridge University Press. [Exposición exhaustiva de los teoremas de limitación de Gödel. Contiene abundante material sobre distintas formalizaciones de la aritmética, así como interesantes incursiones en la teoría de la computabilidad.] Smullyan, R. (1992). Gödel’s Incompleteness Theorems. Oxford: Oxford University Press. [Los teoremas de Gödel se presentan desde un punto de vista muy abstracto y en relación con los teoremas de Tarski sobre el predicado de verdad.] Smullyan, R. (2001). “Gödel’s Incompleteness Theorems”. In L. Goble [ed.], The Blackwell Guide to Philosophical Logic. Oxford: Blackwell, pp. 72-89. [Síntesis de Smullyan (1992), accesible para quienes hayan seguido un curso de lógica.] Método axiomático Blanché, R. (2002). La axiomática. México: FCE. Original: L’axiomatique, 1955. [Introducción elemental al método axiomático. No requiere conocimientos previos de lógica ni de matemáticas.]

Díez, J.A., Ulises Moulines, C. (2008). Fundamentos de Filosofía de la Ciencia. 3ª ed. Barcelona: Ariel. 11997. [Manual universitario de filosofía de la ciencia. Su capítulo 8 es una excelente introducción a la concepción de las teorías empíricas como sistemas axiomáticos interpretados.] Torretti, R. (1993). “El método axiomático”. In C. Ulises Moulines [ed.], La ciencia: estructura y desarrollo. Madrid: Trotta, pp. 89-110. [Introducción al método axiomático con referencias a la lógica.] Zach, R. (2009). “Hilbert’s Program”. In E.N. Zalta [ed.], The Stanford Encyclopedia of Philosophy. Spring 2009 Edition. URL = Metalógica Boolos, G.S. et al. (2007). Computability and Logic. 5ª ed. Cambridge: Cambridge University Press. [Exposición de la metalógica clásica con el acento puesto en los métodos computacionales.] Hunter, G. (1981). Metalógica. Madrid: Paraninfo. Original: Metalogic, 1971. [Exposición muy detallada de la metateoría de la lógica de predicados.] Kleene, S.C. (1974). Introducción a la metamatemática. Madrid: Tecnos. Original: Introduction to Metamathematics, 1952. [Obra clásica donde se exponen los principales resultados alcanzados hacia la mitad del siglo XX.] Ladrière, J. (1969). Limitaciones internas de los formalismos. Madrid: Tecnos. Original: Les limitations internes des formalismes, 1957. [Obra clásica sobre resultados de limitación. tanto de Gödel como inspirados en Gödel.] Manzano, M. (1989). Teoría de Modelos. Madrid: Alianza. [Se demuestran y comentan en detalle los teoremas de corrección, completud, compacidad, LöwenheimSkolem y otros muchos.] Zalabardo, J.L. (2002). Introducción a la teoría de la lógica. Madrid: Alianza. Original: Introduction to the Theory of Logic, 2000. [Presupone unos pocos conocimientos elementales de lógica.]

Guión-resumen 1. La lógica como sistema formal axiomático 1.1. El método axiomático  El método axiomático es la axiomatización de teorías, que pueden ser acerca de distintos ámbitos pero que son estudiadas (en tanto teorías) por la lógica.  Una teoría es un conjunto de afirmaciones que está cerrado bajo la relación de consecuencia. Aunque tales afirmaciones sean interpretadas como refiriéndose a algo, es característico del método axiomático estudiarlas (al menos en un primer momento) con independencia de sus interpretaciones.  Axiomatizar una teoría consiste en convertirla en el conjunto de teoremas generados por un sistema axiomático.  Un sistema axiomático S = (L, X, R) es una construcción que consta de un lenguaje formal L, un conjunto X de axiomas tomados de dicho lenguaje, y un conjunto R de reglas de inferencia que transforman unas expresiones en otras.  Un sistema axiomático suele incluir reglas de definición para introducir nuevos términos. Sus reglas de inferencia suelen formalizar la relación de inferencia deductiva. Y las expresiones de su lenguaje suelen estar interpretadas. 1.2. Origen del método axiomático

Desde Aristóteles y Euclides se consideraba que toda teoría científica debía ser axiomatizada, explicitando sus axiomas y conceptos primitivos.  Los axiomas eran verdades necesarias y autoevidentes desde las cuales se podían demostrar el resto de verdades de una ciencia.  Esta concepción del método axiomático dura hasta el siglo XIX. 1.3. La lógica como sistema axiomático  Las fórmulas lógicamente válidas de la lógica de predicados son generadas por el sistema axiomático LP, equivalente por ejemplo al cálculo de deducción natural que vimos en el tema 6.  Th(LP) contiene los teoremas que son comunes a toda teoría matemática, es decir, que puede verse como la interseccón de todas las teorías matemáticas.  Mediante su repertorio de símbolos lógicos, axiomas y reglas puede servir de herramienta para axiomatizar cualquier teoróa matemática. 1.4. La aritmética como sistema axiomático  La aritmética puede axiomatizarse lógicamente mediante el sistema AP.  El sistema AP contiene todos los axiomas y reglas de la lógica de predicados con identidad. También contiene 6 axiomas y un esquema de axioma. 

2. Los límites de los sistemas formales axiomáticos 2.1. Propiedades de un sistema axiomático  Consistencia: un sistema S es consistente sii no hay ninguna fórmula A tal que tanto ella como su negación pertenecen a la teoría de S.  Completud: un sistema S es completo sii para toda fórmula A o bien ella o bien su negación pertenecen a la teoría de S.  Decidibilidad: un sistema S es decidible sii existe un algoritmo con el cual se puede determinar si una fórmula dada pertenece a la teoría de S.  Independencia: un sistema S es independiente sii ninguno de sus axiomas es demostrable a partir de los demás. 2.2. El programa de Hilbert  En diversos escritos de la década de 1920 Hilbert propone un programa de fundamentación de las matemáticas.  Su pretensión fundamental era demostrar la consistencia de AP, pues ello implicaba la consistencia dela matemática entera.  También exigía que los sistemas axiomáticos fueran completos y decidibles, así como que su relación de derivabilidad fuese coextensiva con la relación de consecuencia semántica. 2.3. Teoremas de limitación de Gödel  Primer teorema: si AP es consistente, es incompleto.  Segundo teorema: si AP es consistente, no se puede demostrar en AP el teorema, expresable dentro del lenguaje de AP, que afirma la consistencia de AP.  Es compatible con el relaismo matemático.  Da lugar a la tesis de Lucas-Penrose, según la cual no caben modelos computacionales de la mente humana porque ésta es apaz de acceder a la verdad de afirmaciones matemáticas no derivables por ningún sistema axiomático.

Cuestionario 1. ¿Qué se entiende en lógica por teoría?

a) b) c) d)

Conjunto de afirmaciones que cubren todas las verdades sobre un asunto. Conjunto de afirmaciones generadas por un cálculo axiomático. Conjunto de afirmaciones cerrado bajo la relación de consecuencia. Ninguna de las anteriores.

2. ¿Cuál de los siguientes elementos no aparece en un sistema axiomático? a) Lenguaje formal. b) Semántica. c) Axiomas. d) Reglas de inferencia. 3. Hasta finales del siglo XIX un axioma: a) Había de ser autoevidente y necesariamente verdadero. b) No se distinguía de una definición. c) Era una afirmación que se aceptaba por convención. d) Era derivable a partir de uno o más teoremas. 4. ¿Qué relación guardan Th(LP) con una teoría cualquiera? a) Las afirmaciones de Th(LP) son verdades de cualquier teoría. b) Las afirmaciones de Th(LP) no son verdades de ninguna teoría. c) Th(LP) ni siquiera es una teoría. d) Ninguna de las respuestas anteriores. 5. La relación de identidad: a) Se introduce en AP pero no en LP. b) Se introduce en LP por medio de dos axiomas. c) Se introduce en LP pero es redundante cuando se utiliza AP. d) Es imposible de caracterizar en lógica de predicados. 6. Los axiomas de AP: a) Solamente son los axiomas formulados con vocabulario aritmético. b) Son los axiomas de LP más los propios de AP. c) Forman un conjunto finito. d) Incluyen los axiomas de la geometría. 7. La decidibilidad de un sistema significa que: a) Puede determinarse si una determinada regla pertenece o no al sistema. b) No existen ninguna fórmula tal que ni ella ni su negación son derivables. c) No hay axiomas que sean derivables a partir del resto de axiomas. d) Puede determinarse si una determinada fórmula pertenece o no a la teoría generada por el sistema. 8. El primer teorema de Gödel dice que: a) Si AP es completa, entonces es decidible. b) Si AP es consistente, entonces es decidible. c) Si AP es incompleta, entonces es consistente. d) Si AP es consistente, entonces es incompleta. 9. En el segundo teorema de Gödel se utiliza una expresión que dice acerca de AP lo siquiente:

a) b) c) d)

Que es decidible. Que es consistente. Que es completa. Que es autorreferente.

10. El argumento de Lucas-Penrose sostiene que: a) Hay verdades matemáticas indemostrables. b) Hay verdades matemáticas que el ser humano no puede demostrar pero que un ordenador sí que podría. c) Hay verdades matemáticas que el ser humano puede conocer como verdaderas pero no demostrar por medio de un sistema axiomático como AP. d) Hay enunciados matemáticos que no son ni verdaderos ni falsos. Respuestas: 1.c, 2.b, 3.a, 4.a, 5.b, 6.b, 7.d, 8.c, 9.b, 10.c