VOLLSTÄNDIGKEIT

Completitud

(Recop.) Justo Fernández López

 

Vgl.:

Widerspruchsfreiheit / Gödel-Satz / Wissenschaftstheorie und Linguistik  

 

Vollständigkeit

Die Vollständigkeit einer Menge besagt die Umkehrung der Widerspruchsfreiheit, d.h.

semantisch:

alles was wahr ist, ist beweisbar.

klassisch:

von zwei Aussagen A und nicht A ist stets eine beweisbar.

syntaktisch:

wenn eine nicht beweisbare Aussage als Axiom genommen wird, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar.“

[Prof. Peter H. Starke und Stephan Roch. In:

http://www.informatik.hu-berlin.de/lehrstuehle/automaten/logik/node2.html]

Completo

El vocablo ‘completo’ es uno de los conceptos fundamentales usados en metalógica. 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. Las dos anteriores definiciones corresponden a dos tipos de completitud y son aplicadas, según los casos, a diversas clases de cálculos.

Como ocurre con el concepto de consistencia, el de completitud es también un concepto sintáctico, pero se tienen en cuenta en su formulación y desarrollo consideraciones de carácter semántico. Referencia a la relación entre consistencia y completitud, en el artículo Gödel [ver aquí: Gödel- Satz].“

[Ferrater Mora, José: Diccionario de filosofía. Buenos Aires: Editorial Sudamericana, 1969, vol. 1, p. 312]

Metateoría de la lógica

La Metateoría consiste sobre todo en estudiar si los cálculos lógicos responden a cierto tipo de requisitos. Estos requisitos son, fundamentalmente, tres.

1.  El requisito de consistencia. Un cálculo es consistente si y sólo si no es posible demostrar en él una fórmula y su negación.

2. El requisito de completud o completitud. Un cálculo es completo cuando en él se pueden demostrar todas las fórmulas verdaderas construibles con sus símbolos.

3. El requisito de decibilidad. En rigor, llamar «decidible» a un cálculo es una figura de dicción. Decidibles serán, en todo caso, las fórmulas del cálculo, y no el cálculo como tal. Se acostumbra a decir que un cálculo es decidible cuando dispone de al menos un procedimiento para decidir, en un número finito de pasos reglamentados, si una fórmula es verdadera o no (y, por ende, en el caso de que el sistema sea completo, si es o no derivable en él).

Por lo que se refiere al cálculo de enunciados, cumple con los dos primeros requisitos.

También el cálculo de predicados de primer orden reúne los requisitos de consistencia y completud.

Importante es la demostración del carácter completo de la lógica cuantificacional elemental, llevada a cabo por Kurt Gödel en 1930. El cálculo de predicados de primer orden no es decidible, en su conjunto. Lo son ciertos estratos – como la lógica de predicados monádicos – o ciertos conjuntos de fórmulas – ciertos tipos de expresiones de la lógica de predicados poliádicos –, pero la lógica de predicados poliádicos es, como tal, indecidible, y, por lo tanto, lo es también la lógica general de predicados, que la incluye. Lo demostró Alonzo Church en 1936.

En cuanto a la lógica cuantificacional superior, Kurt Gödel, el que probó en 1930 la completud de la lógica elemental, demostró, en un celebérrimo trabajo publicado en 1931, que es incompleta: mientras que las verdades formales acerca de cualesquiera individuos pueden ser organizadas en un cálculo lógico que las fundamente, las verdades acerca de cualesquiera conjuntos de individuos (o acerca de cualesquiera predicados de individuo) no pueden ser presentadas en su totalidad como el conjunto de los teoremas de un sistema lógico. El hecho de que León Henkin, en 1950, haya matizado el teorema de Gödel mostrando la posibilidad de alcanzar en lógica cuantificacional superior una cierta completud, una completud secundum quid, apenas priva a dicho resultado metateórico de su impacto sobre la lógica formal, sobre la filosofía de la lógica, y, en definitiva, sobre la filosofía a secas.”

[Deaño, Alfredo: Introducción a la lógica formal. 2. Lógica de predicados. Madrid: Alianza Ed., 1975, p. 200-201]

«Completitud del cálculo lógico elemental

En sentido semántico se dice que un cálculo es completo cuando todas las verdades formales formulados en su lenguaje son teoremas del cálculo. En sentido sintáctico, se dice que un cálculo es completo cuando, al añadírsele una fórmula que no sea un teorema suyo, el cálculo se hace inconsistente. (El añadido se entiende hecho al sistema de los teoremas del cálculo). El sentido sintáctico de ‘completitud’ incluye en cierto modo al semántico: pues si el añadir al cálculo una fórmula no demostrable en él le hace inconsistente, es que él demuestra todas las fórmulas verdaderas, o que, por decirlo gráficamente, es completo porque “no se le puede añadir nada”.

La parte de la lógica elemental a la que hemos llamado ‘lógica de enunciados’ es completa en el sentido más fuerte (el sintáctico) de los dos dichos; luego veremos un esbozo de como se demuestra que la lógica de predicados de primer orden –o sea, el sistema de la lógica elemental– es completa (semánticamente).»

[Sacristán, Manuel: Introducción a la lógica y al análisis formal. Barcelona: Ariel, 1973, p. 182]

«La gödelización

La gödelización se basa en el teorema fundamental de la aritmética que enseña que la descomposición de un número en factores primos es unívoca. La técnica consiste en representar toda fórmula de la lógica de predicados por un número que es un producto de factores primos afectados por exponentes.

Se empieza por asignar a cada símbolo elemental un número, llamado ‘número de Gödel’ del símbolo. [...]

Lo esencial de la gödelización es esto: la lógica de predicados (de orden superior) permite expresar la aritmética. En lógica de predicados pueden construirse, pues, expresiones que hablan de números, los relacionan, etc. Esas expresiones constituirían (si dieran lugar a un cálculo completo) una formalización de la aritmética. Por otra parte, dada la infinitud de órdenes de la lógica de predicados, en ella pueden también expresarse afirmaciones acerca de las afirmaciones aritméticas: por ejemplo, que tal afirmación aritmética es verdadera o falsa, o que es demostrable, o que es indemostrable. Diremos, para abreviar, que en la lógica de predicados puede expresarse también la “metaaritmética”. Pues bien: la gödelización de la lógica de predicados permite a su vez representar las expresiones de la lógica de predicados –incluidas, naturalmente, las metaaritméticas– por expresiones aritméticas, de modo que una expresión metaaritmética sobre la verdad, falsedad, demostrabilidad o indemostrabilidad de una expresión aritmética podrá representarse a su vez por una expresión aritmética. En esta circunstancia se basa la argumentación de Gödel. [...]

El teorema de incompletitud de Gödel

La argumentación de Gödel demuestra que ya la parte de la lógica de predicados necesaria para formular la aritmética es incompleta, en el sentido de que existe al menos una fórmula de la teoría aritmética formulable en ella la cual es verdadera (cosa que se establece por un razonamiento metalógico, “metaritmético”) y que, sin embargo, no puede ser demostrada en la formulación de la aritmética misma en la lógica de predicados.»

[Sacristán, Manuel: Introducción a la lógica y al análisis formal. Barcelona: Ariel, 1973, p. 189 y 191-193]

«Sobre la significación del teorema de incompletitud de Gödel para la teoría de la ciencia:

El teorema de incompletitud de Gödel enseña por de pronto que toda formalización de la aritmética en el cálculo de predicados es incompleta. Como el cálculo de predicados, si limitación de orden, es el algoritmo lógico más potente, puede decirse, de un modo más general, que toda formalización de la aritmética es incompleta. [...]

La incompletitud de la formalización de la aritmética es una incompletitud del instrumento formalizador mismo, o sea, del algoritmo lógico. De aquí que el resultado de Gödel pueda entenderse también así: el cálculo de predicados es incompleto. (Todos estos resultados se entienden con la condición de nuestro punto de partida, a saber: que el cálculo de predicados es consistentes.)

La lógica de predicados sin limitación de orden es aquella en la cual se intenta (sin éxito) formalizar la deducción para cualquier tipo de conocimiento que sea al menos de la complejidad de la aritmética. Y por debajo de la complejidad de la aritmética debe haber, puede pensarse, muy poco conocimiento teórico de interés. De aquí que, aún más laxamente, el teorema de Gödel haya podido entenderse también en el siguiente sentido filosófico: la lógica es incapaz de formalizar la deducción necesaria para fundamentar definitivamente cualquier conocimiento de algún interés teórico.

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 expresable en el lenguaje de la lógica de predicados. Esto, naturalmente, no excluye que los criterios logicoformales en particular, y los criterios racionales en general, sigan valiendo. Ellos son los que se aplican en las argumentaciones metalógicas que resultan necesarias por la incompletitud del cálculo mismo. En principio, las fórmulas verdaderas indemostrables en un cálculo a partir de los axiomas del mismo pueden demostrarse metalógicamente con los mismos “criterios lógicos”, como se hace, por ejemplo, en la argumentación de Gödel. Claro que la demostración metalógica planteará a su vez el problema de la incompletitud del razonar metalógico formalizado mismo: también en ese metalenguaje habrá verdades indemostrables, que serán demostrables en el metalenguaje de ese metalenguaje; y así sucesivamente. El proceso es, desde luego, ilimitado. Y ello muestra que el programa o ideal algorítmico, en el sentido de calculización de toda deducción, no es realizable. Pero eso sólo quiere decir que el sistema formal no se contiene ni se justifica nunca totalmente a sí mismo. Lo cual puede ser acaso molesto para filósofos idealistas como Platón, que crean en la autosuficiencia del mundo de los abstractos; pero no para un racionalismo como el aconsejado por la práctica de las ciencias, el cual debe ver en la experiencia con el mundo real la justificación de las formaciones abstractas, justificación siempre provisional y relativa.

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 cuáles 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 a muchos filósofos.»

[Sacristán, Manuel: Introducción a la lógica y al análisis formal. Barcelona: Ariel, 1973, p. 197-199]