3.2: Completitud

Arreglemos una colección de axiomas no lógicos,\(\Sigma\). Nuestro objetivo en esta sección es mostrar eso para cualquier fórmula\(\phi\), si\(\Sigma \models \phi\), entonces\(\Sigma \vdash \phi\). En cierto sentido, esta es la única interpretación posible de la frase “puedes probar cualquier cosa que sea verdad”, si estás discutiendo la adecuación del sistema deductivo. Decir que\(\phi\) es cierto cada vez que\(\Sigma\) es una colección de verdaderos axiomas es precisamente decir que\(\Sigma\) lógicamente implica\(\phi\). Así, el Teorema de la Completitud dirá que siempre que\(\phi\) sea lógicamente implícito por\(\Sigma\), hay una deducción de\(\Sigma\) de\(\phi\). Entonces el Teorema de la Integtud es lo contrario del Teorema de la Solidez.

Tenemos que comenzar con una breve discusión de consistencia.

Definición 3.2.1: consistencia

Dejar\(\Sigma\) ser un conjunto de\(\mathcal{L}\) -fórmulas. Diremos que\(\Sigma\) es inconsistente si hay una deducción\(\Sigma\) de\(\left[ \left( \forall x \right) x = x \right] \land \neg \left[ \left( \forall x \right) x = x \right]\). Decimos que\(\Sigma\) es consistente si no es inconsistente.

Entonces\(\Sigma\) es inconsistente si\(\Sigma\) demuestra una contradicción. El Ejercicio 1 te pide demostrar que si\(\Sigma\) es inconsistente, entonces hay una deducción\(\Sigma\)\(\mathcal{L}\) de cada fórmula. Por conveniencia notacional, aceptemos usar el símbolo\(\perp\) (léase “falso” o “eet”) para la oración contradictoria\(\left[ \left( \forall x \right) x = x \right] \land \neg \left[ \left( \forall x \right) x = x \right]\). Todo lo que tendrás que recordar es que\(\perp\) es una oración que está en todos los idiomas y que es cierta en ninguna estructura.

Teorema 3.2.2: Teorema de la Integtud

Supongamos que\(\Sigma\) es un conjunto de\(\mathcal{L}\) -fórmulas y\(\phi\) es una\(\mathcal{L}\) -fórmula. Si\(\Sigma \models \phi\), entonces\(\Sigma \vdash \phi\).

Prueba

Chaff: Este teorema fue establecido en 1929 por el matemático austriaco Kurt Gödel, en su tesis doctoral. Si aún no lo has recogido, debes saber que la obra de Gödel es central para el desarrollo de la lógica en el siglo XX. Es responsable de la mayoría de los principales resultados que expondremos en el resto del libro: El teorema de la integridad, el teorema de la compacidad y los dos teoremas de incompletitud. Gödel era un hombre absolutamente brillante, con una personalidad compleja y problemática. Una biografía maravillosa y atractiva de Gödel es [Dawson 97]. El primer volumen de las obras recopiladas de Gödel, [Gödel-Works], también incluye una biografía y comentarios introductorios sobre sus trabajos que pueden ayudar a tu comprensión de esta maravillosa matemática.

La prueba que presentamos del Teorema de Completura se basa en el trabajo de Leon Henkin. La idea de la prueba de Henkin es brillante, pero los detalles tardan algún tiempo en resolverse.

Antes de involucrarnos en los detalles, veamos un esquema aproximado de cómo procede el argumento. Hay algunas simplificaciones y una o dos mentiras directas en el esquema, pero vamos a enderezar todo a medida que elaboremos la prueba.

Esquema de la Prueba

Habrá un argumento preliminar que demostrará que es suficiente para probar que si\(\Sigma\) es un conjunto consistente de oraciones, entonces\(\Sigma\) tiene un modelo. Entonces procederemos a asumir que se nos da tal conjunto de oraciones, y construiremos un modelo para\(\Sigma\).

La construcción del modelo procederá en varios pasos, pero la idea central se introdujo en el Ejemplo 1.6.4. Los elementos del modelo serán términos libres de variables de un idioma. Construiremos este modelo para que las fórmulas que serán verdaderas en el modelo sean precisamente las fórmulas que están en un cierto conjunto de fórmulas, a las que llamaremos\(\Sigma^\prime\). Nos aseguraremos de eso\(\Sigma \subseteq \Sigma^\prime\), así que todas las fórmulas de\(\Sigma\) serán ciertas en este modelo construido. En otras palabras, habremos construido un modelo de\(\Sigma\).

Para hacer el trabajo de construcción tomaremos nuestro conjunto de\(\mathcal{L}\) oraciones dado\(\Sigma\) y lo extenderemos a un conjunto más grande de oraciones\(\Sigma^\prime\) en un idioma más grande\(\mathcal{L}^\prime\). Hacemos esta extensión en dos pasos. Primero, agregaremos algunos axiomas nuevos, llamados Henkin Axioms, para obtener una colección\(\hat{\Sigma}\). Entonces nos extenderemos\(\hat{\Sigma}\) a\(\Sigma^\prime\) de tal manera que:

1. \(\Sigma^\prime\)es consistente.
2. Por cada\(\mathcal{L}^\prime\) -oración\(\theta\), ya sea\(\theta \in \Sigma^\prime\) o\(\left( \neg \theta \right) \in \Sigma^\prime\).

Así diremos que\(\Sigma^\prime\) es una extensión máxima consistente de\(\Sigma\), donde máxima significa que es imposible agregar ninguna oración\(\Sigma^\prime\) sin hacer\(\Sigma^\prime\) inconsistentes.

Ahora hay dos posibles fuentes de problemas en esta expansión de\(\Sigma\) a\(\Sigma^\prime\). El primero es que vamos a cambiar idiomas de\(\mathcal{L}\) a\(\mathcal{L}^\prime\), donde\(\mathcal{L} \subseteq \mathcal{L}^\prime\). Es concebible que no\(\Sigma\) sea consistente cuando se vea como un conjunto\(\mathcal{L}^\prime\) de oraciones, aunque\(\Sigma\) sea consistente cuando se vea como un conjunto\(\mathcal{L}\) de oraciones. La razón por la que esto podría suceder es que hay más\(\mathcal{L}^\prime\) deducciones que\(\mathcal{L}\) deducciones, y una de estas nuevas deducciones simplemente podría pasar a ser una deducción de\(\perp\). Afortunadamente, Lemma 3.2.3 nos mostrará que esto no sucede, por lo que\(\Sigma\) es consistente como un conjunto de\(\mathcal{L}^\prime\) -oraciones. El otro posible problema está en nuestras dos extensiones de\(\Sigma\), primero a\(\hat{\Sigma}\) y luego a\(\Sigma^\prime\). Ciertamente podría suceder que pudiéramos agregar una oración a de tal\(\Sigma\) manera que se haga\(\Sigma^\prime\) inconsistente. Pero Lema 3.2.4 y Ejercicio 4 demostrarán que\(\Sigma^\prime\) sigue siendo consistente.

