Tema 7. 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

El método axiomático consiste en aceptar sin prueba ciertas proposiciones como axiomas o postulados, y en derivar luego de esos axiomas todas las demás proposiciones del sistema, en calidad ya de teoremas. Los axiomas constituyen los “cimientos” del sistema; los teoremas son las “superestructuras”, y se obtienen a partir de los axiomas sirviéndose, exclusivamente, de los principios de la lógica. La principal característica de un sistema axiomático es que si puede demostrarse de alguna manera la verdad de los axiomas, quedan automáticamente garantizadas tanto la verdad como la consistencia mutua de todos los teoremas. Durante los dos últimos siglos el método axiomático ha ido adquiriendo fuerza y vigor crecientes. Nuevas y viejas ramas de las matemáticas fueron provistas de los que parecían ser unos adecuados conjuntos de axiomas. Nació así un estado de opinión en el que se admitía tácitamente que todos los sectores del pensamiento matemático podían ser dotados de unos conjuntos de axiomas susceptibles de desarrollar sistemáticamente la infinita totalidad de proposiciones verdaderas suscitadas en el campo sujeto a investigación.

Según Poincaré,

Los axiomas geométricos no son, pues, ni juicios sintéticos a priori ni hechos experimentales. Son convenciones: nuestra elección entre todas las convenciones posibles está guiada por los hechos experimentales, pero permanece libre, y sólo está guiada por la necesidad de evitar toda contradicción […]. En otros términos, los axiomas de la geometría no son sino definiciones disfrazadas (La ciencia y la hipótesis, Madrid, Espasa-Calpe, 3ª ed., 1963, p. 57)

Lo característico del sistema axiomático como realización de la idea de cálculo consiste en disponer de un conjunto de enunciados o fórmulas que se admiten sin demostración y a partir de los cuales se obtienen todas as demás afirmaciones de la teoría, las cuales se llaman teoremas. Y las fórmulas aceptadas sin discusión son axiomas o postulados. El conjunto de axiomas, más la definición de enunciado o fórmula del sistema (definición que precede al enunciado de los axiomas) y el conjunto de las reglas para la obtención de teoremas a partir de los axiomas (reglas de transformación) constituyen la base primitiva del sistema.

El axiomatismo moderno no sólo no acepta la evidencia de los axiomas de las teorías, sino tampoco la intuitividad de los términos básicos de las mismas: ‘punto’, ‘recta’, ‘plano’, etc., no tienen significado por sí mismos. Son conceptos indefinidos, que sólo cuando se combinan por medio de unos u otros axiomas comienzan a quedar implícitamente definidos. Establecidas unas reglas de inferencia lógica, a partir de los axiomas puede deducirse una serie de teoremas, pero durante esta fase deductiva nada tiene significado: el cálculo es pura sintaxis. Únicamente cuando, una vez derivadas las expresiones bien formadas que pueden inferirse de los axiomas y de los términos primitivos (no definidos), comenzamos a buscar interpretaciones de dicho cálculo formal, los términos comienzan a adquirir significado y los axiomas pasan a ser verdaderos o falsos. Cada sistema axiomático puede poseer varios modelos o interpretaciones diferentes.

Sin embargo, el conocido como teorema de Gödel puso frente a los matemáticos la asombrosa conclusión de que el método axiomático posee ciertas intrínsecas que excluyen la posibilidad de que ni siquiera la aritmética ordinaria de los números enteros pueda llegar a ser plenamente axiomatizada. Demostró que es imposible establecer la consistencia lógica interna de una amplia clase de sistemas deductivos, a menos que se adopten principios tan complejos de razonamiento que su consistencia interna quede tan sujeta a la duda como la de los propios sistemas. A la luz de estas conclusiones, resulta inalcanzable una compleja sistematización final de muchas y muy importantes zonas de las matemáticas, y no puede darse ninguna garantía absolutamente impecable de que muchas de las más significativas ramas del pensamiento matemático se hallen enteramente libres de toda contradicción interna.

1. El problema de la consistencia

El método axiomático tiene su antepasado más antiguo, y también más ilustre, en Euclides. Como todos sabemos, Euclides formuló las bases para la axiomatización de la geometría a partir de cinco axiomas básicos. Unos de los axiomas que Euclides utilizó para axiomatizar la geometría se refiere a las paralelas. El axioma que adoptó es lógicamente equivalente a la hipótesis de que por un punto exterior a una línea dada solamente puede trazarse una paralela a esa línea. Este axioma es el único problemático de todo el sistema euclidiano, pues es el único axioma que no es “evidente por sí mismo”. Se trató, a lo largo de la historia de las matemáticas, por tanto, de deducirlo de otros axiomas euclidianos que se consideraban claramente autoevidentes. ¿Puede hallarse una demostración del axioma de las paralelas? Generaciones enteras de matemáticos trabajaron sin resultado en esta cuestión. Pero el reiterado fracaso en el intento de construcción de un prueba no significa que ésta no puede ser encontrada. Fue en el siglo XIX cuando se demostró la imposibilidad de deducir el axioma de las paralelas a partir de otros axiomas. La importancia de este resultado radicaba en que llamó la atención hacia el hecho de que puede demostrarse la imposibilidad de demostrar ciertas proposiciones dentro de un determinado sistema. En segundo lugar, la resolución de la cuestión planteada por el axioma de las paralelas obligó a admitir que Euclides no había dicho la última palabra acerca de la geometría, ya que pueden construirse nuevos sistemas de geometría utilizando cierto número de axiomas distintos de los adoptados por Euclides e incompatibles con ellos.

La creencia tradicional de que los axiomas de la geometría pueden ser establecidos como tales por su aparente autoevidencia fue así destruida en su misma base. Además, fue haciéndose cada vez más claro que la tarea propia del matemático puro es deducir teoremas a partir de hipótesis postuladas, y que, en cuanto tal matemático, no le atañe la cuestión de decidir si los axiomas que acepta son realmente verdaderos.

Otro modo de expresar este último punto es la famosa afirmación wittgensteiniana de que la lógica es independiente del mundo. En efecto, al lógico no le interesa para nada el saber si las proposiciones con las que hace cálculos son verdaderas o son falsas, lo único que le interesa es saber que “si las proposiciones que toma como base en sus cálculos son verdaderas, las conclusiones a las que llegue en su cálculo también serán verdaderas”; es decir, de la verdad, en un sistema axiomático, siempre se sigue la verdad; la verdad es, por tanto, una propiedad hereditaria.

La lógica – y las matemáticas en tanto que parte de la lógica – puede contemplarse por tanto como la disciplina por excelencia que extrae las conclusiones lógicamente implicadas en cualquier conjunto dado de axiomas o postulados. La validez de una deducción lógica – o matemática no depende en absoluto de ningún significado especial que pueda estar asociado con los términos o expresiones contenidos en sus postulados. La lógica – y la matemática – es algo totalmente abstracto y formal; abstracto, porque las afirmaciones lógicas pueden ser hechas en principio sobre cualquier objeto, sin estar esencialmente circunscritas a un determinado conjunto de objetos o propiedades de objeto; y formal, porque la validez de las demostraciones lógicas se asienta en la estructura de las afirmaciones más que en la naturaleza especial de su contenido. Los postulados de la lógica, o de la matemática, nunca versan intrínsecamente sobre manzanas, propiedades o presupuestos financieros; y ningún significado especial que pueda asociarse con los términos contenidos en los postulados desempeña papel esencial alguno en el proceso de deducir teoremas. La única cuestión a la que se enfrenta el lógico no es si los postulados de que parte o las conclusiones que de ellos deduce son verdaderos, sino si las conclusiones obtenidas son realmente las consecuencias lógicas necesarias de las hipótesis iniciales.

Así, Hilbert ha podido decir que mientras estemos interesados en la fundamental labor matemática de explorar las relaciones estrictamente lógicas de dependencia entre afirmaciones debemos prescindir de las connotaciones familiares de los términos primitivos, y los únicos “significados” que se deben asociar con ellos son los que se hallan determinados por los axiomas en que están contenidos. Russell dice lo mismo de una forma mucho más concisa: “la matemática pura es la ciencia en la que no sabemos de qué estamos hablando ni si lo que estamos diciendo es verdadero”.

La ventaja que ofrece una formalización tan radical, un tan radical estar apartado de la experiencia, es que la mente se libera de las restricciones que la habitual interpretación de las expresiones establece para la construcción de nuevos sistemas de postulados. Puede así surgir nuevas lógicas, nuevas álgebras y nuevas geometrías. Al hacerse más generales los significados de ciertos términos, se hace más amplia su utilización y menos limitadas las deducciones que pueden extraerse de ellos.

