Posterior: Irresolubilidad en la Aritmética Arriba: Coherencia y completitud Anterior: Algebra de Lindenbaum

Completitud

Teorema 4.2 (de completitud)   Toda fórmula que es universalmente válida es demostrable. Es decir, si $\phi\in\mbox{\rm Fbf}(L)$ entonces

$$\models\phi\ \ \ \Rightarrow\ \ \ \vdash \phi.$$

Demostración
Veremos que si $\phi$ no es demostrable entonces no es universalmente válida, es decir, existe un modelo de $\neg \phi$. Ya que $\not\vdash \phi$ entonces $[\phi]$ no puede ser el elemento máximo $\mbox{\bf 1}$ del álgebra de Lindenbaum ${\cal L}(L)$ ni $[\neg\phi]$ es el elemento mínimo $\mbox{\bf0}$. Sea $\left(\phi_n(x_n)\right)_{n\in{\mathbb{N}}}$ una enumeración de las fórmulas en $\mbox{\rm Fbf}(L)$ con una sola variable libre. Consideremos

$${\cal B} = \left\{\left.\left\{\phi_n(x_n\leftarrow y)\vert\, y\in\mbox{\rm Var}\right\}\right\vert n\in{\mathbb{N}}\right\}$$

Por el Lema de Tarski (teorema en la sección ) se tiene que existe un ultrafiltro $F$ en el álgebra de Lindenbaum ${\cal L}(L)$ que contiene a $[\neg\phi]$ y preserva las intersecciones en ${\cal B}$. Por la relación (3) hemos de tener entonces

$${[\forall x_n\,\phi_n(x_n)]\in F} \ \ \ \Leftrightarrow\ \ \ \forall y\in\mbox{\rm Var}:\ [\phi_n(x_n\leftarrow y)]\in F$$ (4)

Con estos preliminares, pasemos ahora a construir el modelo de $\neg \phi$. Introduzcamos la siguiente relación en el conjunto de términos:

$$\forall \xi_1,\xi_2\in\mbox{\rm Term}(L):\ \xi_1\sim_F \xi_2\ \ \ \Leftrightarrow\ \ \ {[\xi_1=\xi_2]\in F}$$ (5)

$\sim_F$ es una relación de equivalencia pues, por un lado, la igualdad de términos es demostrablemente reflexiva, simétrica y transitiva y, por otro lado, la clase de teoremas $\mbox{\bf 1}$ es un elemento del ultrafiltro $F$. Sea $M=\mbox{\rm Term}(L)/\sim_F$ el espacio cociente. $M$ no es vacío y su cardinalidad es a lo sumo la de $\mbox{\rm Term}(L)$, es decir, es a lo sumo numerable. Para cada símbolo de función $f^n_i$ en la signatura de $L$, definamos

$$\overline{f^n_i}\left([\xi_1],\ldots,[\xi_n]\right) = [\xi] \... ...ightarrow\ \ \ \left[f^n_i(\xi_1,\ldots,\xi_n)=\xi\right]\in F.$$

Similarmente, para cada símbolo de relación $R^n_i$ en la signatura de $L$, definamos

$$\left([\xi_1],\ldots,[\xi_n]\right)\in \overline{R^n_i}\ \ \ \Leftrightarrow\ \ \ \left[R^n_i(\xi_1,\ldots,\xi_n)\right]\in F.$$

Tenemos pues que $\mathfrak{M}=(M,\overline{\cdot})$ es una $L$-estructura. En ella, se tiene para cualquier fórmula $\phi(\mbox{\bf x})\in\mbox{\rm Fbf}(L)$:

$$\mathfrak{M}\models\phi(\mbox{\bf x})\ \ \ \Leftrightarrow\ \ \ {[\phi(\mbox{\bf x})]\in F}.$$ (6)

lo cual puede verse por inducción en la complejidad de la fórmula $\phi(\mbox{\bf x})$. Ya que $[\neg\phi]\in F$, $\mathfrak{M}$ es un modelo de $\neg \phi$ y en consecuencia $\phi$ no podría ser universalmente válida. $\quad\Box$

Una fórmula $\phi\in\mbox{\rm Fbf}(T)$ se dice ser REFUTABLE si su negación es demostrable, es decir, $\vdash\neg\phi$. Naturalmente $\phi$ es IRREFUTABLE si no es refutable, es decir $\not\vdash\neg\phi$. El Teorema de Completitud implica que si $\phi$ es irrefutable, entonces $\neg \phi$ no puede ser universalmente válida y, siguiendo la misma técnica de la demostración del Teorema de Completitud, existe un modelo a lo sumo numerable de $\phi$. Así pues, podemos formular la

Observación 4.1   Un conjunto finito de fórmulas bien formadas es consistente si y sólo si posee un modelo a lo sumo numerable.

En efecto, si $\Phi = \left(\phi_i\right)_{i=1}^n$ es consistente, entonces $\phi_1 \land\cdots\land \phi_n$ es irrefutable y por tanto posee un modelo a lo sumo numerable. Recíprocamente, si $\Phi$ posee un modelo, entonces necesariamente $\Phi$ es consistente. $\quad\Box$