Una vez que tengamos nuestro conjunto máximo consistente de oraciones\(\Sigma^\prime\), construiremos un modelo\(\mathfrak{A}\) y probaremos que las oraciones de las\(\mathcal{L}^\prime\) que están en\(\Sigma^\prime\) son precisamente las oraciones en las que son verdaderas\(\mathfrak{A}\). Así,\(\mathfrak{A}\) será un modelo de\(\Sigma^\prime\), y como\(\Sigma \subseteq \Sigma^\prime\),\(\mathfrak{A}\) será un modelo de\(\Sigma\), también.

Esto parece desalentador, pero si mantenemos nuestro ingenio sobre nosotros y hacemos las cosas paso a paso, todo se unirá al final.

Argumento preliminar

Así que arreglemos nuestra configuración para el resto de esta prueba. Estamos trabajando en un idioma\(\mathcal{L}\). Para los efectos de esta prueba, asumimos que el lenguaje es contable, lo que significa que las fórmulas de\(\mathcal{L}\) pueden escribirse en una lista infinita\(\alpha_1, \alpha_2, \ldots, \alpha_n, \ldots\). (Un esquema de los cambios en la prueba necesaria para el caso cuando no\(\mathcal{L}\) es contable se puede encontrar en el Ejercicio 6.)

Se nos da un conjunto de fórmulas\(\Sigma\), y lo estamos asumiendo\(\Sigma \models \phi\). Tenemos que demostrarlo\(\Sigma \vdash \phi\).

Obsérvese que podemos suponer que\(\phi\) es una frase: Por Lema 2.7.2,\(\Sigma \vdash \phi\) si y sólo si hay una deducción\(\Sigma\) del cierre universal de\(\phi\). También, por los comentarios que siguen a Lema 2.7.3, también podemos suponer que cada elemento de\(\Sigma\) es una oración. Entonces, ahora todos (!) tenemos que hacer es probar que si\(\Sigma\) es un conjunto de oraciones y\(\phi\) es una oración y si\(\Sigma \models \phi\), entonces\(\Sigma \vdash \phi\).

Ahora afirmamos que basta con probar el caso donde\(\phi\) está la sentencia\(\perp\). Por supongamos que sabemos que si\(\Sigma \models \perp\), entonces\(\Sigma \vdash \perp\), y supongamos que se nos da una frase\(\phi\) tal que\(\Sigma \models \phi\). Entonces\(\Sigma \cup \left( \neg \phi \right) \models \perp\), como no hay modelos de\(\Sigma \cup \left( \neg \phi \right)\), entonces\(\Sigma \cup \left( \neg \phi \right) \vdash \perp\). Esto nos dice, por el Ejercicio 4 en la Sección 2.7, que\(\Sigma \vdash \phi\), según sea necesario.

Entonces hemos reducido lo que tenemos que hacer para probar eso si\(\Sigma \models \perp\), entonces\(\Sigma \vdash \perp\), por\(\Sigma\) un conjunto de\(\mathcal{L}\) -oraciones. Esto equivale a decir que si no hay modelo de\(\Sigma\), entonces\(\Sigma \vdash \perp\). Trabajaremos con lo contrapositivo: Si\(\Sigma \nvdash \perp\), entonces hay un modelo de\(\Sigma\). En otras palabras, demostraremos:

Si\(\Sigma\) es un conjunto consistente de oraciones, entonces hay un modelo de\(\Sigma\).

Esto termina el argumento preliminar que se prometió en el esbozo de la prueba. Ahora, vamos a suponer que\(\Sigma\) es un conjunto consistente de\(\mathcal{L}\) -oraciones y vamos a hacer la tarea de construir un modelo de\(\Sigma\).

Cambiar el idioma de\(\mathcal{L}\) a\(\mathcal{L}_1\)

El modelo de lo\(\Sigma\) que construiremos será un modelo cuyos elementos sean términos libres de variables de un lenguaje. Esto podría dar lugar a problemas. Por ejemplo, supongamos que no\(\mathcal{L}\) contiene símbolos constantes. Entonces no habrá términos libres de variables de\(\mathcal{L}\). O, tal vez\(\mathcal{L}\) tiene exactamente un símbolo constante\(c\), sin símbolos de función, una relación unaria\(P\), y

\[\Sigma = \{ \exists x P ( x ) , \neg P ( c ) \}.\]

Aquí\(\Sigma\) es consistente, pero ninguna estructura cuyo universo es\(\{ c \}\) (\(c\)es el único charrán libre de variables de\(\mathcal{L}\)) puede ser un modelo de\(\Sigma\). Entonces tenemos que expandir nuestro lenguaje para darnos suficientes símbolos constantes para construir nuestro modelo.

Así que vamos\(\mathcal{L}_0 = \mathcal{L}\), y definir

\[\mathcal { L } _ { 1 } = \mathcal { L } _ { 0 } \cup \left\{ c _ { 1 } , c _ { 2 } , \dots , c _ { n } , \dots \right\},\]

donde los\(c_i\)'s son nuevos símbolos constantes.

Chaff:Te diste cuenta de que cuando estábamos definiendo\(\mathcal{L}_1\) tomamos algo que ya sabíamos,\(\mathcal{L}\), y le dimos un nuevo nombre,\(\mathcal{L}_0\)? Cuando estás leyendo matemáticas y sucede algo así, casi siempre es una pista de que lo que pase a continuación va a ser iterado, en este caso para construir\(\mathcal{L}_2\),\(\mathcal{L}_3\), y así sucesivamente. En esos cursos de literatura que tomamos, llamaron a eso presagiar.

Decimos (por la razón obvia) que\(\mathcal{L}_1\) es una extensión por constantes de\(\mathcal{L}_0\). Como se menciona en el esquema, no queda claro de inmediato que\(\Sigma\) siga siendo consistente cuando se ve como una colección de\(\mathcal{L}_1\) -oraciones en lugar de\(\mathcal{L}\) -oraciones. El siguiente lema, cuya prueba se retrasa, demuestra que\(\Sigma\) sigue siendo consistente.

