Consistencia (lógica)

Los principales resultados relacionados con la consistencia y completitud fueron demostrados por Kurt Gödel:

• El teorema de completitud de Gödel indica que toda teoría de primer orden consistente es completa con respecto al conjunto consistente máximo de las fórmulas que se generan por medio del algoritmo de búsqueda de demostración.
• Los teoremas de la incompletitud de Gödel indican que las teorías capaces de expresar su propia relación de demostrabilidad y de desarrollar un argumento diagonal son capaces de demostrar su propia consistencia solo si son inconsistentes. Estas teorías, si son consistentes, son denominadas teorías esencialmente incompletas.

Mediante la aplicación de estas ideas, se pueden encontrar cuatro tipos distintos de teorías de primer orden:

1. Teorías inconsistentes, que no poseen modelos.
2. Teorías que no pueden analizar su propia relación de demostración, tales como la axiomatización de Tarski de la geometría del punto y la línea, y la aritmética de Presburg. Dado que estas teorías son descriptas en forma satisfactoria por el modelo que se obtiene mediante el teorema de completitud, entonces estos sistemas son completos.
3. Teorías capaces de analizar su propia consistencia, y que incluyen la negación de la proposición que asevera su propia consistencia. Este tipo de teorías son completas con respecto al modelo que se obtiene a partir del teorema de completitud, pero contienen como teorema la implicancia de una contradicción, en contradicción al hecho de que son consistentes.
4. Teorías esencialmente incompletas.

En forma adicional, se ha descubierto recientemente que existe un quinto tipo de teoría, las teorías auto verificables, que son lo suficientemente robustas como para analizar su propia relación de demostración, pero son demasiado débiles como para realizar una diagonalización de Gödel, y que por lo tanto pueden demostrar en forma consistencia su propia consistencia. Sin embargo, una teoría que demuestra su propia consistencia no permite obtener ninguna información interesante, dado que las teorías inconsistentes también demuestran su propia consistencia.

Un conjunto de fórmulas ${\displaystyle \Phi }$ en lógica de primer orden es consistente (expresado como Con${\displaystyle \Phi }$) si y solo si no existe una fórmula ${\displaystyle \phi }$ tal que ${\displaystyle \Phi \vdash \phi }$ y ${\displaystyle \Phi \vdash \lnot \phi }$. De lo contrario ${\displaystyle \Phi }$ es inconsistente y se expresa Inc${\displaystyle \Phi }$.

${\displaystyle \Phi }$ es simplemente consistente si y solo si para ninguna fórmula ${\displaystyle \phi }$ de ${\displaystyle \Phi }$ son tanto ${\displaystyle \phi }$ como la negación de ${\displaystyle \phi }$ teoremas de ${\displaystyle \Phi }$.

${\displaystyle \Phi }$ es absolutamente consistente si por lo menos una fórmula de ${\displaystyle \Phi }$ no es un teorema de ${\displaystyle \Phi }$.

${\displaystyle \Phi }$ es máximamente consistente si y solo si para toda fórmula ${\displaystyle \phi }$, si Con ${\displaystyle \Phi \cup \phi }$ entonces ${\displaystyle \phi \in \Phi }$.

${\displaystyle \Phi }$ se dice contiene testigos si y solo si para cada fórmula de la forma ${\displaystyle \exists x\phi }$ existe un término ${\displaystyle t}$ tal que ${\displaystyle (\exists x\phi \to \phi {t \over x})\in \Phi }$.

1. Los siguientes son equivalentes:

(a) Inc${\displaystyle \Phi }$

(b) Para todo ${\displaystyle \phi ,\;\Phi \vdash \phi .}$

2. Todo conjunto de fórmulas satisfactible es consistente, un conjunto de fórmulas ${\displaystyle \Phi }$ es satisfactible si y solo si existe un modelo ${\displaystyle {\mathfrak {I}}}$ tal que ${\displaystyle {\mathfrak {I}}\vDash \Phi }$.

