Metalógica de Proposiciones
David Baños Abril
En cualquier rama de la matemática que sea formalizable en un sistema, habrá que distinguir entre los conocimientos que nos aporta el sistema en forma de teoremas, del conocimiento que podemos nosotros inferir del sistema como un todo. Este último recibe el nombre de metalógica.
Una visión desde fuera
Los sistemas lógicos formales cuentan con un conjunto de propiedades que conciernen al sistema como un todo y que, por tanto, solo pueden ser expresadas «desde fuera» del sistema. La metalógica se encarga de estudiar estas propiedades. En ocasiones, «desde dentro» el sistema es incapaz de deducir como teoremas estas propiedades generales referidas al todo.
Como va siendo usual, usaremos una cita cinéfila para ilustrar el concepto de metalógica. Pongamos como ejemplo estas:
«La luz que brilla con el doble de intensidad dura la mitad de tiempo, y tu has brillado mucho, Roy»
“Es toda una experiencia vivir con miedo; eso es lo que significa ser esclavo.”
«Todos esos momentos se perderán en el tiempo, como lágrimas en la lluvia.»
Estas citas tienen un contenido significativo, filosófico si se quiere. Pero, para el amante de la ciencia ficción, estas citas comparten una propiedad. Todas ellas se han extraído de la película Blade Runner. Esta propiedad no es algo evidente a partir de las frases, puesto que en ningún momento hacen referencia a la propia película. De hecho ningún diálogo de ningún personaje de Blade Runner trata sobre la película de Blade Runner. La película no es autorreferente. Es «desde fuera» del film donde podemos ver que esas frases pertenecen a un universo propio de ciencia ficción.
Hay sistemas que sí son capaces de hablar de sí mismos. El más evidente es el lenguaje humano, capaz de expresar propiedades del propio lenguaje con sus propios recursos. Esta facultad arrastra consigo la existencia de paradojas que veremos en un futuro.
La verdad metalógica
Debe quedar claro que no es lo mismo que una fórmula exprese una verdad universal a que dicha fórmula sea deducible en el sistema lógico. Esta diferencia es la que justifica la mayoría de propiedades metalógicas: la relación entre lo que es deducible a partir de unos axiomas y por medio de la aplicación ciega y mecánica de las reglas de inferencia y lo que es cierto. ¿Son todas las deducciones verdades universales? ¿Puede nuestro sistema dejar fuera alguna verdad tautológica que no sea deducible?
Consistencia
La primera meta-propiedad que veremos será la consistencia, muy relacionada con el concepto de solidez visto en el artículo previo. Decimos que un sistema es consistente si no es posible deducir fórmulas contradictorias. Si uno de los teoremas es F, y resulta que ¬F es también demostrable, entonces el sistema es inconsistente.
También podemos expresarlo así:
es decir, si una fórmula X es demostrable entonces no es demostrable ¬X. Notar como usamos el signo ⇒ para denotar una implicación sin recurrir al símbolo → que pertenece al lenguaje de estudio.
Un sistema inconsistente.
Principio de ex falso quodlibet
El Principio de Explosión o ex falso quodlibet es sumamente importante. Afirma que a partir de una contradicción, es posible deducir cualquier fórmula bien formada, ya sea una verdad tautológica como otra contradicción.
La razón se encuentra en la propiedad de la disyunción. Si existe una contradicción y tanto A como ¬A son deducibles, entonces también será deducible la disyunción: \vdash (A ∨ ¬A). Recordemos que para que sea cierta la disyunción, al menos una de las dos debe ser cierta. Por lo tanto, la contradicción implica que tanto A ∨ B como ¬A ∨ B son deducibles, siendo así para cualquier fórmula que sea B.
En otras palabras: la lógica no admite imperfecciones. Una solo contradicción y los objetivos de un sistema lógico que solo deduzca verdades universales se desmorona.
La consistencia es por tanto una propiedad de naturaleza restrictiva: un sistema consistente, que no contenga ninguna contradicción, no demostrará todas las fórmulas posibles de un lenguaje.
Consistencia del Cálculo Proposicional
Toca preguntarse ¿Es el cálculo lógico visto en el artículo previo consistente? ¿Puede la aplicación de las reglas de inferencia -sustitución y modus ponens- sobre el conjunto de axiomas válidos terminar ofreciéndonos dos teoremas que sean contradictorios?
Tal y como vimos en el artículo anterior, todos las deducciones del cálculo lógico son sólidas, esto es, sus premisas son verdaderas y los son también las consecuencias. Cada nuevo teorema hereda su veracidad desde las premisas, las cuales o son axiomas o son teoremas ya demostrados. Dado que se ha restringido el uso exclusivamente a deducciones sólidas, podemos decir que el sistema en su totalidad es consistente.
Consistencia y Verdad Matemática
La propiedad de consistencia ha tenido una importancia histórica en el desarrollo de la lógica y de la formalización de amplias ramas de la matemática. A la pregunta de por qué unos axiomas y no otros, la consistencia ha tenido un rol importante.
-Si los axiomas arbitrariamente estipulados, junto con todas sus consecuencias, no se contradicen entre sí, entonces son verdaderos y existen las cosas definidas por ellos. Ese es mí criterio de la existencia y de la verdad.-
-David Hilbert. Carta a Gottlob Frege (1899).
En esta cita Hilbert nos desvela que la elección de axiomas está condicionada precisamente a que sean capaces de generar un sistema consistente. No es necesario que los principios axiomáticos nos parezcan intuitivamente comprensibles. Aunque tesis, como que todas las posibles rectas de un plano se intersecan o la raíz cuadrada de -1, fueron inicialmente extrañas, la demostración de que podían deducirse a partir de ellas nuevas teorías matemáticas no contradictoras despejó toda duda sobre su legitimidad.
La consistencia es una propiedad que, por sí misma, garantiza la verdacidad de una teoría matemática. Esta es la primera vez que nos acercamos a un concepto de verdad desligado completamente de cualquier referencia psicológica o mental, una verdad plenamente matemática. ¿Significa eso que hemos conseguido desligar la matemática definitivamente de lo que es asimilable por nuestra intuición? Esa es precisamente el tema del que trata nuestra serie de Metamatemática, a la que recomendamos ver una vez acabada esta serie.
Completitud
Podemos imaginarnos un sistema formal que de lugar a fórmulas consistentes entre sí. Pero ese sistema puede llegar a ser muy pobre y ofrecernos tan solo un conjunto limitado de fórmulas. De esta manera, la formalización habrá sido algo inútil. Buscamos que el sistema formal dé cuenta de cualquier fórmula tautológica. Necesitamos un concepto nuevo, el de completitud. Se conoce como completitud la capacidad de un sistema formal de deducir todas las fórmulas universalmente ciertas.
Un sistema incompleto.
Podemos observar que mientras la propiedad de consistencia limita las fórmulas demostrables, la completitud establece un mínimo de estas fórmulas. Así mismo, mientras que la solidez establecía que todo lo demostrable era verdadero, la completitud invierte esto y afirma que todo lo verdadero es demostrable:
Por el Principio de Explosión, todo sistema inconsistente es completo.
La completitud y la consistencia son sin duda las dos propiedades de la metalógica más importantes.
Completitud del Cálculo Proposicional
La demostración de la completitud del cálculo proposicional depende de dos metateoremas (no teoremas del sistema, sino teoremas acerca del sistema) que no vamos a demostrar aquí por problemas de espacio y que eventualmente tendrán que creerse. Se trata del Teorema de Deducción, sumamente importante en los casos en los que las premisas no son necesariamente verdades universales:
Recordemos que una deducción es una cadena de fórmulas, las cuales o bien son axiomas o bien son generadas a partir de estos vía reglas de deducción. Este Teorema de Deducción afirma que si A es la última fórmula de la cadena a partir de la cual se demuestra B, entonces A → B es también demostrable en el sistema.
Este teorema nos permite realizar afirmaciones como la de que cada fila de una tabla de verdad representa realmente un procedimiento de deducción.
Es esta tabla vemos la resolución de una expresión lógica no tautológica. Cada combinación de valores de verdad de las variables A,B y C equivale a un proceso deductivo. Por ejemplo, la última de las filas: A, ¬B, ¬C \vdash A→((B ∨ C)→(C → ¬A)), pero A, ¬B, C \vdash ¬(A→((B ∨ C)→(C → ¬A))). La misma lógica es aplicable a los pasos previos en la resolución de la tabla de verdad. Así ¬B y ¬C \vdash ¬(B ∨ C).
En el caso de una expresión tautológica, cualquier combinación de variables la resuelve igualmente como una verdad universal. Pongamos que A, B \vdash X, siendo X una expresión tautológica. Entonces sabemos que cualquier otra combinación ((¬A, ¬B), (A, ¬B) y (¬A, B)) también demostraría X.
Por la propiedad de la disyunción, podemos poner sin problemas que (A ∨ ¬A), (B ∨ ¬B) \vdash X.
Un segundo metateorema, de gran calado también en lógica, es el Teorema de Tercio Excluso («no existe una tercer alternativa»), el cual sentencia que para toda fórmula A:
Así que cada una de las disyunciones son verdaderas y demostrables. Y, por tanto el teorema X es demostrable. Este procedimiento es generalizable a cualquier fórmula universalmente válida, y por ello podemos demostrar que el cálculo lógico proposicional es completo.
Formulaciones alternativas
Existen formulaciones de la completitud que son algo diferentes y más robustas a la presentada previamente. Podemos decir que un sistema es completo si, al incluirse como axioma una fórmula que previamente no era demostrable, entonces el sistema se torna inconsistente. Bajo esta formulación se nos es posible realizar la demostración por reducción al absurdo: comprobaremos las imposibles consecuencias que conlleva suponer de ese nuevo axioma. Esta propiedad se conoce como completitud de Post.
Existe una tercera, conocida como completitud sintáctica que expresa que para cualquier fórmula bien formada X, o bien \vdash X o bien \vdash ¬X.
Decibilidad
Se conoce como decibilidad la propiedad de un sistema lógico de contar con un algoritmo o procedimiento mecánico para determinar si una de sus fórmulas es o no verdadera (demostrable a partir de los axiomas).
En el Cálculo Proposicional este mecanismo era la elaboración de Tablas de Verdad, tal y como puede verse en la imagen del apartado previo. Si el conector más externo resultaba siempre verdadero independientemente del valor de verdad de las variables proposicionales, entonces la fórmula era válida. Este procedimiento nos confirma que el Cálculo Proposicional es efectivamente decidible.
La decibilidad usando Tablas de Verdad es evidentemente un procedimiento largo y tedioso sabiendo además que cuando el número de variables crece su complejidad asciende exponencialmente. Pero lo importante es que la resolución sea posible en un número de pasos finitos, por grande que sea este número.
Problema de Decisión
La decibilidad es, en última instancia la propiedad que justificó el llamado Problema de Decisión (Entscheidungsprobleme), planteado por Hilbert y Ackermann a principios del siglo XX.
Dicho problema sería más tarde solucionado haciendo uso de dos herramientas completamente distintas: el Cálculo Lambda de Alonzo Church y el experimento mental conocido como la Máquina de Turing. En este último caso, la decibilidad se reformularía como el Problema de la Parada, tema al cual le fue dedicado su respectivo artículo:
Independencia de Axiomas
Nos falta una propiedad metalógica más a la que podemos hacer referencia. Esta es la independencia de axiomas.
Los axiomas son fórmulas no demostrables que sirven para cimentar nuestras teorías lógicas. Eso significa que ningún axioma puede ser obtenido dentro del sistema por deducción. Si lo fuera, entonces dejaría de ser una axioma para convertirse en un teorema más. Es a esto lo que denominamos independencia de axiomas. Este criterio debe unirse al de consistencia para ofrecernos axiomas con suficiente potencial.
Lecturas recomendadas
– Delgado, V. M. (1972) Lecciones de lógica (I).
– Kolmogórov, A.N. y Dragalin, A.G. (2013) Introducción a la lógica matemática.
– de Swart, H. (2018) Philosophical and Mathematical Logic.