Ahora bien, esta creciente abstracción plantea un problema: el de saber si un determinado conjunto de postulados erigidos como bases de un sistema es internamente consistente, de tal modo que no puedan deducirse teoremas mutuamente contradictorios a partir de esos postulados. Es el conocido como problema de la consistencia.

El método general para resolver el problema de la consistencia (la idea subyacente a cualquier prueba de consistencia) consiste en encontrar un “modelo” (o “interpretación”) para los postulados abstractos de un sistema, de tal modo que cada postulado se convierta en una afirmación verdadera respecto del modelo. Por tanto, una fórmula es consistente si tiene un modelo, esto es, si puede ser interpretada como el valor de verdad V. Una fórmula no consistente se dice inconsistente o insatisfacible.

A partir de aquí podemos decir que un conjunto S de fórmulas es (semánticamente) consistente si todos los elementos admiten un modelo común; en caso contrario es inconsistente. Un conjunto de fórmulas es considerado, desde un punto de vista semántico, como la conjunción de sus elementos. Si I es una interpretación y si S es un conjunto de fórmulas, I(s) es verdadero si I(s) es verdadero para cada sÎS.

La fórmula C es una consecuencia lógica del conjunto finito S sii S unión {} es inconsistente (principio de reducción). Un conjunto es inconsistente si F es una consecuencia lógica de él o, equivalentemente, si toda fórmula es una consecuencia suya. Formalmente, el principio de reducción se expresa así:

{H1,…,Hn} |=C Û {H1,…,Hn,C}|=F

En los diversos intentos realizados para resolver el problema de la consistencia late siempre una permanente fuente de dificultad, la cual radica en el hecho de que los axiomas son interpretados por modelos compuestos de un número infinito de elementos. Esto hace imposible encerrar los modelos en un número finito de observaciones; de ahí que la verdad de los axiomas sea objeto de duda. El problema es aún mayor si tenemos en cuenta que la mayoría de los sistemas de postulados que constituyen los fundamentos de las numerosas ramas de las matemáticas y la lógica no pueden ser reflejados en modelos finitos.

El dilema al que nos vemos abocados es el siguiente: los modelos finitos bastan, en principio, para demostrar la consistencia de ciertos conjuntos de postulados, pero éstos tienen muy escasa importancia lógica o matemática. Los modelos no finitos, necesarios para la interpretación de la mayoría de los sistemas de postulados lógica o matemáticamente importantes, sólo pueden ser descritos en términos generales; y no podemos dar por sentado que las descripciones se hallen exentas de contradicciones.

Podríamos sentirnos tentados a sugerir que podemos estar seguros de la consistencia de las formulaciones en que se describen los modelos no finitos si las nociones básicas empleadas son transparentemente “claras” y “distintas”. Sin embargo, éste no es el caso. Así, en ciertas zonas de la investigación matemática en que las hipótesis acerca de los conjuntos infinitos desempeñan un importante papel han surgido contradicciones, pese a la intuitiva claridad de las nociones implicadas en las hipótesis y pese al carácter aparentemente consistente de las construcciones realizadas.

Bertrand Russell, por ejemplo, fue capaz de construir una contradicción dentro del sistema mismo de la lógica elemental. La antinomia – así se llama a estas contradicciones – puede enunciarse del modo siguiente: las clases pueden ser de dos tipos, las que no se contienen a sí mismas como miembros y las que sí se contienen. Una clase será llamada “normal” si, y solamente si, no se contiene a sí misma como miembro; en otro caso se la llamará “no normal”. Un ejemplo de clase normal es la de los lógicos, ya que, evidentemente, la clase misma no es un lógico y, por tanto, no es un miembro de si misma. Un ejemplo de clase no normal es la clase de todas las cosas pensables, ya que la clase de todas las cosas pensables es, a su vez, pensable y, por consiguiente, un miembro de sí misma. Sea “N”, por definición, la clase de todas las clases normales. Preguntamos si N mismo es una clase normal. Si N es normal, es un miembro de sí misma (pues, por definición, N contiene a todas las clases normales); pero, en este caso, N es no normal, porque, por definición, una clase que se contiene a sí misma es no normal. Por otra parte, si N es no normal, es un miembro de sí misma (por la definición de no normal); pero, en este caso, N es normal, porque, por definición, los miembros de N son las clases normales. En resumen, N es normal, si y solamente si, N es no normal. De lo que se desprende que la afirmación “N es normal” es verdadera y falsa a la vez.

1.1 Hilbert: crítica de la evidencia. El criterio de verdad de un axioma como ausencia de contradicción lógica

La idea fundamental de Hilbert estriba en que la geometría euclidiana no es la prescripción del espacio físico, ni de la intuición espacial humana (como sostenía Kant), ni de ninguna realidad concreta. En definitiva, la geometría euclídea no es una historia, sino una teoría, la descripción de una estructura que puede realizarse o no realizarse en el espacio físico, en la intuición humana, etc. Por eso puede haber tantas geometrías distintas e incompatibles entre sí, tantas como estructuras abstractas seamos capaces de definir, con independencia de cualquier realidad. Y esta situación no implica contradicción ninguna, pues los teoremas de que se compone la teoría no son verdaderos ni falsos, a diferencia de las ideas de que se compone la historia, que sí son verdaderas en o falsas.

Hilbert llego en sus Fundamentos de la geometría hasta el punto de renunciar a la evidencia como criterio de verdad. A los conceptos básicos de la geometría euclidiana, como pueden ser los de punto, recta, plano, corresponden meras variables “x”, “y”, “z”, cuyos contenidos no se precisan, sino que en principio pueden interpretarse a discreción.

Hilbert separa lo lógico-formal de lo manifiesto y evidente y declara como criterio de verdad y existencia (lógica) la ausencia de contradicción lógica. De modo que cuando los axiomas arbitrariamente establecidos no se contradicen entre sí con el conjunto de las consecuencias, quiere decirse que son verdaderos y por tanto existen las cosas definidas por los axiomas. Ese es para Hilbert el criterio de verdad y existencia.

Sólo en un segundo paso añade también una semántica a los términos básicos y a los axiomas como, por ejemplo, el significado de “punto”, “recta” y “plano” o el de los axiomas euclidianos, aunque ciertamente sin el axioma de las paralelas.

Ahora bien, la renuncia a la evidencia como criterio de verdad tiene una consecuencia importante. Mientras que con la evidencia aún se creía poder afirmar que un axioma era evidente en el sentido de verdadero “en sí”, ahora ya no se puede afirmar que un axioma es verdadero “en sí”, sino que sólo es verdadero dentro de la comunidad lingüística que acepta dicho axioma. Asimismo un teorema sólo es verdadero dentro del lenguaje del correspondiente sistema axiomático. La validez universal de la verdad de unos axiomas se limita así a la comunidad lingüística de los matemáticos que comparten esas afirmaciones y su semántica.

Pero es posible ir un poco más allá. Los axiomas no tienen que ser unas afirmaciones hechas arbitrariamente. En efecto, tan pronto como a esos signos sintácticos les asignamos una semántica y ésta es aceptada por una comunidad lingüística, tales asignaciones constituyen ya las reglas semánticas de una comunidad lingüística, y tan pronto como tales reglas se han estabilizado, se convierten en las instituciones semánticas de una comunidad lingüística. Eso significa que el criterio de la verdad de unos axiomas no debe ser su mera evidencia ni su fijación libre de contradicciones, sino que también puede serlo el hecho social de su aceptación semántica estabilizada.

Hilbert propuso que se considerasen las matemáticas como una ciencia en la que habría que distinguir tres niveles. El primer nivel es el práctico cotidiano, cuyo valor es esencialmente pragmático más que verdaderamente matemático. En este nivel se expresan las teorías informales que los matemáticos, físicos u otros científicos usan en su trabajo diario. En un segundo nivel están los sistemas formales que representan simbólicamente estas teorías. Las teorías axiomatizadas son “traducidas” a un sistema formal de símbolos, es decir, a un conjunto de objetos físicos con reglas combinatorias rigurosas y exhaustivas de formación y derivación. Las tesis informales tienen ahora sus correlatos (si el sistema es completo) en los axiomas y teoremas expresados formalmente. Los sistemas formales se constituyen así en un dominio de objetos abstractos independientes de su significado intuitivo de los que se ocupa propiamente la matemática.

La filosofía hilbertiana se resume en las tesis de que las matemáticas son una ciencia independiente acerca de estos sistemas formales y en la prescripción de que solamente son aceptables las pruebas metamatemáticas constructivas, es decir, las que se reducen a operaciones recursivas que no empleen infinitos actuales.

2. Pruebas absolutas de consistencia

