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.
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.
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.
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.
La construcci�n de un sistema formal de l�gica se lleva a cabo en cuatro fases que, convenientemente numeradas, son:
Se prepara un cat�logo completo de los signos que se han de usar en el c�lculo. Estos signos son nuestro vocabulario
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
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.
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:
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
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.
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
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.
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.
G�del mostr�:
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
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.
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.
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.
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.
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:
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.
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:
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.
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.
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.
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.
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:
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);
M debe, si no se produce ning�n error, producir siempre el resultado deseado en un n�mero finito de pasos;
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;
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
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.)