Lema 3.2.3.

Si\(\Sigma\) es un conjunto consistente de\(\mathcal{L}\) -oraciones y\(\mathcal{L}_1\) es una extensión por constantes de\(\mathcal{L}\), entonces\(\Sigma\) es consistente cuando se ve como un conjunto de\(\mathcal{L}_1\) -oraciones.

Las constantes que hemos agregado a la forma\(\mathcal{L}_1\) se llaman constantes de Henkin, y sirven para un propósito particular. Serán los testigos que nos permitan asegurar que en cualquier momento\(\Sigma\) reclame\(\exists x \phi \left( x \right)\), entonces en nuestro modelo construido\(\mathfrak{A}\), habrá un elemento (que será una de estas constantes\(c\)) tal que\(\mathfrak{A} \models \phi \left( c \right)\).

Chaff: Recordemos que la notación\(\exists x \phi \left( x \right)\) implica que\(\phi\) es una fórmula con\(x\) como la única variable libre. Entonces\(\phi \left( c \right)\) es el resultado de reemplazar las ocurrencias libres\(x\) de por el símbolo constante\(c\). Así\(\phi \left( c \right)\) es\(\phi_c^x\).

El siguiente paso en nuestra construcción asegura que las constantes Henkin serán los testigos de las sentencias existenciales en\(\Sigma\).

Extender\(\Sigma\) para incluir los axiomas Henkin

Considera la colección de oraciones de la forma\(\exists x \theta\) en el idioma\(\mathcal{L}_0\). Como el lenguaje\(\mathcal{L}_0\) es contable, la colección de\(\mathcal{L}_0\) -oraciones es contable, por lo que podemos enumerar todas esas oraciones de la forma\(\exists x \theta\), enumerándolas por los enteros positivos:

\[\exists x \theta _ { 1 } , \exists x \theta _ { 2 } , \exists x \theta _ { 3 } , \ldots , \exists x \theta _ { n } , \dots.\]

Ahora usaremos las constantes Henkin de\(\mathcal{L}_1\) para agregar a\(\Sigma\) contablemente muchos axiomas, llamados axiomas Henkin. Estos axiomas garantizarán que toda oración existencial que sea afirmada por\(\Sigma\) tenga un testimonio en nuestra estructura construida\(\mathfrak{A}\). La colección de axiomas Henkin es

\[H _ { 1 } = \{ \left[ \exists x \theta _ { i } \right] \rightarrow \theta _ { i } \left( c _ { i } \right) | \left( \exists x \theta _ { i } \right) \: \text{is an} \: \mathcal{L}_0 \: \text{sentence} \},\]

donde\(\theta_i \left( c_i \right)\) es la abreviatura de\(\theta^x_{c_i}\).

Ahora vamos\(\Sigma_0 = \Sigma\) y definamos

\[\Sigma _ { 1 } = \Sigma _ { 0 } \cup H _ { 1 }.\]

Chaffa: ¡Presagio!

Como\(\Sigma_1\) contiene muchas más frases que\(\Sigma_0\), parece totalmente posible que ya no\(\Sigma_1\) sea consistente. Afortunadamente, el siguiente lema demuestra que ese no es el caso.

lema 3.2.4.

Si\(\Sigma_0\) es un conjunto consistente de oraciones y\(\Sigma_1\) se crea agregando axiomas Henkin a\(\Sigma_0\), entonces\(\Sigma_1\) es consistente.

Ahora tenemos\(\Sigma_1\), un conjunto consistente de\(\mathcal{L}_1\) -oraciones. Podemos repetir esta construcción, construyendo un lenguaje más amplio\(\mathcal{L}_2\) que consiste en\(\mathcal{L}_1\) junto con un conjunto infinito de nuevas constantes Henkin\(k_i\). Entonces podemos dejar\(H_2\) ser un nuevo conjunto de axiomas Henkin:

\[H_2 = \{ \left[ \exists x \theta_i \right] \rightarrow \theta_i \left( k_i \right) | \left( \exists x \theta_i \right) \: \text{is an} \: \mathcal{L}_1 \: \text{sentence} \},\]

y déjalo\(\Sigma_2\) ser\(\Sigma_1 \cup H_2\). Como antes,\(\Sigma_2\) será consistente. Podemos continuar con este proceso para construir:

• \(\mathcal{L} = \mathcal{L}_0 \subseteq \mathcal{L}_1 \subseteq \mathcal{L}_2 \cdots\), una cadena cada vez mayor de idiomas.
• \(H_1, H_2, H_3, \ldots\), cada uno\(H_i\) una colección de axiomas Henkin en el idioma\(\mathcal{L}_i\).
• \(\Sigma = \Sigma_0 \subseteq \Sigma_1 \subseteq \Sigma_2 \subseteq \cdots\), donde cada uno\(\Sigma_i\) es un conjunto consistente\(\mathcal{L}_i\) de oraciones.

Dejar\(\mathcal{L}^\prime = \bigcup_{i < \infty} \mathcal{L}_i\) y dejar\(\hat{Sigma} = \bigcup_{i < \infty} \Sigma_i\). Cada uno\(\Sigma_i\) es un conjunto consistente\(\mathcal{L}^\prime\) de frases, como puede demostrarse mediante pruebas que son idénticas a las de Lemmas 3.2.3 y 3.2.4. Mostrarás en el Ejercicio 2 que\(\hat{Sigma}\) es un conjunto consistente\(\mathcal{L}^\prime\) de frases.

Extender a un Conjunto Máximo Consistente de Sentencias

Como recuerdas, íbamos a construir nuestro modelo de tal\(\mathfrak{A}\) manera que las oraciones que eran verdaderas en\(\mathfrak{A}\) fueran exactamente los elementos de un conjunto de oraciones\(\Sigma^\prime\). Es tiempo de construir\(\Sigma^\prime\). Dado que cada oración es verdadera o falsa en un modelo dado, será necesario que nos aseguremos de que para cada oración\(\sigma \in \mathcal{L}^\prime\), ya sea\(\sigma \in \Sigma^\prime\) o\(\neg \sigma \in \Sigma^\prime\). Como no podemos tener ambos\(\sigma\) y\(\neg \sigma\) verdad en ninguna estructura, también debemos asegurarnos de que no pongamos ambos\(\sigma\) y\(\neg \sigma\) en\(\Sigma^\prime\). Así,\(\Sigma^\prime\) será una extensión máxima consistente de\(\hat{Sigma}\).

