Corrección y completitud

Dos preguntas sobre el sistema del curso

La unidad sobre la deducción fijó el sistema del curso: los esquemas de axiomas A1, A2 y A3 de Łukasiewicz y dos reglas, el modus ponens (MP) y el reemplazo de la doble negación (RDN), que la clase sobre las cuatro técnicas de deducción añadió después de demostrar la doble negación. Una deducción desde un conjunto $\Gamma$ es una sucesión finita de fórmulas en la que cada una es un axioma, un elemento de $\Gamma$, el resultado del modus ponens aplicado a dos fórmulas anteriores o el resultado de RDN aplicada a una anterior; $\Gamma \vdash \varphi$ significa que hay una deducción desde $\Gamma$ cuya última fórmula es $\varphi$. La unidad sobre la semántica, por su parte, definió en la clase sobre consecuencia y equivalencia semántica la relación $\Gamma \models \varphi$: toda valoración que satisface todas las fórmulas de $\Gamma$ satisface $\varphi$. Ambas relaciones se escriben con el mismo patrón, un conjunto a la izquierda y una fórmula a la derecha; ahora bien, su naturaleza es opuesta. La primera es sintáctica y existencial: afirma que existe un objeto finito, una deducción, que se puede revisar signo por signo. La segunda es semántica y universal: afirma algo de todas las valoraciones, que son infinitas, y cada una de las cuales da valor a infinitas variables.

Dos preguntas se plantean, por tanto, sobre el sistema. La primera: ¿deduce solo lo que debe? Se dice que el sistema es correcto si, para todo conjunto $\Gamma$ y toda fórmula $\varphi$, $\Gamma \vdash \varphi$ implica $\Gamma \models \varphi$: lo que se deduce de unas premisas es verdadero bajo toda valoración que hace verdaderas las premisas. La segunda: ¿deduce todo lo que debe? Se dice que el sistema es completo si $\Gamma \models \varphi$ implica $\Gamma \vdash \varphi$. La completitud admite tres grados, según los conjuntos de premisas que abarca:

• completitud débil: si $\models \varphi$, entonces $\vdash \varphi$; toda tautología es un teorema;
• completitud para conjuntos finitos: si $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$, entonces $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$;
• completitud fuerte: si $\Gamma \models \varphi$, entonces $\Gamma \vdash \varphi$, para un conjunto $\Gamma$ cualquiera, también infinito.

Esta clase demuestra la corrección y los dos primeros grados de la completitud. El tercero se demuestra en la clase sobre el teorema de compacidad, y la razón de esa división se explicará al final de la clase.

Lo que no hay que decir

El artículo del que procede esta clase llamaba «solvencia» a la corrección, calco del inglés soundness; el término castellano es «corrección», y es el que el curso usa. Además, la definía como la propiedad del sistema «de inferir una expresión a partir de un conjunto de expresiones», que es la deducibilidad misma y no una propiedad del sistema. Los errores de fondo, sin embargo, eran otros dos.

El primero era afirmar que la corrección y la completitud «se pueden inferir una de la otra». Son propiedades independientes: el sistema de Łukasiewicz, sin la regla RDN, es correcto (la demostración de esta clase lo prueba, suprimiendo un caso) y no es completo (la clase sobre los sistemas deductivos formales exhibió una tautología que no deduce); y un sistema que adoptara todas las fórmulas como axiomas sería completo sin ser correcto. El problema resuelto 2 examina ambos ejemplos.

El segundo error es más grave, porque presentaba como demostración de la completitud un argumento circular. Decía, en sustancia: si $\varphi \nvdash \psi$, entonces, por el teorema de deducción, $\nvdash (\varphi \rightarrow \psi)$; «por la corrección», $\not\models (\varphi \rightarrow \psi)$; y por el teorema de deducción semántico, $\varphi \not\models \psi$. Ahora bien, la corrección dice que lo deducible es válido, y su contrapositiva, que lo que no es válido no es deducible:

El paso del argumento va en el otro sentido, de $\nvdash \chi$ a $\not\models \chi$, que es la contrapositiva de $\models \chi \Rightarrow \vdash \chi$, es decir, de la completitud débil. Si esto es así, el argumento supone lo que pretende demostrar. De ello se sigue que la completitud no se «infiere de un modo sencillo», como afirmaba el artículo: es el resultado más profundo del curso, y su demostración ocupa la mayor parte de esta clase. Por último, el artículo resumía la completitud diciendo que «todas las expresiones verdaderas tienen una demostración»; lo que tiene demostración es lo válido, verdadero bajo toda valoración, no lo verdadero bajo alguna: la variable $v_{1}$ es verdadera bajo muchas valoraciones, y no es un teorema.