Posterior: Completitud Arriba: Coherencia y completitud Anterior: Coherencia

Algebra de Lindenbaum

En el conjunto de fórmulas bien formadas $\mbox{\rm Fbf}(L)$ definamos la relación siguiente:

$$\phi \equiv \psi \ \ \ \Leftrightarrow\ \ \ \left(\vdash \p... ...\psi\right) \;\&\; \left(\vdash \psi \rightarrow \phi\right)$$ (1)

Es claro que $\equiv$ es una relación de equivalencia. El cociente ${\cal L}(L) = \mbox{\rm Fbf}(L)/\equiv$ se dice ser el ´ALGEBRA DE LINDENBAUM del alfabeto $L$. ${\cal L}(L)$ es, en efecto, un álgebra booleana con las operaciones inducidas por los conectivos lógicos en $\mbox{\rm Fbf}(L)$. El elemento máximo es la clase de equivalencia de los teoremas y el elemento mínimo la de las contradicciones. Más aún, el orden del álgebra queda caracterizado por la relación:

$${[\phi]} \leq [\psi] \ \ \ \Leftrightarrow\ \ \ \vdash \phi \rightarrow \psi$$ (2)

Recordamos que si $\phi(x)$ es una fórmula donde $x$ aparece libre (si apareciese también ligada entonces mediante un mero renombramiento de variables se deja en $\phi$ sólo las apariciones libres de la variable $x$), entonces $\phi(x\leftarrow y)$ denota a la fórmula obtenida de sustituir toda aparición de $x$ por la variable $y$. Se tiene

$${[\forall x\,\phi(x)]} = \bigwedge\left\{[\phi(x\leftarrow y)]\vert\, y\in\mbox{\rm Var}\right\}$$ (3)

En efecto, por el axioma $\mbox{\rm Ax}_4$ se tiene

$$\vdash \forall x\,\phi(x) \rightarrow \phi(x\leftarrow y).$$

Por tanto ${[\forall x\,\phi(x)]} \leq \bigwedge\left\{[\phi(x\leftarrow y)]\vert\, y\in\mbox{\rm Var}\right\}$. Ahora, supongamos que la clase $[\psi]$ sea una cota inferior de $\left\{[\phi(x\leftarrow y)]\vert\, y\in\mbox{\rm Var}\right\}$. Sea $y$ una variable que no aparezca en $\psi$. Entonces hemos de tener $\vdash \psi \rightarrow \phi(x\leftarrow y)$. Por Generalización se ha de tener también $\vdash \psi \rightarrow \forall y\,\phi(y)$. Así pues, $[\psi] \leq {[\forall x\,\phi(x)]}$.
Posterior: Completitud Arriba: Coherencia y completitud Anterior: Coherencia