Para construir esta extensión, arregle una enumeración de todas las\(\mathcal{L}^\prime\) frases -

\[\sigma_1, \sigma_2, \ldots, \sigma_n, \ldots .\]

Podemos hacer esto como\(\mathcal{L}^\prime\) es contable, siendo una unión contable de conjuntos contables. Ahora nos abrimos camino a través de esta lista, una frase a la vez, agregando cualquiera\(\sigma_n\) o la negación de\(\sigma_n\) a nuestra creciente lista de oraciones, dependiendo de cuál mantenga nuestra colección consistente.

Aquí están los detalles: Dejar\(\Sigma^0 = \hat{Sigma}\), y asumir que\(\Sigma^k\) se sabe que es un conjunto consistente\(\mathcal{L}^\prime\) de frases. Mostraremos cómo construir\(\Sigma^{k+1} \supseteq \Sigma^k\) y demostrar que también\(\Sigma^{k+1}\) es un conjunto consistente\(\mathcal{L}^\prime\) de frases. Entonces dejamos

\[\Sigma^\prime = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots \cup \Sigma^n \cup \cdots.\]

Demostrarás en el Ejercicio 4 que\(\Sigma^\prime\) es un conjunto consistente de oraciones. Será obvio a partir de la construcción de\(\Sigma^{k+1}\)\(\Sigma^k\) eso\(\Sigma^\prime\) es máximo, y así habremos completado nuestra tarea de producir una extensión máxima consistente de\(\hat{\Sigma}\).

Entonces todo lo que tenemos que hacer es describir cómo llegar\(\Sigma^{k+1}\)\(\Sigma^k\) y demostrar que\(\Sigma^{k+1}\) es consistente. Dado\(\Sigma^k\), considere el conjunto\(\Sigma^k \cup \{ \sigma^{k+1} \}\), donde\(\sigma_{k+1}\) está el elemento\(\left( k + 1 \right)\) st de nuestra lista fija de todas las\(\mathcal{L}^\prime\) frases. Let

\[\sigma^{k+1} = \begin{cases} \begin{array}{ll} \Sigma^k \cup \{ \sigma_{k+1} \} & \text{if} \: \Sigma^k \cup \{ \sigma_{k+1} \} \: \text{is consistent,} \\ \Sigma^k \cup \{ \neg \sigma_{k+1} \} & \text{otherwise.} \end{array} \end{cases}\]

Se le pide en el Ejercicio 3 que demuestre que\(\Sigma^{k+1}\) es consistente. Una vez que lo has hecho, hemos construido una consistencia máxima\(\Sigma^\prime\) que se extiende\(\Sigma\).

El siguiente lema establece que\(\Sigma^\prime\) se cierra deductivamente, al menos en lo que respecta a las sentencias. A medida que se trabaja a través de la prueba, el Teorema de Deducción será útil.

Lema 3.2.5.

Si\(\sigma\) es una oración, entonces\(\sigma \in \Sigma^\prime\) si y sólo si\(\Sigma^\prime \vdash \sigma\).

prueba

Ejercicio 5.

Construcción del Modelo - Preliminares

Hemos mencionado algunas veces que el modelo de lo\(\Sigma\) que vamos a construir tendrá como universo la colección de términos libres de variables del lenguaje\(\mathcal{L}^\prime\). Ahora es el momento de confesar que hemos mentido. Es fácil ver por qué el plan de usar los términos como elementos del universo está condenado al fracaso. Supongamos que hay dos términos diferentes\(t_1\) y\(t_2\) del idioma y en algún lugar de\(\Sigma^\prime\) está la oración\(t_1 = t_2\). Si los términos fueran los elementos del universo, entonces no podríamos modelar\(\Sigma^\prime\), como los dos términos\(t_1\) y no\(t_2\) son los mismos (son tipográficamente distintos), mientras que\(\Sigma^\prime\) exige que sean iguales. Nuestra solución a este problema es tomar la colección de términos libres de variables, definir una relación de equivalencia en ese conjunto y luego construir un modelo a partir de las clases de equivalencia de los términos libres de variables.

Así que deja\(T\) ser el conjunto de términos libres de variables del lenguaje\(\mathcal{L}^\prime\), y definir una relación\(\sim\) sobre\(T\) por

\[t_1 \sim t_2 \: \text{if and only if} \: \left( t_1 = t_2 \right) \in \Sigma^\prime.\]

No es difícil demostrar que\(\sim\) es una relación de equivalencia. Verificaremos que\(\sim\) sea simétrico, dejando reflexividad y transitividad a los Ejercicios.

Para demostrar que\(\sim\) es simétrico, asumamos eso\(t_1 \sim t_2\). Eso debemos probarlo\(t_2 \sim t_1\). Como sabemos\(t_1 \sim t_2\), por definición sabemos que la oración\(\left( t_1 = t_2 \right)\) es un elemento de\(\Sigma^\prime\). Tenemos que demostrarlo\(\left( t_2 = t_1 \right) \in \Sigma^\prime\). Supongamos que no. Entonces por la maximalidad de\(\Sigma^\prime\),\(\neg \left( t_2 = t_1 \right) \in \Sigma^\prime\). Pero como sabemos eso\(\Sigma^\prime \vdash t_1 = t_2\), por el Teorema 2.7.1,\(\Sigma^\prime \vdash t_2 = t_1\). (¿Puede proporcionar los detalles?) Pero como también sabemos eso\(\Sigma^\prime \vdash \neg \left( t_2 = t_1 \right)\), debe darse el caso de eso\(\Sigma^\prime \vdash \perp\), que es una contradicción, como sabemos que\(\Sigma^\prime\) es consistente. Entonces nuestra suposición es errónea y\(\left( t_2 = t_1 \right) \in \Sigma^\prime\), y así\(\sim\) es una relación simétrica.

Entonces, asumiendo que has trabajado a través del Ejercicio 7, hemos establecido que\(\sim\) es una relación de equivalencia. Ahora dejemos\(\left[ t \right]\) ser el conjunto de todos los términos libres\(s\) de variables del lenguaje\(\mathcal{L}^\prime\) tal que\(t \sim s\). Así\(\left[ t \right]\) es la clase de equivalencia de todos los términos que nos\(\Sigma^\prime\) dice son iguales a\(t\). El acervo de todas esas clases de equivalencia será el universo de nuestro modelo\(\mathfrak{A}\).

