Posterior: Teorema de completitud Arriba: Coherencia y completitud Anterior: Coherencia y completitud

Teorema de coherencia

Hemos dicho que un conjunto de hipótesis $H\subset \mbox{\it Pbf}(X)$ es consistente si no se deducen de él una proposición y la negación de esa proposición. El cálculo proposicional será consistente si el mero conjunto de axiomas no deduce una pareja de proposiciones contradictorias, es decir, si $\emptyset$ es consistente. El TEOREMA DE COHERENCIA, llamado en inglés Soundness Theorem, asevera, precisamente, que el cálculo proposicional es consistente (por lo cual a dicho teorema se le llama también DE LA CONSISTENCIA).

Teorema 3.1 (de la Coherencia)   Sea $H$ un conjuntode proposiciones y sea $p$ otra proposición. Entonces:

$$H\vdash p\ \Rightarrow \ H\models p$$ (1)

Es decir, si $p$ se deduce de $H$ entonces $p$ es una consecuencia lógica de $H$. En particular, si $H=\emptyset$, la implicación (1) dice que todo teorema es una tautología.

Demostración
Probaremos la implicación (1) por inducción en la longitud de una prueba de $p$ a partir de $P$. Hemos de probar que toda vez que $P$ es verdadera bajo una asignación, entonces $p$ lo es también bajo esa asignación. Caso base. Supongamos que $p$ es un axioma o un elemento de $P$. Tenemos tres casos:

1. $p$ es una axioma del tipo $A_1$: Si $p=(q\rightarrow (r\rightarrow q))$ tenemos, por el lema 2.1.2, que $p$ es una tautología si y sólo si $\{q,r\}\models q$. Pero esto vale trivialmente.
2. $p$ es una axioma del tipo $A_2$: Si $p=(q\rightarrow (r\rightarrow s))\rightarrow ((q\rightarrow r)\rightarrow (q\rightarrow s))$ tenemos, por el lema 2.1.2, que $p$ es una tautología si y sólo si $Q\models s$, donde $Q=\{q\rightarrow (r\rightarrow s),q\rightarrow r,q\}$. Probemos esto último. Sea $\mbox{\boldmath$\epsilon$}$ una asignación tal que $\langle \mbox{\boldmath$\epsilon$},t \rangle = 1$ para cada proposición $t\in Q$. Por Modus Ponens (MP), considerando $q$ y $q\rightarrow r$ (ver ejemplo 2.1.1), se tiene $\langle \mbox{\boldmath$\epsilon$},r \rangle = 1$. También por MP, considerando $q$ y $q\rightarrow (r\rightarrow s)$, se tiene $\langle \mbox{\boldmath$\epsilon$},r\rightarrow s \rangle = 1$. Igual, por MP, resulta $\langle \mbox{\boldmath$\epsilon$},s \rangle = 1$.
3. $p$ es una axioma del tipo $A_3$: Si $p=\left(\neg q\rightarrow r\right) \rightarrow \left(\left(\neg q\rightarrow \neg r\right)\rightarrow q\right)$ tenemos, por el lema 2.1.2, que $p$ es una tautología si y sólo si $\{\neg q\rightarrow r,\neg q\rightarrow \neg r\}\models q$. Sea $\mbox{\boldmath$\epsilon$}$ una asignación tal que $\langle \mbox{\boldmath$\epsilon$},\neg q\rightarrow r \rangle = 1$ y $\langle \mbox{\boldmath$\epsilon$},\neg q\rightarrow \neg r \rangle = 1$. Entonces necesariamente $\langle \mbox{\boldmath$\epsilon$},\neg q \rangle = 0$, es decir $\langle \mbox{\boldmath$\epsilon$},q \rangle = 1$.
4. Si $p$ es una hipótesis, es decir, $p\in P$ entonces evidentemente $P\models p$.

Caso inductivo. En el ejemplo 2.1.1 vimos que la propiedad de asumir el valor verdadero ``es invariante bajo Modus Ponens''. De aquí se ve inmediatamente que vale el caso inductivo. $\quad\Box$

Corolario 3.1   El cálculo de proposiciones es consistente. Es decir, no hay proposición alguna tal que tanto ella como su negación sean demostrables.

En efecto, si hubiera tal proposición, tanto ella como su negación serían tautologías, lo cual es imposible. $\quad\Box$
Posterior: Teorema de completitud Arriba: Coherencia y completitud Anterior: Coherencia y completitud