Ver George Tourlakis, la Lógica Matemática (2008), página 93 :
3.2.1 Metatheorem (Post Tautología Teorema) : Si $\Gamma \vDash_{TAUT} A$,$\Gamma \vdash A$.
Prueba. Es más conveniente para probar el contrapositivo, es decir, si $\Gamma \nvdash A$, ,, a continuación, $\Gamma \nvDash_{TAUT} A$
Algunos hechos son necesarios :
Afirman Que Uno. No es una enumeración $G_0,G_1, \ldots$ de todas las fórmulas de la lógica proposicional.
Consulte la página 95 :
Asumir la hipótesis de lado, $\Gamma \nvdash A$.
Estamos próximos a la construcción de un conjunto de fórmulas, $\Delta$, que es tan grande como sea posible con el
las propiedades que se incluye el $\Gamma$, pero también
$\Delta \nvdash A$.
Construimos $\Delta$ por etapas, $\Delta_0, \Delta_1, \ldots$ por una definición inductiva, la adición de no más de una fórmula en cada paso.
El $\Delta_n$ secuencia es:
$\Delta_0 = \Gamma$
Para $n \ge 0$ :
$\Delta_{n+1} = \Delta_n \cup \{ G_n \}$ si $\Delta_n \cup \{ G_n \} \nvdash A$
$\Delta_{n+1} = \Delta_n \cup \{ \lnot G_n \}$ si $\Delta_n \cup \{ \lnot G_n \} \nvdash A$
$\Delta_n$, otra cosa.
Por lo tanto, en cada etapa se agrega a la serie que estamos construyendo en más de una fórmula, que es un miembro o una negación de un miembro de la secuencia $\{ G_n \}$.
Definimos $\Delta = \bigcup_{n \ge 0} \Delta_n$, formando $\Delta$ como el conjunto de todos los miembros que se encuentran en todas las $\Delta_n$.
Varios de los hechos siguientes :
Reclamación Dos. $\Gamma \subseteq \Delta$.
Reclamación De Tres. Para $n \ge 0, \Delta_n \nvdash A$. De esta manera se sigue por la inducción en $n$.
Reclamación De Cinco. $\Delta \nvdash A$.
Reclamación De Seis. Para cada fórmula $B$, $B \in \Delta$ o $\lnot B \in \Delta$, pero no tanto.
Reclamación De Siete. $\Delta$ es deductivamente cerrado, es decir, si $\Delta \vdash B$,$B \in \Delta$.
Ahora podemos definir una valoración $v$ que verifica $\Gamma \nvDash A$.
Definir una valoración $v$ estableciendo, para cada variable $p$, $v(p) = t$ iff $p \in \Delta$.
La Reivindicación Principal. Para todas las fórmulas de $B, v(B) = t$ fib $B \in \Delta$.
La prueba es por inducción sobre la complejidad de $B$. Tenemos los siguientes casos:
(i) $B$ es una variable : por definición de $v$.
A continuación, compruebe todos los casos de acuerdo a la definición inductiva de la fórmula.
Después de eso, podemos fácilmente concluir la prueba de la siguiente manera: Por la Demanda Principal, cada
fórmula $B \in \Delta$ - y, por tanto, cada fórmula $B \in \Gamma$ desde $\Gamma \subseteq \Delta$ - satisface $v(B) = t$.
Por otro lado, como $\Delta \nvdash A$ debe $A \notin \Delta$; por lo tanto, de nuevo a través de la Demanda Principal, $v(A) = f$. Por lo tanto,$\Gamma \nvDash_{TAUT} A$.
Consulte la página 99 :
3.2.2 Corolario. Si $\vDash B$,$\vdash B$.
Prueba. Caso de $\Gamma = \emptyset$.
Nota
Un tipo diferente de prueba del Teorema de Completitud para la lógica proposicional (debido a Kalmar, 1935) se puede encontrar en Elliott Mendelson, Introducción a la lógica matemática (4ed - 1997), página 42; también en este caso se requiere la prueba de un lexema por inducción sobre la complejidad de la fórmula.