Construcción del Modelo - Las Ideas Principales

Para definir nuestro modelo de\(\Sigma^\prime\), debemos construir una\(\mathcal{L}^\prime\) -estructura. Así, tenemos que describir el universo de nuestra estructura así como interpretaciones de todos los símbolos constantes, de función y de relación del lenguaje\(\mathcal{L}^\prime\). Discutimos cada uno de ellos por separado:

El Universo\(A\): Como se explicó anteriormente, el universo de\(\mathfrak{A}\) será la colección de clases de\(\sim\) -equivalencia de los términos libres de variables de\(\mathcal{L}^\prime\). Por ejemplo, si\(\mathcal{L}^\prime\) incluye el símbolo de función binaria\(f\), el símbolo de constante no Henkin\(k\), y las constantes de Henkin\(c_1, c_2, \ldots, c_n, \ldots\), entonces el universo de nuestra estructura incluiría entre sus elementos\(\left[ c_{17} \right]\) y\(\left[ f \left( k, c_3 \right) \right]\).

Las constantes: Para cada símbolo constante\(c\) de\(\mathcal{L}^\prime\) (incluyendo las constantes de Henkin), necesitamos escoger un elemento\(c^\mathfrak{A}\) del universo para que sea el elemento representado por ese símbolo. Aquí no hacemos nada elegante:

\[c^\mathfrak{A} = \left[ c \right].\]

Entonces cada símbolo constante denotará su propia clase de equivalencia.

Las Funciones: Si\(f\) es un símbolo de función\(n\) -aria, debemos definir una función\(n\) -aria\(f^\mathfrak{A} : A^n \rightarrow A\). Escribamos la definición de\(f^\mathfrak{A}\) y luego podremos tratar de averiguar exactamente lo que dice la definición:

\[f^\mathfrak{A} \left( \left[ t_1 \right], \left[ t_2 \right], \ldots, \left[ t_n \right] \right) = \left[ f t_1 t_2 \ldots t_n \right].\]

En el lado izquierdo de la igualdad notarás que hay clases de\(n\) equivalencia que son las entradas a la función\(f^\mathfrak{A}\). Dado que los elementos de\(A\) son clases de equivalencia y\(f^\mathfrak{A}\) es una función\(n\) -aria, eso debería estar bien. En el lado derecho de la ecuación hay una sola clase de equivalencia, y la cosa dentro de los corchetes es un término libre de variables de\(\mathcal{L}^\prime\). Observe que la función\(f^\mathfrak{A}\) actúa colocando el símbolo\(f\) frente a los términos y luego tomando la clase de equivalencia del resultado.

Hay un detalle que hay que abordar. Debemos demostrar que la función\(f^\mathfrak{A}\) está bien definida. Digamos un poco sobre lo que eso significa, asumiendo que\(f\) es un símbolo de función unario, por simplicidad. Observe que nuestra definición de\(f^\mathfrak{A} \left( \left[ t \right] \right)\) depende del nombre de la clase de equivalencia en la que estemos poniendo\(f^\mathfrak{A}\). Esto podría dar lugar a problemas, ya que al menos es concebible que pudiéramos tener dos términos,\(t_1\) y\(t_2\), tal que\(\left[ t_1 \right]\) sea el mismo conjunto que\(\left[ t_2 \right]\), pero\(f^\mathfrak{A} \left( \left[ t_1 \right] \right)\) y\(f^\mathfrak{A} \left( \left[ t_2 \right] \right)\) evaluar como conjuntos diferentes. Entonces nuestra supuesta función ni siquiera\(f^\mathfrak{A}\) sería una función. Demostrar que esto no sucede es a lo que nos referimos cuando decimos que debemos demostrar que la función\(f^\mathfrak{A}\) está bien definida.

Veamos la prueba de que nuestra función\(f^\mathfrak{A}\) está, de hecho, bien definida. Supongamos que\(\left[ t_1 \right] = \left[ t_2 \right]\). Debemos demostrarlo\(f^\mathfrak{A} \left( \left[ t_1 \right] \right) = f^\mathfrak{A} \left( \left[ t_2 \right] \right)\). En otras palabras, debemos demostrar que si\(\left[ t_1 \right] = \left[ t_2 \right]\), entonces\(\left[ f t_1 \right] = \left[ f t_2 \right]\). De nuevo mirando la definición de nuestra relación de equivalencia\(\sim\), esto quiere decir que debemos demostrar que si\(t_1 = t_2\) es un elemento de\(\Sigma^\prime\), entonces así es\(f \left( t_1 \right) = f \left( t_2 \right)\). Entonces supongamos que\(t_1 = t_2\) es un elemento de\(\Sigma^\prime\). Aquí hay un esquema de una deducción\(\Sigma^\prime\) de\(f \left( t_1 \right) = f \left( t_2 \right)\). :

\[\begin{array}{ll} x = y \rightarrow f \left( x \right) = f \left( y \right) & \text{Axiom (E2)} \\ \vdots & \\ t_1 = t_2 \rightarrow f \left( t_1 \right) = f \left( t_2 \right) & \\ t_1 = t_2 & \text{element of} \: \Sigma^\prime \\ f \left( t_1 \right) = f \left( t_2 \right) & \text{PC} \end{array}\]

Ya que\(\Sigma^\prime \vdash f \left( t_1 \right) = f \left( t_2 \right)\), Lemma 3.2.5 nos dice que\(f \left( t_1 \right) = f \left( t_2 \right)\) es un elemento de\(\Sigma^\prime\), según sea necesario. Entonces la función\(f^\mathfrak{A}\) está bien definida.

Las relaciones: Supongamos que\(R\) es un símbolo de relación\(n\) -aria de\(\mathcal{L}^\prime\). Debemos definir una relación\(n\) -aria\(R^\mathfrak{A}\) sobre\(A\). Es decir, debemos decidir qué\(n\) -tuplas de clases de equivalencia se ubicarán en la relación\(R^\mathfrak{A}\). Aquí es donde utilizamos los elementos de\(\Sigma^\prime\). Definimos\(R^\mathfrak{A}\) por esta declaración:

\[R^\mathfrak{A} \left( \left[ t_1 \right], \left[ t_2 \right], \ldots, \left[ t_n \right] \right) \: \text{is true if and only if} \: R t_1 t_2 \ldots t_n \in \Sigma^\prime\].

