Siguiente: Incompletitud Un nivel arriba: Aritmética de Peano Anterior: Demostrabilidad

Interpretaciones

Sea ${\cal L}$ una lógica. Una estructura-${\cal L}$ es una pareja $(E,\Phi)$, donde E es un conjunto y $\Phi$ es una correspondencia que asocia

• a cada constante c de ${\cal L}$ un elemento $\Phi(c)\in E$ (es decir asocia ``nombres'' con ``objetos'',
• a cada símbolo de función f_mⁿ, de aridad n, le asocia una función $\Phi(f_m^n):E^n\rightarrow E$, y
• a cada símbolo de relación R_mⁿ, de aridad n, le asocia una relación $\Phi(R_m^n)\subset E^n$.

Por ejemplo, $(I\!\!N,\mbox{\it id})$ es una estructura-AP, donde $I\!\!N$ es el conjunto de números naturales e id es la interpretación usual de los símbolos aritméticos. También, el conjunto de funciones de los naturales en los naturales $\mbox{\bf N}=I\!\!N^{I\!\!N}$ es una estructura-AP con la interpretación de los símbolos ``punto-a-punto'':

Cero 0	:	$\Phi(0)=\mbox{\bf0}$, donde $\mbox{\bf0}:n\mapsto 0$ es la función cero,
Sucesor s	:	$\Phi(s):f\mapsto f'$, donde $f':n\mapsto s(f(n))$ es la función f+1,
Suma +	:	$\Phi(+):(f,g)\mapsto f+g$, donde $f+g:n\mapsto f(n)+g(n)$ es la función suma punto-a-punto,
Igualdad =	:	$\Phi(=)=\{(f,g)\vert\forall n:f(n)=g(n)\}$, es decir, dos funciones son iguales si lo son sus correspondientes valores en cada punto.

Mencionemos una tercer estructura de AP. Para esto es menester introducir algunos tecnicismos. Un filtro en $I\!\!N$ es una colección de conjuntos ``grandes'', es decir, es un conjunto ${\cal F}\subset{\cal P}(I\!\!N)$ tal que

$$\begin{eqnarray*}\mbox{\rm i)} && I\!\!N\in{\cal F} \\ \mbox{\rm ii)} && A\in{... ...x{\rm iii)} && A,B\in{\cal F}\ \Rightarrow\ A\cup B\in{\cal F} \end{eqnarray*}$$

por ejemplo, el filtro de Frèchet ${\cal F}=\left\{\left\{m\in I\!\!N\vert m\geq n\right\}\right\}_{n\in I\!\!N}$ es, en efecto, un filtro. Un ultrafiltro es un filtro ${\cal U}$ consistente de los conjuntos ``más grandes posibles'', es decir, además de satisfacer los axiomas de filtro, satisface también

$$\mbox{\rm iv)}\ \ \ A\in{\cal P}(I\!\!N)\ \Rightarrow\ (A\in{\cal U})\lor(A^c\in{\cal U})$$

Bajo ciertas suposiciones es posible ver que todo filtro se extiende a un ultrafiltro (de hecho, a una infinidad de ultrafiltros). Sea pues ${\cal U}$ un ultrafiltro en $I\!\!N$ y sea $\sim_{{\cal U}}$ la relación en $\mbox{\bf N}$ definida como

$$f\sim_{{\cal U}} g\ \Leftrightarrow\ \{n\in I\!\!N\vert f(n)=g(n)\}\in U.$$

$\sim_{{\cal U}}$ es una relación de equivalencia congruente con las operaciones de $\mbox{\bf N}$ y por tanto $I\!\!N^*=\mbox{\bf N}/\sim_{{\cal U}}$ es una estructura-AP. Si $(E,\Phi)$ es una estructura-${\cal L}$ las fórmulas atómicas cerradas, es decir, aquellas que no tienen variables libres, de ${\cal L}$ se evalúan naturalmente en E. A partir de ellas se puede evaluar a todas los enunciados, es decir, fórmulas bien formadas que no tienen variables libres:

• $\phi=\neg\phi_1$ es verdadera en E si $\phi_1$ es falsa en E,
• $\phi=(\phi_1\rightarrow\phi_2)$ es verdadera en E si dado que $\phi_1$ es verdadera en E necesariamente ha de tenerse que $\phi_2$ es verdadera en E,
• $\phi=\forall x \phi_1(x)$ es verdadera en E si para cualquier sustitución de x por un elemento e en E, $\phi_1(e)$ es verdadera en E.

Si un enunciado $\phi$ es verdadero en E escribiremos $E\models \phi$, y en tal caso diremos que E es una interpretación o modelo de $\phi$. Si H es un conjunto de enunciados, escribiremos $E\models H$ si para cada $\phi\in H$ se cumple $E\models \phi$. Por ejemplo, la fórmula de la aritmética de Peano

$$\phi_0 \equiv \forall x(x\not=0\rightarrow\exists y(s(y)=x)$$

que asevera que todo elemento no nulo posee un antecesor es válida en $I\!\!N$, no lo es en $\mbox{\bf N}$ pues la función $x\mapsto(x\mbox{\rm mod }2)$ es no-nula mas no posee antecesor alguno. Sin embargo, $\phi_0$ sí es verdadera en $I\!\!N^*$.

$\phi$ es universalmente válido si para cualquier estructura-${\cal L}$ $(E,\Phi)$ se cumple $E\models \phi$. Si H es un conjunto de enunciados y $\phi$ es otro enunciado, diremos que $\phi$ es una consecuencia lógica de $\phi$, y escribiremos $H\models \phi$, si rige la implicación siguiente:

$$\forall E:(E\mbox{\rm estructura-${\cal L}$})\ \Rightarrow\ (E\models H\ \Rightarrow\ E\models \phi).$$

La lógica ${\cal L}$ se dice ser

sólida

si para cualquier conjunto de enunciados H y cualquier otro enunciado $\phi$ rige la implicación

$$H\vdash \phi\ \Rightarrow\ H\models \phi,$$

completa

si para cualquier conjunto de enunciados H y cualquier otro enunciado $\phi$ rige la implicación recíproca

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

Ambos el cálculo de predicados y la aritmética de Peano son sólidos. El Teorema de Completitud de Gödel asevera que cálculo de predicados es también completo. Su demostración excede los alcances del presente texto y por eso omitimos su demostración.
Siguiente: Incompletitud Un nivel arriba: Aritmética de Peano Anterior: Demostrabilidad