Apéndice 3
Teoría, metateoría y existencia de fórmulas indecibles
Roland Fraïssé
La actividad lógica más elemental consiste en una formalización de las teorías matemáticas, es decir, en una representación de cada frase del discurso matemático por medio de una fórmula lógica. Esta representación exige que se enuncien reglas de construcción para las fórmulas, que consisten en sucesiones finitas de símbolos; y exige, además, que se enuncien reglas de deducción inmediata de una fórmula a partir de una o dos fórmulas en general: por ejemplo, la regla de separación, llamada también modus ponens, la cual dice que, a partir de las dos fórmulas P y P ⇒ Q, o equivalentemente ¬P ⋁ Q, se deduce Q. La deducción se define por la aplicación, un número finito de veces, de deducciones inmediatas. La actividad así descrita se llama la sintaxis lógica.
Esta sintaxis no puede desarrollarse siquiera un poco rigurosamente más que sumergiéndola en una teoría matemática, llamada la metateoría o teoría representante. En particular, es indispensable prever la aparición de fórmulas lógicas con longitudes finitas arbitrariamente grandes, así como, para definir la deducción, de sucesiones finitas arbitrariamente largas de deducciones inmediatas. Ello sólo es posible si existe la noción de entero natural en la metateoría, y si está acompañada de las relaciones y funciones más elementales, tales como la comparación <, la función «entero siguiente, o consecutivo», y la adición, útiles por ejemplo para establecer la longitud de una fórmula que es el resultado de la concatenación de otras dos, P y Q, así como la de una conexión tal como P ⋀ Q.
Por lo demás, la metateoría no es de una naturaleza distinta a la de las otras teorías matemáticas; en particular, es susceptible de representarse, a su vez, en una segunda metateoría, y así sucesivamente. Diversas observaciones, bastante elementales, exigen la consideración de dos metateorías consecutivas; y los lógicos utilizan a veces la existencia de sucesiones infinitas de metateorías encajadas unas en otras.
El desarrollo de la semántica, o estudio de los valores veritativos y de los modelos, ha supuesto una renovación para la noción de metateoría representante. Históricamente, la semántica hizo ya su aparición en la obra de Hilbert (1904) con los primeros intentos de demostrar la consistencia, o no contradicción, de determinadas teorías sencillas. Experimentó un desarrollo con Herbrand (1930), que demostró la consistencia de una aritmética desprovista de los axiomas generales de inducción o recurrencia. Estos éxitos y fracasos a medias quedaron aclarados por el teorema de incompleción de Gödel (1931), que demuestra la existencia de fórmulas indecidibles, es decir, ni demostrables ni invalidables a partir de los axiomas, para el caso de la aritmética usual, definida por ejemplo por los axiomas de Peano (ver la nota: «La axiomática de Peano», pág. 67). En términos más precisos, la fórmula indecible afirma la consistencia de la aritmética (se trata de una fórmula expresada tan sólo por medio de las nociones o predicados de suma y producto, estando cada fórmula representada por un número).
El hecho de que esta fórmula de consistencia sea fácilmente demostrable en la metateoría que representa a la aritmética revela la superioridad de la metateoría sobre la teoría representada. Por otra parte, hay que hacer notar que el teorema de Gödel no impide la existencia de una aritmética completa en la que se dispusiera de suficientes axiomas, además de los de Peano, como para que cada fórmula en términos de «más» y «multiplicado por» fuera demostrable o invalidable (su negación fuera demostrable). Sólo que, entonces, el teorema toma la forma de un enunciado de no axiomatizabilidad recursiva: una tal aritmética completa no puede obtenerse ni con un número finito de axiomas, ni tampoco siquiera con una infinidad recursiva de axiomas, susceptibles de ser enunciados sucesivamente, en el transcurso de un porvenir infinito, por un ordenador (véase el apéndice 2: «Recursividad»).
La noción de valor de verdad de una fórmula para un sistema de relaciones y de elementos se ha considerado ya en el apéndice 1: «Tesis, deducción…». Su formulación en términos precisos y generales se debe a Tarski (1936); pero, en la práctica, había sido utilizada ya por Hilbert, Herbrand e, incluso, se la había usado intuitivamente en el enunciado del teorema del modelo numerable de Löwenheim (1915), ampliado por Skolem (1920): toda teoría consistente admite un modelo numerable, es decir, un sistema de relaciones de base a lo más numerable, que la verifica.
La representación de una teoría en otra puede adoptar diversas formas que, al parecer, nunca se han clasificado ni han sido estudiadas desde un punto de vista general por los lógicos, si se exceptúa la representación directa llamada interpretación, obtenida al definir cada predicado, o noción, de la teoría interpretada en el seno de la teoría interpretante; o, en otras palabras, obtenida al construir un modelo de la teoría interpretada en el marco de la teoría interpretante. Éste es ya el caso para las geometrías. Y es también el caso, en Gödel (1940), de la teoría de conjuntos con axioma de elección, interpretada en una teoría de conjuntos privada de este axioma: todo conjunto viene interpretado como un conjunto constructible. A menudo, la interpretación es simétrica: cada una de ambas teorías puede interpretarse en la otra; mientras que la representación propiamente dicha, por metateoría, siempre tiene lugar en un único sentido.
Aparte de las interpretaciones, las dos representaciones más conocidas son: la numeración de las fórmulas, debida a Gödel (1931) y llamada numeración gödeliana; y la representación mediante valores veritativos, debida a Tarski (1936) y llamada representación tarskiana. En la primera, cada fórmula queda numerada, por ejemplo, ordenando el conjunto de las fórmulas según su longitud creciente, y lexicográficamente las de igual longitud, a partir del alfabeto finito de los símbolos lógicos; cada fórmula es una sucesión finita de dichos símbolos. De esta manera, a cada teoría representada le corresponde el conjunto de los números de las fórmulas que la integran. A cada procedimiento de construcción de fórmulas le corresponde una función de los números enteros. Por ejemplo, a la conjunción (y) le corresponde la función f que, para cada par de enteros p, q, toma el valor f(p, q) = número de la conjunción de la fórmula número p con la fórmula número q.
En la representación tarskiana, la metateoría encargada de representar la aritmética, por ejemplo, empezará por definir el conjunto E de los enteros. Luego, a cada fórmula lógica que conste de los símbolos suma y producto, además de los símbolos lógicos, y de los símbolos de los enteros, la metateoría le asociará un valor veritativo que siempre está definido (incluso si no siempre se puede calcular). Este valor veritativo es evidente para el caso de una fórmula libre, es decir desprovista de cuantificadores, tal como 2 + 3 = 5 ó 2 · 4 = 8. Cuando se introduce el cuantificador «para todo», el valor de ∀x P(x) es «verdadero» si y sólo si P(0), P(1), P(2),… poseen todas el valor «verdadero»; y cuando se introduce el cuantificador «existe alguno», el valor de ∃x P(x) es «verdadero» si y sólo si una al menos, de las P(0), P(1), P(2),… toma el valor «verdadero». Así pues, es preciso que la metateoría sea suficientemente rica en axiomas y definiciones como para poder representar, para cada fórmula P, la función que asocia a cada entero x el valor veritativo de P(x).
Diremos que una teoría U es más potente que T, o que tiene una potencia representativa superior, cuando, o bien T es interpretable en U mediante definiciones, o bien existe una representación gödeliana o tarskiana de T en U. Esta noción de potencia representativa, aunque nunca se haya definido hasta ahora con precisión, es mucho más útil y sutil que la de fuerza axiomática ya considerada en el apéndice 1, «Tesis, deducción…». Así, la teoría cantoriana usual U de conjuntos es a la vez más fuerte y más potente que la teoría tronco común T, obtenida a partir de U por supresión del axioma del infinito. Pero la combinatoria U obtenida a partir de T añadiendo el axioma «todo conjunto es finito», aunque es más fuerte axiomáticamente que T, equivale a T en potencia representativa: para representar C en T, basta con relativizar cada fórmula a los conjuntos finitos, o sea, sustituir cada cuantificador «para todo x» por «para todo x, si x es finito, entonces…», y cada «existe algún x» por «existe algún x finito tal que…».
Otro ejemplo: la teoría cantoriana de conjuntos con axioma de elección, aunque es estrictamente más fuerte que aquélla que no lo posee, sigue teniendo la misma potencia representativa. El trabajo de Gödel (1940) es una representación de la teoría con axioma de elección en la teoría sin axioma de elección, por relativización de las fórmulas a los conjuntos constructibles.
Acabemos con una argumentación sencilla, que se remonta al procedimiento diagonal de Cantor y permite demostrar que, cuando una metateoría incluye la noción de función numérica, es estrictamente más potente que las teorías que representa por numeración gödeliana o por utilización tarskiana de los valores veritativos. Una tal metateoría permite enumerar si que pueden definirse en la teoría representada; por consiguiente, la sucesión numérica si(i) puede definirse en la metateoría; así pues, también puede definirse una sucesión t(i) ≠ si(i) para todo entero i, sucesión que es evidentemente distinta de todas las si; de aquí resulta la imposibilidad de representar la metateoría en la teoría.