Las limitaciones inherentes a la utilización de modelos para demostrar la consistencia y la creciente aprensión de que las formulaciones clásicas de muchos sistemas pudiesen albergar contradicciones internas condujeron a nuevas formas de abordar el problema. Hilbert propuso una alternativa a las pruebas relativas de consistencia. Trató de construir pruebas “absolutas” con las que pudiera demostrarse la consistencia de los sistemas sin necesidad de dar por supuesta la consistencia de algún otro sistema.

El primer paso en la construcción de una prueba absoluta es la completa formalización de un sistema deductivo. Esto significa la extracción de todo significado de las expresiones existentes dentro del sistema. Se las debe considerar, simplemente, como signos vacíos. La forma en que se deben manipular y combinar estos signos ha de ser plasmada en un conjunto de reglas enunciadas con toda precisión. La finalidad de este procedimiento estriba en construir un sistema de signos (llamado un “cálculo”) que no oculte nada y que solamente contenga lo que expresamente se haya puesto en él. Los postulados y los teoremas de un sistema completamente formalizado son “hileras” (o sucesiones de longitud finita) de signos carentes de significado construidas conforme a las reglas establecidas para combinar los signos elementales del sistema hasta formar más amplios conjuntos. Cuando un sistema ha sido completamente formalizado, la derivación de teoremas a partir de los postulados se limita, simplemente, a la transformación (siguiendo la regla) de un conjunto de estas “hileras” en otro conjunto de “hileras”. De esta manera se elimina el peligro de utilizar cualesquiera reglas no declaradas de razonamiento. Cuando un sistema ha sido formalizado quedan a la vista las relaciones lógicas existentes entre las proposiciones; pueden verse los módulos estructurales de las diversas “hileras” de signos “carentes de significado”, cómo permanecen unidas, cómo se combinan, cómo se alojan una en otra, etc.

Una página entera cubierta con signos “carentes de significado” no afirma nada; es, simplemente, el diseño abstracto de un mosaico que posee una determinada estructura. Sin embargo, es perfectamente posible describir las configuraciones de un sistema así y formular declaraciones acerca de las configuraciones y de sus diversas relaciones mutuas. Estas declaraciones poseen significado y pueden suministrar información importante acerca del sistema formal. No obstante, tales declaraciones significativas acerca de un sistema carente de significado (o formalizado) no pertenecen plenamente a dicho sistema. Pertenecen a la “metamatemática”, o a la “metalógica” (depende de qué estemos hablando). Las declaraciones metamatemáticas, o metalógicas, son declaraciones acerca de los signos existentes dentro de un sistema lógico formalizado (es decir, un cálculo), acerca de las especies y disposición de tales signos cuando se combinan para formar hileras más largas de signos llamadas “fórmulas”, o acerca de las relaciones entre fórmulas que pueden obtenerse como consecuencia de las reglas de manipulación establecidas para ellas.

El valor de la distinción entre lógica y metalógica, o entre matemática y metamatemática, radica en que da origen a una minuciosa codificación de los diversos signos que entran en la composición de un cálculo formal, libre de engañosas suposiciones y de irrelevantes asociaciones de ideas. Exige, además, disponer de definiciones exactas de las operaciones y de las reglas lógicas de la construcción y la deducción matemática.

Hilbert captó el núcleo de la cuestión y basó su intento de construir pruebas “absolutas” de consistencia en la distinción entre un cálculo formal y su descripción. Trató de desarrollar un método que produjera demostraciones de consistencia tan ajenas a una auténtica duda lógica como el uso de modelos finitos para demostrar la consistencia de ciertos conjuntos de postulados, y ello mediante el análisis de un número finito de características estructurales de las expresiones contenidas en cálculos completamente formalizados. El análisis consiste en anotar los diversos tipos de signos que se dan en un cálculo, indicar cómo combinarlos en fórmulas, prescribir cómo pueden obtenerse nuevas fórmulas a partir de otras y determinar si fórmulas de una determinada clase pueden derivarse de otras mediante reglas operativas explícitamente enunciadas. Hilbert creía posible presentar cualquier cálculo matemático como una especie de esquema “geométrico” de fórmulas, en el que las fórmulas se relacionaran mutuamente en número finito de relaciones estructurales. Esperaba demostrar, examinando exhaustivamente estas propiedades estructurales de las expresiones encerradas en un sistema, que no pueden obtenerse fórmulas formalmente contradictorias a partir de los axiomas de cálculos dados. Requisito esencial del programa de Hilbert era que las demostraciones de consistencia implicaran únicamente procedimientos que no hicieran referencia ni a un número infinito de propiedades estructurales de fórmulas ni a un número infinito de operaciones con fórmulas. Tales procedimientos son denominados “finitistas”, y una prueba de consistencia que se halle en adecuación a dicho procedimiento recibe el nombre de “absoluta”. Una prueba absoluta logra sus objetivos utilizando un mínimo de principios de deducción y no presupone la consistencia de ningún otro conjunto de axiomas. Una prueba absoluta de consistencia de la lógica de primer orden, si pudiera construirse alguna, demostraría, pues, mediante un procedimiento metalógico, que dos fórmulas contradictorias, tales como A Ù B y su negación ¬(A Ù B), no pueden derivarse de los axiomas mediante reglas explícitamente enunciadas.

3. Construcción de un sistema formal

La construcción de un sistema formal de lógica se lleva a cabo en cuatro fases que, convenientemente numeradas, son:

1. Se prepara un catálogo completo de los signos que se han de usar en el cálculo. Estos signos son nuestro vocabulario

2. Se establecen las reglas de formación de fórmulas. Estas reglas declaran qué combinaciones de signos del vocabulario pueden ser aceptadas como “fórmulas”. Las reglas pueden ser consideradas como constitutivas de la gramática del sistema

3. Se expresan las reglas de transformación que describen la estructura precisa de las fórmulas de las cuales pueden derivarse otras fórmulas de estructura determinada. Estas reglas son las reglas de deducción.

4. Se seleccionas ciertas fórmulas como axiomas (o “fórmulas primitivas”). Estas fórmulas sirven de fundamento a todo el sistema.

Un “teorema del sistema” es cualquier fórmula que pueda ser derivada de los axiomas aplicando sucesivamente las reglas de transformación. Una “prueba” es una serie finita de fórmulas, cada una de las cuales o es un axioma o puede ser derivada de otras fórmulas anteriores de la serie mediante las reglas de transformación.

Para la lógica de proposiciones, el vocabulario es muy sencillo. Se compone de variables y de signos constantes. Las variables pueden ser sustituidas por sentencias o proposiciones y reciben por ello el nombre de “variables sentenciales” o “variables proposicionales”. Son las letras

‘p’, ‘q’, ‘r’, …

Los signos constantes son “enlaces proposicionales” o signos de puntuación. En la lógica de proposiciones estos signos son:

‘¬’ que quiere decir ‘no’ y cuya interpretación semántica podría definirse como sigue: el signo ¬ representa la negación de la proposición que le sigue. Así, si la proposición es verdadera, la proposición negada será falsa, y viceversa.

‘Ù’ que quiere decir ‘y’ y cuya interpretación es: una conjunción afirma la verdad de sus componentes. Es verdadera, pues, cuando sus dos componentes son verdaderos; cuando uno de ellos es falso, y por tanto, también cuando los dos son falsos, la conjunción es falsa.

‘Ú’ que quiere decir ‘o’, y cuya interpretación es la siguiente: la disyunción de dos proposiciones es verdadera cuando una al menos de esas dos proposiciones es verdadera – y, por supuesto, cuando ambas lo son -; es falsa, en cambio, sólo cuando ambas son falsas. Las condiciones de verdad de la disyunción son la imagen invertida de las condiciones de verdad de la conjunción. Para probar la verdad de una conjunción hace falta probar la de todos y cada uno de sus miembros; para probar la verdad de la disyunción, basta probar la de uno. Lo mismo ocurre con la falsedad: la falsedad de una conjunción se establece con sólo probar la de uno de sus miembros; mientras que la falsedad de una disyunción requiere probar la de todos y cada uno de sus elementos.

‘®’ que quiere decir “si… entonces…’. Su interpretación es: una implicación es verdadera siempre que no se dé el caso de que el antecedente sea verdadero y el consecuente falso; y falsa cuando ese sea el caso.

La interpretación de estos signos de la lógica proposicional se suele dar más abreviadamente mediante lo que se conoce como tablas de verdad. La tabla de verdad de los cuatro símbolos de nuestro cálculos es la siguiente:

Los signos de puntuación son los paréntesis de apertura y cierre.

Las reglas de formación de fórmulas son las siguientes:

  • Cualquier variable proposicional es una fórmula
  • Si S es una fórmula, ¬ S también es una fórmula

Si S y P son fórmulas, también lo son S Ù P, S Ú P y S ® P.