Entonces los elementos del universo están en la relación\(R\) si y sólo si\(\Sigma^\prime\) dice que están en la relación\(R\). Por supuesto, debemos demostrar que la relación\(R^\mathfrak{A}\) está bien definida, también. O mejor dicho, hay que demostrar que la relación\(R^\mathfrak{A}\) está bien definida. Ver Ejercicio 8.

En este punto hemos construido una\(\mathcal{L}^\prime\) estructura perfectamente buena. Lo que tenemos que hacer a continuación es mostrar que\(\mathfrak{A}\) haga que todas las frases sean\(\Sigma^\prime\) verdaderas. Entonces habremos demostrado que hemos construido un modelo de\(\Sigma^\prime\).

proposición 3.2.6.

\(\mathfrak{A} \models \Sigma^\prime\)

Prueba

De hecho vamos a demostrar algo un poco más fuerte. Demostraremos, por cada oración\(\sigma\), que

\[\sigma \in \Sigma^\prime \: \text{if and only if} \: \mathfrak{A} \models \sigma.\]

Bueno, ya que te has dado cuenta, esto no es realmente más fuerte, ya que sabemos que\(\Sigma^\prime\) es máximo. Pero sí parece más fuerte, y esta versión de la proposición es lo que necesitamos para conseguir que los pasos inductivos funcionen bien.

Se procede por inducción sobre la complejidad de las fórmulas en\(\Sigma^\prime\). Para el caso base, supongamos que\(\sigma\) es una oración atómica. Entonces\(\sigma\) es de la forma\(R t_1 t_2 \ldots t_n\), donde\(R\) es un símbolo de relación\(n\) -aria y los\(t_i\)'s son términos libres variables. Pero entonces nuestra definición de\(R^\mathfrak{A}\) garantizó que\(\mathfrak{A} \models \sigma\) si y sólo si\(\sigma \in \Sigma^\prime\). Observe que si\(R\) es\(=\) y\(\sigma\) es\(t_1 = t_2\), entonces\(\sigma \in \Sigma^\prime\) iff\(t_1 \sim t_2\) iff\(\left[ t_1 \right] = \left[ t_2 \right]\) iff\(\mathfrak{A} \models \sigma\).

Para los casos inductivos, supongamos primero eso\(\sigma : \equiv \neg \alpha\), donde sabemos por hipótesis inductiva que\(\mathfrak{A} \models \alpha\) si y sólo si\(\alpha \in \Sigma^\prime\). Observe que como\(\Sigma^\prime\) es un conjunto máximo consistente de oraciones, sabemos que\(\sigma \in \Sigma^\prime\) si y solo si\(\alpha \notin \Sigma^\prime\). Así

\[\begin{align} \sigma \in \Sigma^\prime \: &\text{if and only if} \: \alpha \notin \Sigma^\prime \\ &\text{if and only if} \: \mathfrak{A} \not\models \alpha \\ &\text{if and only if} \: \mathfrak{A} \models \neg \alpha \\ &\text{if and only if} \: \mathfrak{A} \models \sigma \end{align}.\]

El segundo caso inductivo, cuando\(\sigma : \equiv \alpha \lor \beta\), es similar y se deja a los Ejercicios.

El caso interesante es cuando\(\sigma\) es una oración de la forma\(\forall x \phi\). Debemos demostrar que\(\forall x \phi \in \Sigma^\prime\) si y sólo si\(\mathfrak{A} \models \forall x \phi\). Hacemos cada implicación por separado.

Primero, asuma eso\(\forall x \phi \in \Sigma^\prime\). Debemos demostrar eso\(\mathfrak{A} \models \forall x \phi\), lo que significa que debemos mostrar, dada una función de asignación\(s\), eso\(\mathfrak{A} \models \forall x \phi \left[ s \right]\). Dado que los elementos de\(A\) son clases de equivalencia de términos libres de variables, esto significa que tenemos que mostrar para cualquier término libre de variables\(t\) que

\[\mathfrak{A} \models \phi \left[ s \left[ x | \left[ t \right] \right] \right].\]

Pero (aquí hay otro lema para que lo prueben) para cualquier término libre de variables\(t\) y cualquier función de asignación\(s\)\(\bar{s} \left( t \right) = \left[ t \right]\), y así por el Teorema 2.6.2, tenemos que demostrar que

\[\mathfrak{A} \models \phi_t^x \left[ s \right].\]

Observe que\(\phi_t^x\) es una oración, así que\(\mathfrak{A} \models \phi_t^x \left[ s\right]\) si y solo si\(\mathfrak{A} \models \phi_t^x\). Pero también\(\Sigma^\prime \vdash \phi_t^x\) fíjense que, como\(\forall x \phi\) es un elemento de\(\Sigma^\prime\),\(\forall x \phi \rightarrow \phi_t^x\) es un axioma cuantificador de tipo (Q1) (\(t\)es sustituible\(x\) en\(\phi\) como\(t\) está libre de variables), y\(\Sigma^\prime\) se cierra deductivamente para oraciones por Lemma 3.2.5. Pero\(\phi_t^x\) es menos complejo que\(\forall x \phi\), y por lo tanto por nuestra hipótesis inductiva,\(\mathfrak{A} \models \phi_t^x\), según sea necesario.

Para la dirección inversa de nuestro bicondicional, supongamos que\(\forall x \phi \notin \Sigma^\prime\). Tenemos que demostrarlo\(\mathfrak{A} \not\models \forall x \phi\). Como\(\Sigma^\prime\) es máximo,\(\neg \forall x \phi \in \Sigma^\prime\). Vuelva a ser cierre deductivo, esto quiere decir que\(\exists x \neg \phi \in \Sigma^\prime\). A partir de nuestra construcción de\(\Sigma^\prime\), sabemos que hay alguna constante Henkin\(c_i\) tal que\(\left( \left[ \exists x \neg \phi \right] \rightarrow \neg \left( c_i \right) \right) \in \Sigma^\prime\), y utilizando una vez más el cierre deductivo, esto nos dice eso\(\neg \phi \left( c_i \right) \in \Sigma^\prime\). Habiendo despojado a un cuantificador, podemos afirmar a través de la hipótesis inductiva que\(\mathfrak{A} \models \neg \phi \left( c_i \right)\), así\(\mathfrak{A} \not\models \forall x \phi\), según sea necesario.

Esto termina nuestra prueba de Lemma 3.2.6, por lo que sabemos que la\(\mathcal{L}^\prime\) -estructura\(\mathfrak{A}\) es un modelo de\(\Sigma^\prime\).