La hipótesis de finitud del conjunto de fórmulas consistente puede omitirse y esto dará una formulación alternativa del Teorema de Completitud. Para ver que en efecto puede omitirse presentaremos un resultado clásico de la llamada Teoría de Modelos. Supongamos que se tiene una colección $\left(\mathfrak{M}_i = (M_i,\overline{\cdot}^i)\right)_{i\in I}$ de $L$-estructuras, indicada con índices en un conjunto $I$. Sea $F$ un ultrafiltro sobre $I$ y sea $\mathfrak{M}_F$ el ultraproducto de la colección, tal como se definió en la sección .

Teorema 4.3 (de os)   Para cualquier fórmula $\phi\in\mbox{\rm Fbf}(L)$ se tiene

$$\mathfrak{M}_F\models \phi(\mbox{\bf x}\leftarrow \pi_F(\mb... ...ak{M}_i\models \phi(\mbox{\bf x}\leftarrow a_i)\right\}\in F$$ (7)

Demostración
La demostración completa de este teorema excede los propósitos de este curso. Por tanto, sin entrar en detalles técnicos, nos restringiremos a bosquejar la demostración y remitimos al lector al texto [BSl] para conocer los detalles. Se procede por inducción en la complejidad de la fórmula $\phi$. El caso base corresponde a que $\phi$ sea un átomo. La relación (7) corresponde exactamente a la relación () en la sección . El caso inductivo se divide en varios subcasos dependiendo de la forma de $\phi$. Si $\phi$ es una conjunción, (7) será válida porque la intersección de conjuntos en el ultrafiltro está en el ultrafiltro. Si $\phi$ es una negación, (7) será válida porque al ser $F$ un ultrafiltro, para cualquier conjunto de índices se tendrá que bien él, o su complemento, está en el ultrafiltro. Si $\phi$ es la cuantificación existencial de alguna fórmula, (7) será válida porque dado un ``vector'' que realice la veracidad de $\phi$ en el ultraproducto, las entradas en el vector la realizarán en cada $L$-estructura componente, y, viceversa, si se tiene entradas que la realicen en cada componente, al conjuntarlas (acaso apelando al axioma de selección) se forma con ellas un ``vector'' que realice la veracidad de $\phi$ en el ultraproducto. Los subcasos aquí delineados agotan el caso inductivo. $\quad\Box$

Teorema 4.4 (de compacidad)   Un conjunto de fórmulas $T\subset\mbox{\rm Fbf}(L)$ es consistente si y sólo si todo conjunto finito $T_0\subset T$ es consistente.

Demostración
Parte ``si''. Si $T$ fuese inconsistente, entonces habría una fórmula $\phi\in\mbox{\rm Fbf}(L)$ tal que $T\vdash \phi$ y $T\vdash \neg\phi$. Sea $T_0$ el conjunto de fórmulas en $T$ que aparecen en una demostración de $\phi$ o en una demostración de $\neg \phi$ a partir de $T$. Entonces $T_0\subset T$ es finito y es inconsistente.

Parte ``sólo si''. Esto es una consecuencia directa de que el operador $\mbox{\it Ded}$ es de ``cerradura'' (véase la observación que sigue a la proposición 3.3.1). $\quad\Box$ Ahora sí, estamos en posibilidad de suprimir la hipótesis de finitud en la observación 3.4.1.

Teorema 4.5 (presentación alternativa de completitud)   Todo conjunto de fórmulas $T\subset\mbox{\rm Fbf}(L)$ que sea consistente posee un modelo.

Demostración
Sea $T$ un conjunto de fórmulas que es consistente. Por el Teorema de Compacidad, toda parte finita de $T$ es consistente y, por la observación 3.4.1, posee un modelo. Sea pues $I$ la colección de partes finitas de $T$: para cada $i\in I$, $i$ es un conjunto de fórmulas, finito y consistente. Sea $\mathfrak{M}_i$ un modelo de $i$. Sea $C^+(i) = \{j\in I\vert i\subseteq j\}$ el cono superior de $i$ en $I$. Claramente $C^+(i) \not = \emptyset$ y además:

$$i_1,\ldots,i_n\in I\ \ \Rightarrow\ \ \left(i_1 \cup\cdots\cup i_n\right) \subset C^+(i_1) \cap\cdots\cap C^+(i_n).$$

Así pues, la colección de subconjuntos $\left(C^+(i)\right)_{i\in I}$ tiene la propiedad de la intersección finita. Consecuentemente, puede extenderse a un ultrafiltro $F$ sobre $I$. Consideremos el ultraproducto $\mathfrak{M}_F$ de $\left(\mathfrak{M}_i\right)_{i\in I}$ reducido por el ultrafiltro $F$. Veamos que $\mathfrak{M}_F\models T$. En efecto, sea $\phi\in T$. Entonces existe $i_0\in I$ tal que $i_0=\{\phi\}$. Resulta claro que

$$C^+(i_0)\subset\{i\in I\vert\mathfrak{M}_i\models \phi\}.$$

Por tanto, este último conjunto está en el ultrafiltro $F$. Por el Teorema de os (relación (7)) se tiene que $\mathfrak{M}_F\models \phi$. $\quad\Box$
A esta presentación alternativa del Teorema de Completitud se le llama Teorema de Gödel-Henkin.
Posterior: Irresolubilidad en la Aritmética Arriba: Coherencia y completitud Anterior: Algebra de Lindenbaum