A continuación, adoptamos dos reglas de transformación:

· Regla de sustitución: de una fórmula que contenga variables sentenciales puede siempre derivarse otra fórmula sustituyendo uniformemente con fórmulas las variables.

· Regla de separación: De dos fórmulas que tengan la forma S y S ® P se puede derivar la fórmula P. A esta regla también se la conoce como Modus Ponens.

Finalmente, adoptaremos como axiomas de cálculo los siguientes:

1.

(pÚp) ® p

Si (los Beatles eran ingleses, o los Beatles eran ingleses), entonces los Beatles eran ingleses

2

p ® (pÚq)

Si yo soy listo, entonces (o yo soy listo o el Real Madrid gana la liga)

3

(pÚq) ® (qÚp)

Si (o Kant era puntual o la Iglesia es estúpida), entonces (o la Iglesia es estúpida o Kant era puntual)

4

(p®q)® ((rÚp)®(rÚq))

Si (si me gusta el whisky entonces pierdo al mús), entonces (si (o escucho a los Rolling Stones o me gusta el whisky) entonces (o escucho a los Rolling Stones o pierdo al mús))

Atendiendo a los ejemplos, es importante señalar que aunque los consecuentes no guarden relación con los antecedentes, esto no afecta en modo alguno a la validez de las conexiones lógicas establecidas en los mencionados ejemplos.

Con ayuda de las reglas de transformación mencionadas anteriormente es posible derivar, a partir de estos axiomas aparentemente triviales, una clase infinitamente grande de teoremas que no tienen nada de triviales como, por ejemplo, la fórmula:

((p®q)®((r®s)®t))®((u®((r®s)®t))®((p®u)®(s®t)))

Demostrar la consistencia de este sistema axiomático es demostrar que es imposible derivar, a partir de los axiomas, una fórmula y su negación, pues si tanto una fórmula como su negación fuesen deducibles de los axiomas, sería también deducible cualquier fórmula. Es decir, si el cálculo no es consistente, toda fórmula es un teorema, lo que equivale a decir que de un conjunto contradictorio de axiomas puede ser derivada cualquier fórmula. Esto tiene una contrapartida: si no toda fórmula es un teorema, entonces el cálculo es consistente. Lo que hace falta, por consiguiente, es demostrar que existe por lo menos una fórmula que no puede ser derivada de los axiomas.

La forma de hacerlo es emplear un razonamiento metalógico sobre el sistema. El procedimiento consiste en encontrar una característica o propiedad estructural de las fórmulas que satisfaga las tres condiciones siguientes: 1) la propiedad debe ser común a todos los axiomas; 2) la propiedad debe ser “hereditaria”, según las reglas de transformación, esto es, si todos los axiomas poseen la propiedad, cualquier fórmula adecuadamente derivada de ellos mediante las reglas de transformación debe poseerla también. Puesto que cualquier fórmula derivada es por definición un teorema, esta condición estipula en esencia que todo teorema debe poseer esa propiedad; 3) la propiedad no debe pertenecer a toda fórmula que pueda construirse de acuerdo con las reglas de formación del sistema; esto es, debemos tratar de encontrar al menos una fórmula que no posea esa propiedad. Si tenemos éxito en esta triple tarea habremos conseguido una prueba absoluta de consistencia. El razonamiento es el siguiente: la propiedad hereditaria se transmite desde los axiomas a todos los teoremas; pero si puede encontrarse un conjunto de signos que sea adecuado a las exigencias de ser una fórmula del sistema y que, sin embargo, no posea esa determinada propiedad hereditaria, tal fórmula no puede ser un teorema. Pero si descubrimos una fórmula que no es un teorema hemos demostrado la consistencia del sistema, ya que si el sistema no fuese consistente, todas las fórmulas podrían ser derivadas de los axiomas. Por tanto, lo que se necesita es encontrar una sola fórmula que carezca de la propiedad hereditaria.

Una propiedad del tipo requerido es la de ser una “tautología”. En el lenguaje corriente se dice que una expresión es tautológica si contiene una redundancia y manifiesta dos veces la misma cosa con diferentes palabras. En la lógica se define la tautología como una proposición que no excluye ninguna posibilidad lógica; es decir, una tautología es “verdadera en todos los mundos posibles”.

Una fórmula es una tautología si es invariablemente verdadera, independientemente de que sus componentes elementales sean verdaderos o falsos. Una forma de mostrar que nuestros cuatro axiomas son tautologías es utilizando las tablas de verdad. En una tabla de verdad una fórmula es una tautología si en la columna que contiene la fórmula completa sólo hay signos V

4. Completud del cálculo de predicados

Puesto que todo teorema del cálculo de predicados es una tautología, una verdad de la lógica, podemos preguntar si, inversamente, toda verdad lógica susceptible de ser expresada en el vocabulario de nuestro sistema (es decir, toda tautología) es también un teorema (esto es, derivable de los axiomas). Si la respuesta es afirmativa, ello querrá decir que los axiomas son suficientes para engendrar todas las fórmulas tautológicas, todas las verdades lógicas susceptibles de ser expresadas en el sistema; es decir, que nuestro sistema es “completo”. La completud es una propiedad interesante en un sistema axiomático porque ella nos asegura que no hay ninguna verdad en nuestro sistema que nosotros no seamos capaces de encontrar. Dicho de otro modo, un sistema “incompleto” no sería muy útil porque, lo mismo que los jueces, el lógico quiere conseguir la verdad, toda la verdad y nada más que la verdad. Pero solo podremos estar seguros de poder alcanzar toda la verdad si nuestro sistema es completo.

Se llama “completo” a un cálculo, C, si dada una fórmula bien formada, f, de C, o esta fórmula o su negación (¬f) es un teorema de C. Se llama también “completo” a un cálculo C cuando hay otro cálculo C’ tal, que C es inconsistente cuando C’ es igual a C excepto por contener una fórmula que no es susceptible de prueba en C.

5. Las limitaciones de los sistemas formales

El cálculo proposicional constituye un ejemplo de un sistema matemático en el que se alcanzan plenamente los objetivos de la teoría de la demostración de Hilbert. Este cálculo codifica solamente un fragmento de la lógica formal, y su vocabulario y su aparato formal no son suficientes para desarrollar ni siquiera la aritmética elemental, pero el programa de Hilbert no es tan limitado. Puede ser aplicado con éxito a sistemas más amplios, cuyo carácter, a la vez consistente y completo, puede ser demostrado mediante un razonamiento metamatemático. Pero ¿es el método finitista de Hilbert lo suficientemente potente como para demostrar la consistencia de un sistema como Principia, cuyo vocabulario y cuyo aparato lógico son adecuados para expresar toda la aritmética y no simplemente un fragmento de ella?. La publicación en 1931 del artículo de Kurt Gödel Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas afines demostró que no podían por menos de fracasar todos los esfuerzos que se desenvolvieran dentro de los estrictos límites del primitivo programa de Hilbert.

¿Qué es lo que estableció Gödel?. Sus principales conclusiones son dos: en primer lugar, demostró que es imposible presentar una prueba metamatemática de la consistencia de un sistema lo bastante comprensivo como para contener toda la aritmética, a menos que se empleen en la prueba reglas de deducción que difieran en ciertos aspectos esenciales de las reglas de transformación utilizadas para derivar teoremas dentro del sistema. Lo que Gödel demostró es que es imposible que pueda darse una prueba finitista de la consistencia de la aritmética; ahora bien, si la prueba no es finitista, no cubre los objetivos del programa de Hilbert.

La segunda conclusión de Gödel demuestra la existencia de una fundamental limitación en la potencia del método axiomático. Gödel demostró que los Principia, o cualquier otro sistema dentro del cual pueda desarrollarse la aritmética, es esencialmente incompleto, es decir, dado cualquier conjunto consistente de axiomas aritméticos, existen proposiciones aritméticas verdaderas que no pueden ser derivadas de dicho conjunto.

Veámoslo con un ejemplo. Las matemáticas abundan en proposiciones generales a las que no se ha encontrado ninguna excepción que hasta ahora haya frustrado todo intento de prueba; una de ellas es el “teorema de Goldbach”, según el cual todo número par es la suma de dos números primos. Jamás se ha encontrado ningún número par que no sea la suma de dos números primos; sin embargo, nadie ha logrado encontrar una prueba de que la conjetura de Goldbach se aplique sin excepción a todos los números pares. Es esta, pues, una proposición aritmética que puede ser verdadera, pero que no puede ser derivada de los axiomas de la aritmética.