Construcción del Modelo - Limpieza

Como recordarán, de vuelta en nuestro esbozo de la prueba del Teorema de la Completitud, íbamos a probar el teorema construyendo un modelo de\(\Sigma\). Ya casi estamos ahí. Tenemos una estructura,\(\mathfrak{A}\), sabemos que\(\mathfrak{A}\) es un modelo de\(\Sigma^\prime\), y lo sabemos\(\Sigma \subseteq \Sigma^\prime\), así que cada oración en\(\Sigma\) es verdadera en la estructura\(\mathfrak{A}\). Ya casi terminamos. El único problema es que\(\Sigma\) comenzó la vida como un conjunto de\(\mathcal{L}\) frases, mientras que\(\mathfrak{A}\) es una\(\mathcal{L}^\prime\) -estructura, no una\(\mathcal{L}\) -estructura.

Afortunadamente, esto se soluciona fácilmente con un poco de amnesia: Definir la estructura\(\mathfrak{A} \upharpoonright_\mathcal{L}\) (leer \(\mathfrak{A}\)restringida a\(\mathcal{L}\), o la restricción de\(\mathfrak{A}\) a\(\mathcal{L}\)) de la siguiente manera: El universo de\(\mathfrak{A} \upharpoonright_\mathcal{L}\) es el mismo que el universo de\(\mathfrak{A}\). Cualquier símbolo constante, símbolos de función y símbolos de relaciones de\(\mathcal{L}\) se interpretan\(\mathfrak{A} \upharpoonright_\mathcal{L}\) exactamente como se interpretaron en\(\mathfrak{A}\), y simplemente ignoramos todos los símbolos que se agregaron a medida que pasamos de\(\mathcal{L}\) a\(\mathcal{L}^\prime\). Ahora bien,\(\mathfrak{A} \upharpoonright_\mathcal{L}\) es una\(\mathcal{L}\) estructura perfectamente buena, y todo lo que queda para terminar la prueba del Teorema de la Integtud es trabajar a través de un último lema:

lema 3.2.7.

Si\(\sigma\) es una\(\mathcal{L}\) -oración, entonces\(\mathfrak{A} \models \sigma\) si y sólo si\(\mathfrak{A} \upharpoonright_\mathcal{L} \models \sigma\).

prueba

(Esquema) Utilizar inducción sobre la complejidad de\(\sigma\), demostrando que\(\mathfrak{A} \upharpoonright_\mathcal{L} \models \sigma\) si y sólo si\(\sigma \in \Sigma^\prime\), como en la prueba de Lemma 3.2.6.

Así, hemos logrado producir una\(\mathcal{L}\) -estructura que es un modelo de\(\Sigma\), por lo que sabemos que cada conjunto consistente de oraciones tiene un modelo. Por nuestras observaciones preliminares, sabemos así que si\(\Sigma \models \phi\), entonces\(\Sigma \vdash \phi\), y nuestra prueba del Teorema de la Completitud es completa.

Pruebas de los Lemmas

Presentamos aquí las pruebas de dos lemmas que se utilizaron en la prueba del Teorema de la Integtud. El primer lema se introdujo cuando ampliamos el lenguaje\(\mathcal{L}\) al idioma\(\mathcal{L}^\prime\) y nos preocupaba la consistencia de\(\Sigma\) en el nuevo lenguaje expandido.

Lema 3.2.3.

Si\(\Sigma\) es un conjunto consistente de\(\mathcal{L}\) -oraciones y\(\mathcal{L}^\prime\) es una extensión por constantes de\(\mathcal{L}\), entonces\(\Sigma\) es consistente cuando se ve como un conjunto de\(\mathcal{L}^\prime\) -oraciones.

prueba

Supongamos, a modo de contradicción, que eso no\(\Sigma\) es consistente como un conjunto de\(\mathcal{L}^\prime\) -oraciones. Por lo tanto, existe una deducción (in\(\mathcal{L}^\prime\))\(\perp\) de\(\Sigma\). \(n\)Sea el menor número de nuevas constantes utilizadas en cualquier deducción de este tipo, y deje\(D^\prime\) ser una deducción usando exactamente\(n\) tales constantes. Observe que\(n > 0\), como de otra manera\(D^\prime\) sería una deducción de\(\perp\) en\(\mathcal{L}\). Demostramos que existe una deducción de\(\perp\) usar menos que\(n\) constantes, contradicción que establece el lema.

Dejar\(v\) ser una variable que no ocurre en\(D^\prime\), dejar\(c\) ser una de las nuevas constantes que se produce en\(D^\prime\), y dejar\(D\) ser la secuencia de fórmulas\(\left( \phi_i \right)\) que se forma tomando cada fórmula\(\phi_i^\prime\)\(D^\prime\) y reemplazando todas las ocurrencias de\(c\) in \(\phi_i^\prime\)por\(v\). La última fórmula en\(D\) es\(\perp\), así que si podemos demostrar que\(D\) es una deducción, estaremos terminados.

Por lo que utilizamos la inducción sobre los elementos de la deducción\(D^\prime\). Si\(\phi_i^\prime\) es un elemento de en\(D^\prime\) virtud de ser un axioma de igualdad o un elemento de\(\Sigma\), entonces\(\phi_i = \phi_i^\prime\), y\(\phi_i\) es un elemento de una deducción por la misma razón. Si\(\phi_i^\prime\) es un axioma cuantificador, por ejemplo\(\left( \forall x \right) \theta^\prime \rightarrow \theta_t^{\prime x}\), entonces también\(\phi_i\) será un axioma cuantificador, en este caso\(\left( \forall x \right) \theta \rightarrow \theta_t^x\). No habrá problemas con la sustituibilidad de\(t\) for\(x\), dado que eso\(t^\prime\) es sustituible\(x\). Si\(\phi^\prime\) es un elemento de la deducción en virtud de ser la conclusión de una regla de inferencia\(\left( \Gamma^\prime, \phi^\prime \right)\), entonces\(\left( \Gamma, \phi \right)\) será una regla de inferencia que justificará\(\phi\).

Esto completa el argumento que\(D\) es una deducción de\(\perp\). Ya que\(D\) claramente usa menos símbolos nuevos constantes que\(D^\prime\), tenemos nuestra contradicción y nuestra prueba es completa.

El segundo lema era necesario cuando agregamos los axiomas Henkin a nuestro consistente conjunto de oraciones\(\Sigma\). Teníamos que demostrar que el conjunto resultante,\(\hat{\Sigma}\), seguía siendo consistente.