3. Para todo ${\displaystyle \Phi }$ y ${\displaystyle \phi }$:

(a) si no ${\displaystyle \Phi \vdash \phi }$, entonces Con${\displaystyle \Phi \cup \{\lnot \phi \}}$;

(b) si Con ${\displaystyle \Phi }$ y ${\displaystyle \Phi \vdash \phi }$, entonces Con${\displaystyle \Phi \cup \{\phi \}}$;

(c) si Con ${\displaystyle \Phi }$, entonces Con${\displaystyle \Phi \cup \{\phi \}}$ o Con${\displaystyle \Phi \cup \{\lnot \phi \}}$.

4. Sea ${\displaystyle \Phi }$ un conjunto de fórmulas consistentes y que poseen testigos. Para todo ${\displaystyle \phi }$ y ${\displaystyle \psi }$:

(a) si ${\displaystyle \Phi \vdash \phi }$, entonces ${\displaystyle \phi \in \Phi }$,

(b) o bien ${\displaystyle \phi \in \Phi }$ o bien ${\displaystyle \lnot \phi \in \Phi }$,

(c) ${\displaystyle (\phi \lor \psi )\in \Phi }$ si y solo si ${\displaystyle \phi \in \Phi }$ o ${\displaystyle \psi \in \Phi }$,

(d) si ${\displaystyle (\phi \to \psi )\in \Phi }$ y ${\displaystyle \phi \in \Phi }$, entonces ${\displaystyle \psi \in \Phi }$,

(e) ${\displaystyle \exists x\phi \in \Phi }$ si y solo si existe un término ${\displaystyle t}$ tal que ${\displaystyle \phi {t \over x}\in \Phi }$.

Sea ${\displaystyle \Phi }$ un conjunto de fórmulas máximamente consistentes testigos.

Define una relación binaria en el conjunto de términos S ${\displaystyle t_{0}\sim t_{1}\!}$ si y solo si ${\displaystyle \;t_{0}=t_{1}\in \Phi }$; y sea ${\displaystyle {\overline {t}}\!}$ la clase de términos de equivalencia conteniendo ${\displaystyle t\!}$; y sea ${\displaystyle T_{\Phi }:=\{\;{\overline {t}}\;|\;t\in T^{S}\}}$ donde ${\displaystyle T^{S}\!}$ es el conjunto de términos basados en el conjunto de símbolo ${\displaystyle S\!}$.

Define la estructura S ${\displaystyle {\mathfrak {T}}_{\Phi }}$ sobre ${\displaystyle T_{\Phi }\!}$ el término-estructura correspondiente a ${\displaystyle \Phi }$ mediante:

(1) Para el ${\displaystyle n}$-ésimo ${\displaystyle R\in S}$, ${\displaystyle R^{{\mathfrak {T}}_{\Phi }}{\overline {t_{0}}}\ldots {\overline {t_{n-1}}}}$ si y solo si ${\displaystyle \;Rt_{0}\ldots t_{n-1}\in \Phi }$,

(2) Para el ${\displaystyle n}$-ésimo ${\displaystyle f\in S}$, ${\displaystyle f^{{\mathfrak {T}}_{\Phi }}({\overline {t_{0}}}\ldots {\overline {t_{n-1}}}):={\overline {ft_{0}\ldots t_{n-1}}}}$,

(3) Para ${\displaystyle c\in S}$, ${\displaystyle c^{{\mathfrak {T}}_{\Phi }}:={\overline {c}}}$.

Sea ${\displaystyle {\mathfrak {I}}_{\Phi }:=({\mathfrak {T}}_{\Phi },\beta _{\Phi })}$ el término-interpretación han asociado con ${\displaystyle \Phi }$, donde ${\displaystyle \beta _{\Phi }(x):={\bar {x}}}$.

${\displaystyle (*)\;}$ Para todo ${\displaystyle \phi }$,${\displaystyle \;{\mathfrak {I}}_{\Phi }\vDash \phi }$ si y solo si ${\displaystyle \;\phi \in \Phi }$.