Supongamos que sea universalmente verdadera. ¿Qué decir ante la sugerencia de que los axiomas podrían ser modificados o aumentados hasta hacer que las proposiciones hasta el momento indemostrables fuesen derivables en el sistema ampliado?. Los resultados de Gödel muestran que, aun cuando los axiomas de la aritmética fuesen ampliados con un número indefinido de otros axiomas verdaderos, siempre quedarán verdades aritméticas que no son formalmente derivables del conjunto ampliado.

¿Cómo demostró Gödel esto?. La estructura de su argumentación está moldeada sobre el razonamiento implicado en la “paradoja richardiana”, propuesta por el matemático francés Jules Richard en 1905.

Considérese un lenguaje en el que se puedan formular y definir las propiedades puramente aritméticas de los números cardinales. Resulta claro que, so pena de caer en un círculo vicioso, no pueden definirse explícitamente algunos términos que hacen referencia a propiedades aritméticas – ya que no podemos definirlo todo y debemos empezar en alguna parte -. La propiedad de ser un número primo puede ser definida como “no divisible por ningún otro número más que por sí mismo y la unidad”; la propiedad de ser un cuadrado perfecto puede ser definida como “ser el producto de algún número entero por sí mismo”, etc.

Cada una de tales definiciones contendrá solamente un número finito de palabras y sólo un número finito de letras del alfabeto. Así, las definiciones pueden ser ordenadas en una serie: una definición precederá a otra si el número de letras de la primera es menor que el número de letras de la segunda; y si dos definiciones tienen el mismo número de letras, una de ellas precederá a la otra atendiendo al orden alfabético de las letras contenidas en cada una. De este modo, a cada definición corresponderá un único número entero, que representará el lugar que ocupa la definición en la serie.

Dado que cada definición está asociada a un único número entero, puede ocurrir en algunos casos que un número entero posea la misma propiedad expresada por la definición con la cual está asociado. Supongamos que la expresión definidora “no ser divisible por ningún número entero más que por sí mismo y la unidad” se halla en correlación con el número 17; evidentemente, el 17 tiene la propiedad designada por esa expresión. Por otra parte, supongamos que la expresión definidora “ser el producto de algún número entero por sí mismo” se halla en correlación con el número 15; está claro que 15 no posee la propiedad designada por la expresión. Describimos la situación del segundo ejemplo diciendo que el número 15 tiene la propiedad de ser richardiano, y la del primer ejemplo, diciendo que el número 17 no tiene la propiedad de ser richardiano. Es decir, “x es richardiano, sii x no tiene la propiedad designada por la expresión definidora con la que se halla relacionado en la serie ordenada de definiciones”.

Ahora bien, la expresión definidora de ser richardiano describe una propiedad numérica de los enteros. La expresión misma pertenece, por tanto, a la serie de definiciones ya enunciadas antes. De aquí se desprende que la expresión está relacionada con un cierto número entero. Supongamos que este número es n. ¿Es n richardiano?. La conclusión es contradictoria, pues n es richardiano sii, n carece de la propiedad designada por la expresión (definidora) con la que está relacionado. Es decir, n es richardiano sii n no es richardiano.

Podemos dar de lado a esta paradoja distinguiendo entre las proposiciones que se producen dentro de la aritmética y las proposiciones acerca de algún sistema de notación en el que se codifica esa aritmética. La construcción de esta paradoja sugiere la posibilidad de que se pueden “representar” declaraciones metamatemáticas acerca de un sistema formal suficientemente amplio dentro del sistema mismo.

La característica fundamental de la representación es que puede demostrarse que una estructura abstracta de relaciones existente en un campo de “objetos” existe también entre “objetos” pertenecientes a otro campo diferente. Esta característica es lo que impulsó a Gödel a construir sus pruebas. Si, como él esperaba, unas complicadas proposiciones metamatemáticas acerca de un sistema formalizado pudiesen ser traducidas a (o reflejadas por) proposiciones aritméticas contenidas dentro del propio sistema, se habría dado un gran paso en el camino de facilitar las demostraciones metamatemáticas.

La explotación de la idea de la representación es la clave de la argumentación de Gödel. Gödel demostró que las proposiciones metamatemáticas acerca de un cálculo aritmético formalizado pueden efectivamente ser representadas por fórmulas aritméticas dentro del cálculo. Ideó un método de representación tal, que ni la fórmula aritmética correspondiente a una determinada proposición metamatemática verdadera acerca de la fórmula ni la fórmula aritmética correspondiente a la negación de la proposición son demostrables dentro del cálculo. Comoquiera que una de estas fórmulas aritméticas debe codificar una verdad aritmética, ninguna de las cuales es, sin embargo, derivable de los axiomas, los axiomas son incompletos. Este método de representación le permitió construir una fórmula aritmética correspondiente a la proposición metamatemática “el cálculo es consistente” y demostrar que esta fórmula no es demostrable dentro del cálculo. De ahí se desprende que la proposición metamatemática no puede ser demostrada a no ser que se utilicen reglas de deducción que no puedan ser representadas dentro del cálculo, de tal modo que, al demostrar la proposición, se deben emplear reglas cuya propia consistencia pueda ser tan discutible como la consistencia misma de la aritmética

6. Las pruebas de Gödel

6.1 La numeración de Gödel

Gödel describió un cálculo formalizado dentro del cual pueden expresarse todas las acostumbradas notaciones aritméticas ya conocidas. Las fórmulas del cálculo están constituidas con una clase de signos elementales que constituyen el vocabulario fundamental. Los cimientos están formados por un conjunto de fórmulas primitivas, y los teoremas del cálculo son fórmulas.

Gödel demostró que es posible asignar un único número a cada signo elemental o a cada fórmula (o sucesión de signos) y a cada prueba (o sucesión finita de fórmulas). Este número recibe el nombre de “número de Gödel” del signo, fórmula o prueba.

Los signos elementales son de dos clases: constantes y variables. Supondremos que hay diez signos constantes, a los que se asocian, como número de Gödel, los números enteros del 1 al 10.

Tabla de signos constantes

Además de los signos elementales constantes, aparecen tres clases de variables en el vocabulario fundamental del cálculo: 1) las variables numéricas, ‘x’, ‘y’, ‘z’; 2) las variables sentenciales, ‘p’, ‘q’, ‘r’, y 3) las variables predicativas ‘P’, ‘Q’, ‘R’. A estas variables se asignan números de Gödel de acuerdo a las siguientes reglas: a) a cada variable numérica, un número primo mayor que 10; b) a cada variable sentencial el cuadrado de un número primo mayor que 10; y c) a cada variable predicativa el cubo de un número primo mayor que 10.

Tabla de signos variables

Consideremos ahora una fórmula del sistema, por ejemplo, ($x)(x=sy). Los números asociados a sus diez signos elementales son

Es deseable, sin embargo, asimilar a la fórmula un solo número en vez de un conjunto de números. Convenimos en asociar a la fórmula el único número que es el producto de los diez primeros números primos en orden de magnitud, estando cada uno de ellos elevado a una potencia igual al número Gödel del correspondiente signo elemental. Así, la fórmula anterior queda asociada al número

28´34´511´79´1311´175´197´2313´299

llamemos m a este número. De manera similar, se puede asignar a toda sucesión finita de signos elementales y, en particular, a toda fórmula, un único número, el producto de tantos números primos como signos haya.

Consideremos ahora la fórmula ($x)(x=s0), y supongamos que su número de Gödel es n. Tenemos así la sucesión de fórmulas

($x)(x=sy)
($x)(x=s0)

cuyos números de Gödel son, respectivamente, m y n. Igual que antes, es conveniente disponer de un solo número que sirva de rótulo a la sucesión. Convenimos en asociarla con el número que es el producto de los dos primeros números primos en orden de magnitud, estando elevado cada uno de los números primos a una potencia igual al número de Gödel de la fórmula correspondiente. Si llamamos k a ese número podemos escribir K = 2m ´ 3n. Por este procedimiento de condensación podemos obtener un número para cada serie de fórmulas. En resumen, toda expresión contenida en el sistema, sea un signo elemental, una sucesión de signos, o una sucesión de sucesiones, puede llevar asignado un único número de Gödel.

Con ello, hemos aritmetizado completamente el cálculo formal, dando un conjunto de reglas para establecer una correspondencia biunívoca entre las expresiones del cálculo y una cierta subclase de los números enteros.

6.2 La aritmetización de la metamatemática

El paso siguiente de Gödel es demostrar que todas las proposiciones metamatemáticas acerca de las propiedades estructurales de las expresiones contenidas en el cálculo pueden ser adecuadamente reflejadas dentro del cálculo mismo. La idea básica es: puesto que toda expresión del cálculo está asociada a un número, puede construirse una proposición metamatemática acerca de las expresiones y de sus recíprocas relaciones como una proposición acerca de los correspondientes números y de sus recíprocas relaciones aritméticas. De esta manera queda completamente aritmetizada la metamatemática.