lema 3.2.4:

Si\(\Sigma\) es un conjunto consistente de oraciones y\(\hat{\Sigma}\) se crea agregando axiomas Henkin a\(\Sigma\), entonces\(\hat{\Sigma}\) es consistente.

prueba

Supongamos que eso no\(\hat{\Sigma}\) es consistente. Dejar\(n\) ser el menor número de axiomas Henkin utilizados en cualquier posible deducción\(\hat{\Sigma}\) de\(\perp\). Arreglar tal conjunto de axiomas\(n\) Henkin, y dejar\(\alpha\) ser uno de esos axiomas Henkin. Entonces sabemos que

\[\Sigma \cup H \cup \alpha \vdash \perp,\]

donde\(H\) esta la colecta de los otros axiomas\(n - 1\) Henkin necesarios en la prueba. Ahora\(\alpha\) es de la forma\(\exists x \phi \rightarrow \phi \left( c \right)\), donde\(c\) está una constante Henkin y\(\phi \left( c \right)\) es nuestra taquigrafía para\(\phi_c^x\).

Por el Teorema de la Deducción (Teorema 2.7.4), como\(\alpha\) es una oración, esto quiere decir que\(\Sigma \cup H \vdash \neg \alpha\),

\[\Sigma \cup H \vdash \exists x \phi \: \: \: \: \: \text{and} \: \: \: \: \: \Sigma \cup H \vdash \neg \phi_c^x.\]

Ya que\(\exists x \phi\) es lo mismo que\(\neg \forall x \neg \phi\), desde el primero de estos hechos sabemos que

\[\Sigma \cup H \vdash \neg \forall x \neg \phi.\]

Eso también lo sabemos\(\Sigma \cup H \vdash \neg \phi_c^x\). Si tomamos una deducción\(\neg \phi_c^x\) y sustituimos cada ocurrencia de la constante\(c\) por una nueva variable\(z\), el resultado sigue siendo una deducción (como en el comprobante de Lemma 3.2.3 anterior), entonces\(\Sigma \cup H \vdash \neg \phi_z^x\). Por Lemma 2.7.2, sabemos que

\[\Sigma \cup H \vdash \forall z \neg \phi_z^x.\]

Nuestro axioma cuantificador (Q1) establece que siempre y cuando\(x\) sea sustituible por\(z\) in\(\neg \phi_z^x\), (que es, como\(z\) es una nueva variable), entonces podemos afirmar que\(\left[ \forall z \neg \phi_z^x \right] \rightarrow \neg \left( \phi_z^x \right)_x^z\). Por lo tanto

\[\Sigma \cup H \vdash \neg \left( \phi_z^x \right)_x^z.\]

Pero\(\left( \phi_z^x \right)_x^z = \phi\), entonces\(\Sigma \cup H \vdash \neg \phi\). Pero ahora podemos volver a usar Lemma 2.7.2 para concluir que

\[\Sigma \cup H \vdash \forall x \neg \phi.\]

Entonces, por Ecuaciones (3.2.24) y (3.2.27), vemos eso\(\Sigma \cup H \vdash \perp\). Esto es una contradicción, ya que\(\Sigma \cup H\) contiene sólo axiomas\(n - 1\) Henkin. Así nos llevan a concluir que\(\hat{\Sigma}\) es consistente.

Ejercicios

1. Supongamos que eso\(\Sigma\) es inconsistente y\(\phi\) es una\(\mathcal{L}\) fórmula -. \(\Sigma \vdash \phi\)Demuéstralo.
2. Supongamos que\(\Sigma_0 \subseteq \Sigma_1 \subseteq \Sigma_2 \cdots\) son tales que cada una\(\Sigma_i\) es un conjunto consistente de oraciones en un idioma\(\mathcal{L}\). \(\bigcup \sigma_i\)El espectáculo es consistente.
3. Demostrar que si\(\Pi\) es un conjunto consistente de oraciones y\(\sigma\) es una oración tal que\(\Pi \cup \{ \sigma \}\) es inconsistente, entonces\(\Pi \cup \{ \neg \sigma \}\) es consistente. Concluir que en la prueba del Teorema de la Integtud, si\(\Sigma^k\) es consistente, entonces\(\Sigma^{k+1}\) es consistente.
4. Demostrar que lo\(\Sigma^\prime\) construido en la prueba del Teorema de Integtud es consistente. [Sugerencia: Las deducciones son de longitud finita.]
5. Demostrar Lema 3.2.5.
6. Hacia una prueba del teorema de la integridad en un contexto más general:
   a) No asuma que el lenguaje\(\mathcal{L}\) es contable. Supongamos que se le ha dado un conjunto de oraciones\(\Sigma_\text{max}\) que es máxima y consistente. Entonces para cada oración\(\sigma\), ya sea\(\sigma \in \Sigma_\text{max}\) o\(\neg \sigma \in \Sigma_\text{max}\). Imita la prueba de la Proposición 3.2.6 para convencerse de que podemos construir un modelo\(\mathfrak{A}\) de\(\Sigma\).
   (b) El lema de Zorn implica lo siguiente: Si se nos da un conjunto consistente\(\mathcal{L}^\prime\) de frases\(\hat{\Sigma}\), entonces la colección de extensiones consistentes de\(\hat{\Sigma}\) tiene un elemento máximo (con respecto a\(\subseteq\))\(\Sigma_\text{max}\). Si estás familiarizado con el Lema de Zorn, prueba este hecho.
   c) Utilizar las partes (a) y (b) de este problema para delinear una prueba del Teorema de Integtud en el caso de que el lenguaje no\(\mathcal{L}\) sea contable.
7. Completar la prueba del reclamo de que la relación\(\sim\) es una relación de equivalencia.
8. Mostrar que la relación\(R^\mathfrak{A}\) de la estructura\(\mathfrak{A}\) está bien definida. Así que vamos a\(R\) ser un símbolo de relación (un símbolo de relación unario está bien), y mostrar que si\(\left[ t_1 \right] = \left[ t_2 \right]\), entonces\(R^\mathfrak{A} \left( \left[ t_1 \right] \right)\) es verdadero si y solo si\(R^\mathfrak{A} \left( \left[ t_2 \right] \right)\) es verdadero.
9. Terminar la cláusula inductiva de la prueba de la Proposición 3.2.6.
10. Rellena los datos del comprobante de Lemma 3.2.7.