Cada proposición metamatemática se halla representada por una única fórmula dentro de la aritmética; y las relaciones de dependencia lógica entre las proposiciones metamatemáticas se reflejan plenamente en las relaciones numéricas de dependencia entre sus correspondientes fórmulas aritméticas. La exploración de las cuestiones metamatemáticas puede ser desarrollada investigando las propiedades aritméticas y las relaciones de ciertos números enteros.

Como ejemplo, consideremos un axioma del sistema formal sujeto a examen: ‘(pÚp)®p’. Supongamos que su número de Gödel es ‘a’. Consideremos también la fórmula ‘(pÚp)’, y supongamos que su número de Gödel es ‘b’. Enunciamos ahora la proposición metamatemática de que la fórmula ‘(pÚp)’ es una parte inicial del axioma. ¿A qué fórmula aritmética del sistema formal corresponde esta proposición?. Es evidente que la fórmula más pequeña ‘(pÚp)’ puede ser una parte inicial de la fórmula mayor, que es el axioma, sii el número de Gödel, b, que representa a la primera es un factor del número de Gödel, a, que representa a la segunda. Supuesto que la expresión ‘factor de’ esté convencionalmente definida en el sistema aritmético formalizado, la única fórmula aritmética que corresponde a la declaración metamatemática antes enunciada es ‘b es un factor de a’. Si esta fórmula es verdadera, es cierto que ‘(pÚp)’ es una parte inicial de ‘(pÚp)®p’.

Fijemos ahora nuestra atención en la fórmula metamatemática: «La sucesión de fórmulas con número de Gödel x es una prueba de la fórmula con número de Gödel z». Esta declaración está representada por una fórmula definida del cálculo aritmético que expresa una relación entre x y z. Escribimos esta relación entre x y z con la fórmula ‘Dem(x,z)’, para tener presente la proposición metamatemática a la que corresponde (la sucesión de fórmulas con número de Gödel x es una prueba de la fórmula con número de Gödel z).

Una proposición metamatemática que dice que una cierta sucesión de fórmulas constituye una prueba de que una fórmula dada es verdadera sii el número de Gödel de la pretendida prueba están con el número de Gödel de la conclusión en la relación aritmética designada como ‘Dem’. Por consiguiente, para establecer la verdad o la falsedad de la proposición metamatemática sujeta a examen sólo nos interesa la cuestión de si la relación Dem se mantiene entre dos números. Análogamente, la proposición metamatemática ‘La sucesión de fórmulas con el número de Gödel x no es una prueba para la fórmula con número de Gödel z’ se representa en el sistema aritmético formalizado con una fórmula definida. Tal fórmula es la contradictoria de ‘Dem(x,z)’, o sea, ‘¬Dem(x,z)’.

La fórmula ‘($x)(x=sy) tiene como número de Gödel m, mientras que el número de Gödel de la variable ‘y’ es 13. Si en dicha fórmula sustituimos el número de Gödel 13 por el numeral m, el resultado es la fórmula ‘($x)(x=sm)’, que dice que existe un número x tal que x es el sucesor inmediato de m. Esta fórmula también tiene un número de Gödel que se puede calcular; pero en vez de hacer el cálculo podemos identificar el número mediante una caracterización metamatemática: es el número de Gödel de la fórmula que se obtiene a partir de la fórmula de número de Gödel m, sustituyendo la variable de número de Gödel 13 por el numeral de m. Esta caracterización metamatemática determina unívocamente un número definido, que es una cierta función aritmética de los números m y 13, en la que puede ser expresada la función misma dentro del sistema formalizado. El número puede ser designado dentro del cálculo. Esta designación será escrita como ‘sust(m,13,m)’ siendo la finalidad de esta forma recordar la caracterización metamatemática que representa, es decir, ‘el número de Gödel de la fórmula obtenida a partir de la fórmula de número de Gödel m, sustituyendo la variable de número de Gödel 13 por el numeral de m’.

La expresión ‘sust(y,13,y) es la imagen reflejada dentro del cálculo aritmético formalizado de la caracterización metamatemática ‘el número de Gödel de la fórmula que se obtiene a partir de la fórmula de número de Gödel y, sustituyendo la variable de número de Gödel 13 por el numeral de y’. Cuando se sustituye ‘y’ por un numeral definido en ‘sust(y,13,y) la expresión resultante designa un número entero definido, que es el número de Gödel de una determinada fórmula.

6.3 La argumentación de Gödel

Gödel mostró:

1. cómo construir una fórmula aritmética G que represente la declaración metamatemática ‘La fórmula G no es demostrable’. La fórmula ‘¬Dem(x,z)’ representa, dentro de la aritmética formalizada, la proposición metamatemática ‘la sucesión de fórmulas con número de Gödel x no es una prueba de la fórmula con número de Gödel z’. Ahora introducimos el prefijo (x) en la fórmula Dem. Este prefijo equivale a la frase ‘para todo x’. Anteponiendo este prefijo obtenemos la fórmula ‘(x)¬Dem(x,z)’, que equivale a ‘para todo x, la sucesión de fórmulas con número de Gödel x no es una prueba de la fórmula con número de Gödel z’. Esta fórmula es la paráfrasis de ‘la fórmula con número de Gödel z no es demostrable’. Lo que Gödel demostró es que un determinado caso especial de esta fórmula no es formalmente demostrable

2. Gödel mostró también que G es demostrable sii es demostrable su negación formal ¬G. Si una fórmula y su negación son ambas formalmente demostrables, el cálculo aritmético no es consistente. Por consiguiente, si el cálculo es consistente, ni G ni ¬G son formalmente derivables de los axiomas de la aritmética. Por tanto, si la aritmética es consistente, G es una fórmula formalmente indecidible.

3. Gödel también mostró qQue aunque G no sea formalmente demostrable es, sin embargo, una fórmula aritmética verdadera. Es verdadera en el sentido de que afirma que todo número entero posee una cierta propiedad aritmética que puede ser exactamente definida y presentada en cualquier número entero que se examine.

4. Puesto que G es al mismo tiempo verdadera y formalmente indecidible, los axiomas de la aritmética son incompletos: no podemos deducir todas las verdades aritméticas de los axiomas. Gödel demostró además que la aritmética es esencialmente incompleta: aun cuando se admitiesen nuevos axiomas, de tal modo que la fórmula verdadera G pudiera ser formalmente derivada de la incrementada serie de los mismos, todavía podría construirse otra fórmula verdadera pero formalmente indecidible.

5. Gödel describió cómo construir una fórmula aritmética A que represente a la proposición metamatemática ‘la aritmética es consistente’, y demostró que la fórmula ‘A®G’ es demostrable. De aquí se desprende que la consistencia de la aritmética no puede ser establecida por un argumento que pueda hallarse representado en el cálculo aritmético formal.

7. Otros resultados referentes a los fundamentos de la lógica y las matemáticas

Como acabamos de ver, en 1931 Gödel demostró que en un sistema formal (lógico o matemático) que sea consistente y en cuyo interior se pretenda desarrollar acabadamente la lógica o la matemática, existen proposiciones de dicho sistema que son indecidibles, esto es, que ni su afirmación ni su negación son demostrables, siendo una de ellas, precisamente, la que afirma que el sistema es consistente. Sin embargo, no es este el único resultado importante que se ha logrado en este siglo en lo que hace referencia al fundamento de la lógica y las matemáticas. Otros resultados fundamentales han sido los siguientes:

7.1 El teorema de satisfacción de Henkin

El teorema de satisfacción de Henkin establece que “para cualquier conjunto de fórmulas (A) de lógica elemental, si A es consistente, entonces A es simultáneamente satisfacible en un modelo enumerable“. La demostración del teorema comienza extendiendo al máximo el conjunto de fórmulas “A” por adición sucesiva de toda fórmula posible que sea compatible con él, es decir, que no atente contra su consistencia. El resultado será un conjunto consistente máximo que incluye al anterior. Este conjunto no sólo es consistente, sino que además abarca toda fórmula consistente.

7.2 El teorema de completud de la lógica cuantificacional de primer orden de Gödel

En 1930 Gödel demostró la completud de la lógica cuantificacional de primer orden. Literalmente el Teorema de completud de Gödel establece: “Para toda fórmula A de la lógica cuantificacional de primer orden, si A es lógicamente verdadera, entonces A es deducible“. Dicho formalmente: “Si |= A, entonces |- A”. Esto quiere decir que el sistema formal de la lógica cuantificacional será completo si todas las fórmulas que representan verdades lógicas son formalmente deducibles en el sistema. La prueba del teorema de completud se reduce a consignar las siguientes premisas:

  1. A es lógicamente verdadera: |== A.
  2. Si A es lógicamente verdadera, entonces ¬A es insatisfacible.
  3. Si ¬A es insatisfacible, entonces ¬A es inconsistente.
  4. Si ¬A es inconsistente, entonces da lugar a contradicción: ¬A |- B y ¬A |- ¬B.
  5. Si ¬A |- B y ¬A |- ¬B, entonces |- A.

La justificación de estas premisas es la siguiente: 1) es la hipótesis del teorema de completud; 2) se sigue de la definición del concepto de fórmula lógicamente verdadera: su negación ha de ser satisfacible; 3) es la contraposición del teorema de Henkin; 4) es un mero análisis de la definición de inconsistencia, y finalmente 5) se basa en el teorema de deducción, que permite pasar de ¬A |- B y ¬A |- ¬B a |- ¬A ® B y |- ¬A ® ¬B, respectivamente, y en Modus Ponens, que permite, con ayuda de estas dos últimas fórmulas, eliminar los antecendentes en la ley de reducción al absurdo (|- (¬A ® B) ® ((¬A ® ¬B) ® ¬¬A); de |- ¬¬A se pasa a |- a mediante una aplicación de MP a la ley de doble negación |- ¬¬A ® A. Aceptadas estas premiss, se les aplica reiteradamente la regla MP, empezando por 2) y 1), siguiendo con 3) y el consecuente de 2), y así sucesivamente, hasta liberar el consecuente de 5): |- A, que es justamente la tesis del teorema de Gödel, el cual queda, por tanto, demostrado.

7.3 Teorema de Löwenheim-Skolem

Del teorema de satisfacción de Henkin se deriva como corolario el teorema de Löwenheim-Skolem: Si un conjunto de fórmulas cualquiera A es simultáneamente satisfacible en cualquier dominio no vacío, entonces es simultáneamente satisfacible en un dominio enumerable.

7.4 Teorema de compacidad

También es una consecuencia del teorema de satisfacción de Henkin. Dice así: si todo subconjunto finito de un conjunto infinito de enunciados es satisfacible, entonces ese conjunto es, todo él, satisfacible.

7.5 Indecidibilidad de la lógica cuantificacional poliádica (teorema de Church)

En 1936 Alonzo Church demostró la imposibilidad de encontrar un procedimiento mecánico decisorio adecuado para la lógica elemental, incluyendo la lógica cuantificacional poliádica. Este teorema de Church es, junto al teorema de incompletud de Gödel, uno de los denominados teoremas de limitación, que pusieron en crisis la ilimitada fe que hasta entonces se depositaba en los métodos axiomáticos y dieron lugar a una de las corrientes más fecundas de la investigación lógico-matemática: la teoría de la computabilidad.

Partiendo del teorema de Gödel, Church probó que no es posible hallar una solución general para el problema de la decisión en teoría elemental de números, es decir, que el sistema formal de la aritmética es indecidible. Church demostró que el caso general del problema de la decisión para un sistema formal de lógica elemental es insoluble, es decir: la lógica elemental de la cuantifación es indecidible (teorema de Church).

El interés fundamental de este teorema consiste en que por él se establece, o se quiere establecer, la no mecanicidad de la lógica formal. Pues si bien es cierto que existen algoritmos (procedimientos de decisión) que permiten resolver de modo mecánico grandes grupos de problemas de lógica elemental, según este teorema, no existe ni puede existir un algoritmo que los resuelva mecánicamente todos. De aquí se deduce que la operación deductiva de la razón no es totalmente mecanizable. En opinión de Church sólo existe un algoritmo que solucione un problema lógico o matemático si existe una “máquina de Turing” que pueda computerizarlo. De este modo, para Church, la mente humana es como una máquina de Türing, pero más imperfecta.

7.6 La tesis de Chuch-Turing

La tesis Church-Turing hace referencia a la noción de una método efectivo o mecánico en lógica y matemáticas. “Efectivo” y su sinónimo “mecánico” son términos cambiantes en estas disciplinas: no mantienen su significado siempre. Un método, o procedimiento, M, para alcanzar algún resultado deseado se denomina “efectivo” o “mecánico” cuando:

1. M es expresado en términos de un número finito de instrucciones exactas (cada instrucción es expresada por medio de un número finito de símbolos);

2. M debe, si no se produce ningún error, producir siempre el resultado deseado en un número finito de pasos;

3. M puede (en la práctica, o en principio) llevarse a cabo por un ser humano sin la ayuda de ninguna máquina, simplemente con papel y lápiz;

4. M no requiere ningún tipo de comprensión ni de ingenio por parte del humano que intenta resolverlo.

Un ejemplo bien conocido de un método efectivo es la tabla de verdad para la tautologicidad. En la práctica, por supuesto, este test no puede realizarse en fórmulas que contienen un número muy grande de variables proposicionales, pero en principio uno podría aplicarlo exitosamente a cualquier fórmula del cálculo proposicional, con el suficiente tiempo, tenacidad, papel y lápiz.

La afirmación de que hay un método efectivo para alcanzar tal resultado se expresa comúnmente diciendo que hay un método efectivo para obtener los valores de tal función matemática. Por ejemplo, la afirmación de que hay un método efectivo para determinar si cualquier fórmula del cálculo proposicional es o no una tautología -v.g., el método de las tablas de verdad- es expresada diciendo que hay un método efectivo para obtener los valores de una función, llamémosla T, cuyo dominio es el conjunto de fórmulas del cálculo proposicional y cuyo valor para cualquier fórmula x, escrito T(x), es 1 o 0 en función de si x es, o no, una tautología.

La noción de un método efectivo es una noción informal, y se caracteriza, tal y como se ha dicho, por la falta de rigor para el requisito clave de que el método no exija comprensión o ingenio, pues tal requisito permanece inexplicado. Uno de los logros de Turing fue presentar un predicado formalmente exacto que permitía reemplazar al predicado informal “puede ser calculado por medio de un método efectivo”. Church hizo lo mismo. Los predicados que Turing y Church proponían reemplazar eran, a simple vista, muy diferentes uno de otro, pero eran equivalentes en el sentido de que cada uno seleccionaba el mismo conjunto de funciones matemáticas. La tesis Church-Turing consiste en la aserción de que este conjunto contiene toda función cuyos valores pueden obtenerse por un método que satisfaga las anteriores condiciones de eficacia. (Ciertamente, si las funciones del predicado informal, pero no del predicado formal, fueran verdaderas, entonces el más reciente sería menos general que el anterior y por tanto no sería razonable reemplazarlo). Cuando la tesis se expresa en los términos formales propuestos por Turing es apropiado referirse a ella como la “tesis de Turing”; y mutatis mutandis en el caso de Church.

El concepto formal propuesto por Turing es el de computable por una máquina de Turing. He afirmado que si hay (Tesis de Turing) un método efectivo para obtener los valores de una función matemática, la función puede computarse en una máquina de Turing. La afirmación inversa puede establecerse fácilmente. Un programa de una máquina de Turing es una especificación de un método efectivo: un ser humano puede trabajar con las instrucciones del programa y realizar las operaciones requeridas por este sin necesidad de acudir a la comprensión o al ingenio. Si la tesis de Turing es correcta, hablar sobre la existencia o no de métodos efectivos puede reemplazarse en matemáticas y lógica por la existencia o no de programas de máquinas de Turing.

La tesis de Turing fue formulada por Turing así:

Tesis de Turing: Las MCLs [máquinas de computación lógica: la expresión de Turing para las máquinas de Turing] pueden hacer cualquier cosa que podamos describir como [un procedimiento] “puramente mecánico”. (Turing 1948:7.)

Y añadió:

Esto está tan bien establecido que es aceptado por muchos lógicos que “calculable por medio de una MCL” es el modo correcto de aludir a tales expresiones. (Ibid.)

Turing introdujo esta tesis al argumentar que el Entscheidungsproblem, o problema de la decisión, para el cálculo de predicados -planteado por Hilbert- es insoluble. He aquí la formulación de Church al Entscheidungsproblem:

Por el Entscheidungsproblem de un sistema de lógica simbólica hay que entender el problema de encontrar un método efectivo mediante el cual, dada cualquier expresión en la notación del sistema, pueda determinarse si bien Q o no Q es demostrable dentro del sistema.

El test de las tablas de verdad es un método de este tipo para el cálculo proposicional. Turing mostró que, dada su tesis, no puede haber tal método para el cálculo de predicados. Demostró formalmente que no hay ninguna máquina de Turing que pueda determinar, en un número finito de pasos, si una fórmula dada del cálculo de predicados es o no un teorema del cálculo. Así, dada la tesis de que si tal método efectivo existe, puede realizarse por una de estas máquinas, se sigue que tal método no puede encontrarse.

Church había llegado al mismo resultado negativo unos meses antes, empleando el concepto de definibilidad-lambda en lugar de computabilidad por una máquina de Turing. Church y Turing llegaron a este descubrimiento de un modo independiente uno de otro

Church usa la expresión (informal) “efectivamente calculable” para indicar que hay un método efectivo para calcular los valores de la función. Propone

Definir la noción… de una función efectivamente calculable de enteros positivos identificándola con la noción de una función recursiva de enteros positivos (o con una función lambda-definible de enteros positivos)

El concepto de función lambda-definible se debe a Church y Kleene y el concepto de función recursiva se debe a Gödel y Herbrand. La clase de las funciones lambda-definibles y la clase de las funciones recursivas son idénticas. Esto fue establecido en el caso de las funciones de enteros positivos por Church y Kleene. Una vez admitida la propuesta de Church, Turing estableció que el aparato de la lambda-definibilidad y su propio aparato de computabilidad son equivalentes. Así, en la propuesta de Church, las palabras “función recursiva de los enteros positivos” puede reemplazarse por las palabras “función de los enteros positivos computable por una máquina de Turing”.

El término “tesis Church-Turing” parece que fue introducido por Kleene, como una forma de eliminar prejuicios a favor de Church:

Por tanto, las tesis de Turing y Church son equivalentes. Normalmente nos referimos a ambas tesis como tesis de Church, o en conexión con una de sus versiones que habla de “máquinas de Turing” como tesis Church-Turing.

Se acumuló mucha evidencia a favor de la “hipótesis de trabajo” propuesta por Church y Turing en 1936. La mayor cantidad de estas evidencias fueron expuestas por C. S. Kleene: (1) Toda función efectivamente calculable que se ha investigado hasta ahora ha resultado ser computable por una máquina de Turing. (2) Todos los métodos u operaciones conocidos para obtener nuevas funciones efectivamente calculables son métodos paralelos para construir nuevas máquinas de Turing a partir de una máquina de Turing dada. (3) Todos los intentos de hacer un análisis exacto de la noción intuitiva de función efectivamente calculable han resultado ser equivalentes, en el sentido de que cada análisis ofrecido se ha realizado seleccionando la misma clase de funciones, verbigracia, las que son computables por una máquina de Turing. Debido a la diversidad de los análisis realizados, esto último se considera como una evidencia fuerte

8. El sueño roto: ¿verdad en las matemáticas?

Entre los matemáticos circula este chiste: “Dios existe porque la matemática está exenta de contradicción, y el diablo existe porque la no contradicción no se puede probar”. En efecto, doscientos años después de Descartes la matemática entró en una crisis tan radical que muchos matemáticos, pese a los pequeños éxitos, perdieron la confianza en conseguir la verdad con la matemática. Hasta entonces su progreso parecía rectilíneo, constante e irresistible. Su aplicación a la mecánica celeste, a la electricidad, a todos los sectores de las ciencias naturales y técnicas ha traído enormes progresos en la humanidad. ¿Podría hacerse realidad el sueño de Descartes de una ciencia matemática universal? Ya Leibniz trató de elaborar un lenguaje matemático unitario, postulando una characterística de la razón en virtud de la cual las verdades de razón serían alcanzables mediante el cálculo, al igual que en la aritmética y en el álgebra, aplicando un método deductivo.

La lógica matemática de los siglos XIX y XX intentó verificar la idea de Descartes y Leibniz. Pero en la segunda mitad del siglo XIX la teoría de conjuntos, base de la actual matemática, inicial por Cantor, hizo temblar la no contradicción y la incontestabilidad de la matemática. El posterior desarrollo de la teoría de conjuntos trajo consigo antinomias y contradicciones: algunos asertos, relacionados con el concepto de “infinitud” podían ser al mismo tiempo probados y refutados matemáticamente. Sirva como ejemplo la antinomia lógico-matemática de Russell (y también de Burali y Forti) denominada el “conjunto de todos los números ordinales”: Sobre cada conjunto de números ordinales hay un número ordinal que es mayor que todos los números ordinales que aparecen en el conjunto. Ahora bien, todo número ordinal que es mayor que el “conjunto de todos los números ordinales” no puede aparecer en este conjunto (pues es mayor que él), pero (también así se puede probar) debe aparecer en dicho conjunto, ya que de lo contrario no se trataría del conjunto de todos los números ordinales.

Si estos resultados, por sí solos, ya habían provocado inquietud, los resultados de Gödel y Church vienieron a agravar la situación. Parecía que el programa de Hilbert, el más bello programa de la historia de la humanidad, quedaba definitivamente arruinado. ¿Anulaban los resultados de Gödel el programa de Hilbert? En parte sí y en parte no. Anulaban el programa de Hilbert en el sentido de que no se puede establecer -simultáneamente- la completud y consistencia de un sistema axiomático por métodos puramente sintácticos. Ahora bien, sí que hay un modo de salvar la consistencia de la aritmética: este modo consiste en recurrir a la semántica. Es decir, la garantía de la coherencia de los sistemas formales habrá de buscarse en las interpretaciones que sean modelos de dichos cálculos; esto dará lugar al surgimiento de la teoría de modelos. Dado que es posible demostrar que si un cálculo admite un modelo, ese cálculo es consistente, la tarea se centra ahora en la búsqueda de modelos para nuestros cálculos; pero con ellos hemos abandonado el terreno de la sintaxis y nos hemos adentrado en el terreno de la semántica.

En consecuencia, la situación no parece tan grave, basta con cambiar el terreno de la sintaxis por el de la semántica para que todo siga funcionando. Sin embargo, algunos filósofos han llegado a afirmar que el resultado de Gödel demuestra “el fracaso de la lógica” o hasta “el fracaso de la razón”. Contra estas afirmaciones bastan las siguientes palabras de Manuel Sacristán:

[…] estas afirmaciones carecen de fundamento, como puede verse por las siguientes consideraciones. En primer lugar, lo único que demuestra el teorema de Gödel es que resulta imposible conseguir un conjunto de axiomas y un juego de reglas de transformación que suministren todas las verdades formales expresables en el lenguaje de la lógica de predicados […]
En segundo lugar, el hecho de que la lógica misma haya descubierto y demostrado los límites o la inviabilidad de una realización universal del programa algorítmico, en su forma clásica, es más bien un éxito que un fracaso de la actividad capaz de tal resultado. El resultado mismo significa que el pensamiento racional puede saber cuales de sus actividades son algoritmizables, ejecutables (en principio) mecánicamente, y cuáles no; cuáles son, como suele decirse, trabajo racional mecánico, y cuáles trabajo racional productivo. Fracaso del pensamiento es más bien la situación en la cual el pensamiento no sabe cuál es el alcance de su actividad, como suele ocurrir, dicho sea de paso, a muchos filósofos (Introducción a la lógica y al análisis formal, Barcelona, Círculo de Lectores, 1990, pp. 254 ss.)

9. Bibliografía

  • Blanché, R., La axiomática, México, UNAM, 1965
  • Bochenski, I. M., Los métodos actuales del pensamiento, Madrid, Rialp, 1973
  • Boole, G., El análisis de la lógica, Madrid, Cátedra, 1979
  • Cohen, M., Nagel, E., Introducción a la lógicay al método científico, Buenos Aires, Amorrortu, 1968, 2. vols.
  • Deaño, A.: Introducción a la lógica formal, Madrid, Alianza, 1974
  • Garrido, M.: Lógica simbólica, Madrid, Tecnos, 1983
  • Gödel, K.: “Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas afines” en Gödel, K.: Obras completas, Madrid, Alianza
  • Hilbert, D.: El pensamiento axiomático, Revista matemática hispanoamericana, 1, (1919)
  • Hofstadter, D.R.: Gödel, Escher, Bach: un eterno y grácil bucle, Barcelona, Tusquets
  • Mates, B., Lógica matemática elemental, Madrid, Tecnos, 1970
  • Mosterín, J.: Lógica de primer orden, Barcelona, Ariel, 1970
  • Nagel, E. y Newman, J.R.: El teorema de Gödel, Madrid, Tecnos
  • Poincaré, H., La ciencia y la hipótesis, Madrid, Espasa-Calpe, 31963
  • Russell, B. y Whitehead, A.N.: Principia mathematica, Madrid, Paraninfo, 1981
  • Sacristán, M., Introducción a la lógica y al análisis formal, Barcelona, Círculo de Lectores, 1989
  • Suppes, P., Teoría axiomática de conjuntos, Cali (Colombia), Norma, 1968
  • Tarski, A.: Introducción a la lógica, Madrid, Espasa-Calpe, 1951