3.3: Compacidad

El Teorema de la Completitud termina nuestro vínculo entre deducibilidad e implicación lógica. El Teorema de la Compacidad es nuestro primer uso de ese vínculo. En cierto sentido, lo que hace el Teorema de la Compacidad es centrar nuestra atención en la finitud de las deducciones, y entonces podemos comenzar a usar esa finitud en nuestro beneficio.

Teorema 3.3.1: Teorema de la compacidad

Dejar\(\Sigma\) ser cualquier conjunto de axiomas. Hay un modelo de\(\Sigma\) si y solo si cada subconjunto finito\(\Sigma_0\) de\(\Sigma\) tiene un modelo.

Decimos que\(\Sigma\) es satisfactorio si hay un modelo de\(\Sigma\), y decimos que\(\Sigma\) es finitamente satisfactorio si cada subconjunto finito de\(\Sigma\) tiene un modelo. Entonces el Teorema de la Compacidad dice que\(\Sigma\) es satisfecha si y sólo si\(\Sigma\) es finitamente satisfactorio.

prueba

Para la dirección fácil, supongamos que\(\Sigma\) tiene un modelo\(\mathfrak{A}\). Entonces también\(\mathfrak{A}\) es un modelo de cada finito\(\Sigma_0 \subseteq \Sigma\).

Para la dirección más difícil, supongamos que no hay modelo de\(\Sigma\). Entonces\(\Sigma \models \perp\). Por el Teorema de la Completitud\(\Sigma \vdash \perp\),, por lo que hay una deducción\(D\) de\(\perp\) de\(\Sigma\). Ya que\(D\) es una deducción, es finita en longitud y por lo tanto sólo puede contener finitamente muchos de los axiomas de\(\Sigma\). Dejar\(\Sigma_0\) ser el conjunto finito de axiomas a partir de los\(\Sigma\) que se utilizan en\(D\). Entonces\(D\) es una deducción de\(\Sigma_0\), entonces\(\Sigma_0 \vdash \perp\). Pero entonces por el Teorema de la Solidez\(\Sigma_0 \models \perp\),, entonces\(\Sigma_0\) no puede tener un modelo.

Corolario 3.3.2.

Dejar\(\Sigma\) ser un conjunto de\(\mathcal{L}\) -fórmulas y dejar\(\theta\) ser una\(\mathcal{L}\) -fórmula. \(\Sigma \models \theta\)si y sólo si hay un finito\(\Sigma_0 \subseteq \Sigma\) tal que\(\Sigma_0 \models \theta\).

prueba

\[\begin{array}{rll} \Sigma \models \theta & \text{iff} \: \Sigma \vdash \theta & \text{Soundness and Completeness} \\ & \text{iff} \: \Sigma_0 \vdash \theta \: \text{for a finite} \: \Sigma_0 \subseteq \Sigma & \text{deductions are finite} \\ & \text{iff} \: \Sigma_0 \models \theta & \text{Soundness and Completeness} \end{array}\]

Ahora estamos en una posición en la que podemos usar el Teorema de Compactación para comprender mejor las limitaciones de la lógica de primer orden, o, para darle un giro más positivo, ¡una mejor comprensión de la riqueza de las matemáticas!

Ejemplo 3.3.3:

Supongamos que examinamos la\(\mathcal{L}_{NT}\) -estructura\(\mathfrak{N}\), cuyo universo es el conjunto de números naturales\(\mathbb{N}\), dotado de las familiares funciones aritméticas de suma, multiplicación, y exponenciación y la relación binaria habitual menor que. Sería bueno tener una colección de axiomas que caracterizaran la estructura\(\mathfrak{N}\). Con esto nos referimos a un conjunto de oraciones\(\Sigma\) tal que\(\mathfrak{N} \models \Sigma\), y si\(\mathfrak{A}\) es alguna\(\mathcal{L}_{NT}\) -estructura tal que\(\mathfrak{A} \models \Sigma\), entonces\(\mathfrak{A}\) es “igual que”\(\mathfrak{N}\). (\(\mathfrak{A}\)es “igual que”\(\mathfrak{N}\) si hay\(\mathfrak{A}\) y\(\mathfrak{N}\) son isomórficos - ver Ejercicio 5 en la Sección 1.6).

Desafortunadamente, no podemos esperar tener tal conjunto de oraciones, y el Teorema de la compacidad nos muestra por qué. Supongamos que tomamos cualquier conjunto de oraciones\(\Sigma\) que pareciera que debía caracterizar\(\mathfrak{N}\). Añadamos algunas oraciones\(\Sigma\) y creemos una nueva colección de oraciones\(\Theta\) en un lenguaje extendido\(\mathcal{L} = \mathcal{L}_{NT} \cup \{ c \}\), donde\(c\) hay un nuevo símbolo constante:

\[\Theta = \Sigma \cup \{ 0 < c, S0 < c, SS0 < c, \ldots, SSS \cdots S0 \left( nS \text{'s} \right) < c, \ldots \}.\]

Ahora fíjate que\(\Theta\) es finitamente satisfecha. Si\(\Theta_0\) es un subconjunto finito de\(\Theta\), entonces\(\Theta_0\) es un subconjunto de

\[\Theta_n = \Sigma \cup \{ 0 < c, S0 < c, SS0 < c, \ldots, SSS \cdots S0 \left( nS \text{'s} \right) < c \}\]

Para algún número natural\(n\). Pero\(\Theta_n\) tiene un modelo\(\mathfrak{N}_n\), cuyo universo es\(\mathbb{N}\), las funciones y relaciones se interpretan de la manera habitual, y\(c^{\mathfrak{N}_n} = n + 1\). Así que cada subconjunto finito de\(\Theta\) tiene un modelo, y por lo tanto\(\Theta\) tiene un modelo\(\mathfrak{A}^\prime\). Ahora olvídate de la interpretación del símbolo constante\(c\) y te quedas con una\(\mathcal{L}_{NT}\) -estructura\(\mathfrak{A} = \mathfrak{A}^\prime \upharpoonright_{\mathcal{L}_{NT}}\). Este modelo\(\mathfrak{A}\) es interesante, pero no podemos afirmar que\(\mathfrak{A}\) sea “igual que”\(\mathfrak{N}\), ya que\(\mathfrak{A}\) tiene un elemento (el ting que solía llamarse\(c^{\mathfrak{A}^\prime}\)) tal que hay infinitamente muchos elementos\(x\) que se paran en la relación\(<\) con ese elemento, mientras que no existe tal elemento de\(\mathfrak{N}\). El elemento\(c^{\mathfrak{A}^\prime}\) se denomina un modelo no estándar de aritmética, un modelo de aritmética que no es isomórfico a\(\mathfrak{N}\). Primero encontramos modelos aritméticos no estándar en el Ejercicio 7 de la Sección 2.8.

Por lo que ningún conjunto de oraciones de primer orden puede caracterizar completamente los números naturales.

Chaf: ¡No es esto pulcro! Observe cómo cada uno de los\(\mathfrak{N}_n\)'s en el último ejemplo eran modelos perfectamente ordinarios que se parecían a los números naturales, ¡pero lo que obtuvimos al final se veía completamente diferente!

Definición 3.3.4

Si\(\mathfrak{A}\) es una\(\mathcal{L}\) -estructura, definimos la teoría del\(\mathfrak{A}\) ser\(Th \left( \mathfrak{A} \right) = \{ \phi | \phi \: \text{is an} \: \mathcal{L} \text{-formula and} \: \mathfrak{A} \models \phi \}\). Si\(\mathfrak{A}\) y\(\mathfrak{B}\) son\(\mathcal{L}\) -estructuras tales que\(Th \left( \mathfrak{A} \right) = Th \left( \mathfrak{B} \right)\), entonces decimos eso\(\mathfrak{A}\) y\(\mathfrak{B}\) son elementalmente equivalentes, y escribimos\(\mathfrak{A} \equiv \mathfrak{B}\).

Si\(\mathfrak{A} \equiv \mathfrak{N}\), decimos que\(\mathfrak{A}\) es un modelo de aritmética.

Observe que la extraña estructura\(\mathfrak{A}\) que construimos arriba puede ser un modelo de aritmética si simplemente dejamos que sea la\(\Sigma\) de nuestra construcción\(Th \left( \mathfrak{N} \right)\). El Ejercicio 2 te pide que acredites que en este caso tenemos\(\mathfrak{A} \equiv \mathfrak{N}\). Dado que desde\(\mathfrak{A}\) luego no se parece en nada al modelo habitual de aritmética sobre los números naturales, llamar a\(\mathfrak{A}\) un modelo no estándar de aritmética tiene bastante sentido. Lo difícil de ver es que aunque el universo\(A\) ciertamente contiene elementos no estándar, no se interponen en el camino de la equivalencia elemental. La razón de esto es que el lenguaje no\(\mathcal{L}_{NT}\) puede referirse explícitamente a ningún elemento no estándar, así que no podemos expresar una declaración que sea (por ejemplo) true in\(\mathfrak{N}\) pero false in\(\mathfrak{A}\). Entonces la lección que hay que aprender es que es mucho más fácil que dos estructuras sean elementales equivalentes de lo que es para ellas ser isomórficas. Nuestra estructura no\(\mathfrak{A}\) es isomórfica a\(\mathfrak{N}\), sino\(\mathfrak{A}\) que es elementalmente equivalente a\(\mathfrak{N}\).

Ejemplo 3.3.5:

¿Recuerdas esos\(\varepsilon\)\(\delta\) es y es del cálculo? Se introdujeron en el siglo XIX en un intento de afianzar las bases del tema. Cuando estaban desarrollando el cálculo, Newton y Leibniz no se preocuparon por los límites. Felizmente utilizaron cantidades que eran infinitamente pequeñas pero no del todo cero e ignoraron las dificultades lógicas que esto presentaba. Estas cantidades infinitamente pequeñas viven en los libros de texto de cálculo actuales como los diferenciales\(dx\) y\(dy\).

A la mayoría de la gente le resulta mucho más fácil pensar en diferenciales que luchar a través de cálculos límite, y en 1961 Abraham Robinson desarrolló un marco lógico para el cálculo que permitió el uso de estos infinitesimales de una manera coherente, no contradictoria. La versión del cálculo de Robinson llegó a conocerse como análisis no estándar. Aquí hay una introducción aproximada (para un tratamiento completo, ver [Keisler 76]).

Tomando como punto de partida los números reales que tan bien conoces, construimos un idioma\(\mathcal{L}_\mathbb{R}\), el lenguaje de los números reales. Para cada número real\(r\), el idioma\(\mathcal{L}_\mathbb{R}\) incluye un símbolo constante\(\dot{r}\). Entonces el lenguaje\(\mathcal{L}_\mathbb{R}\) incluye símbolos constantes\(\dot{0}\),\(\dot{\pi}\), y\(\frac{\dot{2}}{7}\). Para cada función\(f : \mathbb{R}^n \rightarrow \mathbb{R}\), lanzamos un símbolo de función\(\dot{f}\), y para cada relación\(n\) -aria\(R\) en los reales agregamos un símbolo de relación\(n\) -aria\(\dot{R}\). Entonces nuestro lenguaje incluye, por ejemplo, los símbolos de función\(\dot{+}\) y\(\dot{\cos}\) y el símbolo de relación\(\dot{<}\).

Ahora definimos\(\mathfrak{R}\) que es la\(\mathcal{L}_\mathbb{R}\) -estructura\(\left( \mathbb{R}, \{ r \}, \{ f \}, \{ R \} \right)\), donde cada símbolo se interpreta como el significado del número, función, o relación que dio origen al símbolo. Entonces, el símbolo de función\(\dot{+}\) representa la suma de función, y el símbolo constante\(\dot{\pi}\) se refiere al número real que es igual a la relación de la circunferencia de un círculo a su diámetro.

Dada esta estructura\(\mathfrak{R}\) (fíjate que no\(\mathfrak{R}\) es nada elegante -son solo los números reales con los que has estado trabajando desde la secundaria), genera el conjunto de fórmulas\(Th \left( \mathfrak{R} \right)\), la colección de\(\mathcal{L}_\mathbb{R}\) fórmulas de primer orden que son verdaderas declaraciones sobre los números reales. Ahora es el momento de usar la compacidad.

Let\(\mathcal{L}^\prime = \mathcal{L}_\mathbb{R} \cup \{ c \}\), donde\(c\) es un nuevo símbolo constante, y mira la colección de\(\mathcal{L}^\prime\) -frases

\[\Theta = Th \left( \mathfrak{R} \right) \cup \{ \dot{0} \dot{<} c \} \cup \{ c \dot{<} \dot{r} | r \in \mathbb{R}, r > 0 \}.\]

(¿Tiene claro la diferencia entre los símbolos punteados y los no punteados en esta definición?)

Por el Teorema de la Compacidad,\(\Theta\) tiene un modelo\(\mathfrak{A}\),, y en el modelo\(\mathfrak{A}\), el elemento denotado por\(c\) juega el papel de un elemento infinitesimal: Es positivo, sin embargo es menor que cada número real positivo. Hablando a grandes rasgos, en el universo\(A\) de la estructura\(\mathfrak{A}\) hay tres tipos de elementos. Hay elementos estándar puros, que constituyen una copia de lo\(\mathbb{R}\) que vive en su interior\(A\). Después hay elementos puros no estándar, por ejemplo, el elemento denotado por\(c\). Finalmente, hay elementos como el objeto denotado por\(\dot{17} \dot{+} c\), que tiene una parte estándar y una parte no estándar. (Para más detalles, consulte el Ejercicio 11 en la Sección 3.4.)

Los elementos no estándar de la estructura\(\mathfrak{R}\) proporcionan un método para desarrollar derivados sin usar límites. Por ejemplo, podemos definir la derivada de una función\(f\) en un elemento estándar\(a\) para que sea

\[f^\prime \left( a \right) = \: \text{the standard part of} \: \frac{f \left( a + c \right) - f \left( a \right)}{c}.\]

Como puede ver, no hay límite en la definición. Hemos intercambiado los límites del cálculo por los elementos no estándar de\(\mathfrak{A}\), y la pendiente de una línea tangente no es más que una pendiente de una línea que conecta dos puntos, uno de los cuales no es estándar. El análisis no estándar ha sido un área de estudio activo durante los últimos cuarenta años, y aunque no es exactamente convencional, se ha utilizado para descubrir algunos resultados nuevos en diversas áreas del análisis clásico.

Ejemplo 3.3.6:

Se supone que la idea de colorear un mapa es intuitiva. Cuando estabas en clase de geografía cuando eras niño, sin duda te dieron un mapa de una región y te pidieron colorear en los diversos países, estados, o provincias. Y te faltaba el punto si usabas el mismo color para sombrear dos países que compartían una frontera común, aunque se permitía usar el mismo color para dos países cuyas fronteras se reunían en un solo punto. (Los estados de Utah, Colorado, Arizona y Nuevo México hacen esto en Estados Unidos, por lo que se permitiría colorear tanto Colorado como Arizona con el color rojo). La cuestión de cuántos colores se necesitan para colorear cualquier mapa dibujado en el plano fue planteada por primera vez en 1852 por Francis Guthrie, y la respuesta, que cuatro colores bastan para cualquier mapa de este tipo (siempre y cuando cada división política consista en una sola región - Michigan en un mapa de los Estados Unidos o Pakistán anterior a 1971 en un mapa de Asia no estaría permitido), fue probado en 1976 por Kenneth Appel y Wolfgang Hakin. Aquí no vamos a probar el Teorema de Cuatro Colores; más bien, ampliamos este resultado considerando mapas con infinitamente muchas regiones.

\(R\)Sea un conjunto (estoy pensando en los elementos de\(R\) como siendo las regiones de un mapa con infinitamente muchos países) con una relación binaria simétrica\(A\) (adyacencia). Dejar\(k\) ser un número natural. Afirmamos que es posible asignar a cada región de\(R\) uno de los\(k\) posibles colores de tal manera que las regiones adyacentes reciban diferentes colores si y sólo si es posible colorear así cada subconjunto finito de\(R\).

Esto lo demostraremos usando el Teorema de Compactación. Uno de los trucos para usar la compacidad es elegir sabiamente tu idioma. Para este ejemplo, deje que el lenguaje\(\mathcal{L}\) consista en una colección de constantes\(\{ r \}_{r \in R}\), una para cada región, y una colección de predicados unarios\(\{ C_i \}_{1 \leq i \leq k}\), uno para cada color. Por lo que la declaración\(C_i \left( r \right)\) atómica se interpretará en el sentido de que esa región\(r\) se colorea con color\(i\). También necesitaremos un símbolo de relación binaria\(A\), para adyacencia.

Que\(\Sigma\) sea la colección de oraciones:

\[\Sigma = \begin{cases} \begin{array}{ll} C_1 \left( r \right) \lor C_2 \left( r \right) \lor \cdots \lor C_k \left( r \right) & \text{for each} \: r \in R \\ \neg \left[ C_i \left( r \right) \land C_j \left( r \right) \right] & r \in R, i \neq j \\ A \left( r, r^\prime \right) \rightarrow \left( \neg C_i \left( r \right) \land C_i \left( r^\prime \right) \right) & r, r^\prime \in R, 1 \leq i \leq k \\ A \left( r, r^\prime \right) & r, r^\prime \in R, r \: \text{adjacent to} \: r^\prime \\ \neg A \left( r, r^\prime \right) & r, r^\prime \in R, r \: \text{not adjacent to} \: r^\prime \end{array} \end{cases}\]

Chaf: Detente ya un minuto y asegúrate de entender cada una de las frases en\(\Sigma\). Deberían poder decir, en inglés ordinario, lo que cada frase afirma. Por ejemplo,\(C_1 \left( r \right) \lor C_2 \left( r \right) \lor \cdots \lor C_k \left( r \right)\) dice que a la región se le\(r\) debe dar uno de los\(k\) colores. Es decir, tenemos que colorear cada región en el mapa. Tómese el tiempo ahora para traducir cada uno de los otros tipos de declaraciones\(\Sigma\) al inglés.

Pero ahora nuestra afirmación de que un mapa infinito es\(k\) -colorable si y solo si cada subconjunto finito del mapa es\(k\) -colorable es clara, ya que una coloración de (un subconjunto finito de)\(R\) corresponde a un modelo de (un subconjunto finito de)\(\Sigma\), y el Teorema de Compacidad dice que\(\Sigma\) tiene un modelar si y solo si cada subconjunto finito de\(\Sigma\) tiene un modelo.

Observe que no se utilizan cuantificadores en este ejemplo, por lo que realmente solo necesitábamos compacidad para la lógica del predicado, no la lógica de primer orden. Si se siente cómodo con los términos, observe también que la prueba funciona ya sea que haya una colección de países contablemente infinita o incontablemente infinita.

Si realmente has estado prestando atención, te diste cuenta de que no usamos el hecho de que los mapas están dibujados en el avión. Entonces, si dibujamos un mapa en una rosquilla con innumerables países, solo se necesitan siete colores para colorear el mapa, como lo demostró en 1890 Percy John Heawood que siete colores bastan para mapas finitos dibujados en una rosquilla.

Ejemplo 3.3.7:

Bien puede estar familiarizado con los árboles matemáticos, ya que a menudo se discuten en cursos de matemáticas discretas o cursos introductorios de informática. Para nuestros propósitos un árbol es un conjunto\(T\) particionado en subconjuntos\(T_i\)\(\left( i = 0, 1, 2, \ldots \right)\),, llamados los niveles del árbol, junto con una función\(a\) tal que:

1. \(T_0\)consiste en un solo elemento (llamado la raíz del árbol).
2. \(a : \left( T - T_0 \right) \rightarrow T\)tal que si\(t \in T_i, i > 0\), entonces\(a \left( t \right) \in T_{i - 1}\).

Un camino a través\(T\) consiste en un subconjunto\(P \subseteq T\) tal que\(P \cap T_i\) contiene exactamente un elemento para cada uno\(i\) y\(P\) se cierra bajo\(a\). Si\(t \in T\), el antecesor inmediato de\(t\) es\(a \left( t \right)\). Y\(t_2\) se dice que un elemento es un antecesor de\(t_1\) si\(t_2 = a \left( a \left( \cdots a \left( t_1 \right) \right) \right) \left( k \: a \text{'s} \right)\) para algunos\(k \geq 1\).

Ahora podemos usar el Teorema de Compacidad para probar

lema 3.3.8: Lema Infinito de König

\(T\)Sea un árbol cuyos niveles sean finitos y no vacíos. Entonces hay un camino a través\(T\).

prueba

Supongamos que se nos da tal árbol\(T\). \(\mathcal{L}\)Sea el lenguaje que consiste en un símbolo constante\(\hat{t}\) por cada elemento\(t \in T\), un símbolo de relación unaria\(Q\), que será cierto para los elementos en el camino, y un símbolo de función unaria\(p\), donde\(p \left( \hat{t}_i \right)\) se pretende ser el antecesor inmediato de\(t_i\).

Dejado\(\Sigma\) ser el siguiente conjunto de\(\mathcal{L}\) -formulas:

\[\Sigma = \begin{cases} \begin{array}{ll} p \left( \hat{t}_1 \right) = \hat{t}_2 & \text{for each} \: t_1, t_2 \in T \: \text{such that} \: a \left( t_1 \right) = t_2 \\ Q \left( \hat{t}_1 \right) \lor \cdots \lor Q \left( \hat{t}_k \right) & \text{where} \: T_n = \{ t_1, t_2, \ldots, t_k \} \: \text{(for each} \: n \text{)} \\ \neg \left( Q \left( \hat{t}_1 \right) \land Q \left( \hat{t}_2 \right) \right) & \text{for} \: t_1, t_2 \in T_n, t_1 \neq t_2 \\ Q \left( \hat{t} \right) \rightarrow Q \left( p \left( \hat{t} \right) \right) & \text{for each} \: t \in T - T_0 \end{array} \end{cases}\]

Afirmamos que\(\Sigma\) es finitamente satisfecha: Dejemos\(\Sigma_0\) ser un subconjunto finito de\(\Sigma\), y\(n\) seamos tan grandes que si\(\hat{t}\) se menciona en\(\Sigma_0\), entonces\(t \in T_0 \cup T_1 \cup \cdots \cup T_n\). Escoge cualquier elemento\(t^* \in T_{n + 1}\), y construye una\(\mathcal{L}\) -estructura\(\mathfrak{A}\) dejando que el universo\(A\) sea el árbol\(T\),\(\hat{t}^\mathfrak{A}\) sea\(t\), dejando\(p^\mathfrak{A}\) ser la función\(a\), y dejando\(Q^\mathfrak{A}\) ser la colección de predecesores de\(t^*\). Es fácil comprobar que\(\mathfrak{A}\) es un modelo de\(\Sigma_0\), y así por compacidad, hay una estructura\(\mathfrak{B}\) tal que\(\mathfrak{B}\) es un modelo de\(\Sigma\). Si dejamos\(P = \{ t \in T | \hat{t}^\mathfrak{B} \in Q^\mathfrak{B} \}\), entonces\(P\) es un camino a través\(T\), y el Lema Infinito de König está probado.

Ejercicios

1. Un intento común de intentar escribir un conjunto de axiomas que caracterizarían\(\mathfrak{N}\) (ver Ejemplo 3.3.3) es dejar\(\Sigma\) ser la colección de todas las\(\mathcal{L}_{NT}\) fórmulas que son verdaderas en\(\mathfrak{N}\), y luego argumentar que esto es un elemento de\(\Sigma\):
   \[\left( \forall x \right) \left( \exists n \right) \left( x = SSS \cdots S0 \left( nS \text{'s} \right) \right).\]
   Por lo tanto, no puede haber elementos no estándar en ningún modelo de\(\Sigma\). Explique por qué falla este razonamiento.
2. Mostrar que si dejamos\(\Sigma = Th \left( \mathfrak{N} \right)\) entrar la construcción del Ejemplo 3.3.3, entonces la estructura\(\mathfrak{A}\) que se construye es elementalmente equivalente a la estructura\(\mathfrak{N}\). Así\(\mathfrak{A}\) es un modelo de aritmética.
3. Demostrar que si\(\mathfrak{A}\) y\(\mathfrak{B}\) son\(\mathcal{L}\) -estructuras tales que\(\mathfrak{A} \cong \mathfrak{B}\), entonces\(\mathfrak{A} \equiv \mathfrak{B}\).
4. Supongamos que\(\Sigma\) es un conjunto de\(\mathcal{L}\) -oraciones tales que al menos una oración de\(\Sigma\) es verdadera en cada\(\mathcal{L}\) -estructura. Demostrar que la disyunción de algunas frases finitamente muchas desde\(\Sigma\) es lógicamente válida.
5. Mostrar que cada modelo no estándar de aritmética contiene un número primo infinito, es decir, un número infinito\(a\) tal que si\(a = bc\), entonces cualquiera\(b = 1\) o\(c = 1\).
6. Mostrar que si\(\phi \left( x \right)\) es una fórmula con una variable libre en\(\mathcal{L}_{NT}\) tal que hay infinitamente muchos números naturales\(a\) tales que\(\mathfrak{N} \models \phi \left( x \right) \left[ s \left[ x | a \right] \right]\), entonces en cada modelo no estándar de aritmética\(\mathfrak{N}^*\) hay un número infinito\(b\) tal que\(\mathfrak{N}^* \models \phi \left( x \right) \left[ s \left[ x | b \right] \right]\).
7. Verificar que podamos usar el Teorema de Compacidad en el Ejemplo 3.3.5 verificando que cada subconjunto finito de\(\Theta\) tiene un modelo.
8. (a) Usando solo conectivos, cuantificadores, variables y el símbolo de igualdad, construir un conjunto de oraciones de\(\Sigma\) tal manera que cada modelo de\(\Sigma\) sea infinito.
   b) Demostrar que si\(\Gamma\) es un conjunto de oraciones con modelos finitos arbitrariamente grandes, entonces\(\Gamma\) tiene un modelo infinito.
   (c) Demostrar que no puede haber ningún conjunto de oraciones en la lógica de primer orden que caracterice a los grupos finitos. (Ver Ejercicio 3 en la Sección 2.8.)
   d) Demostrar que no existe un conjunto finito de oraciones
   \[\Phi = \{ \phi_i, \phi_2, \ldots, \phi_n \}\]
   tales que\(\mathfrak{A} \models \Phi\) si y sólo si\(A\) es infinito. [Sugerencia: Mirar\(\neg \left( \phi_1 \land \phi_2 \land \cdots \land \phi_n \right)\).]
9. Supongamos que\(\Sigma_1\) y\(\Sigma_2\) son dos conjuntos de oraciones tales que ninguna estructura es un modelo de ambos\(\Sigma_1\) y\(\Sigma_2\). Mostrar hay una oración\(\alpha\) tal que cada modelo de\(\Sigma_1\) es también un modelo de\(\alpha\) y además, cada modelo de\(\Sigma_2\) es un modelo de\(\neg \alpha\).
10. Se dice que una relación binaria\(<\) en un conjunto\(A\) es un orden lineal si
    (a)\(<\) es irreflexiva -\(\left( \forall a \in A \right) \left( \neg a < a \right)\).
    b)\(<\) es transitivo -\(\left( \forall a, b, c \in A \right) \left( \left[ a < b \land b < c \right] \rightarrow a < c \right)\).
    c)\(<\) satisfaga la tricotomía - es cierto\(\forall a, b \in A\) exactamente uno de los siguientes:\(a < b\),\(b < a\), o\(a = b\).
    Si un orden lineal\(<\) tiene la propiedad adicional de que no hay cadenas descendentes infinitas - no existen\(a_1, a_2, \ldots \in A\) tales que\(a_1 > a_2 > a_3 \cdots\) (donde\(a_1 > a_2\) significa\(a_2 < a_1\)), entonces la relación\(<\) es un buen orden del conjunto\(A\). Supongamos que\(\mathcal{L}\) es un lenguaje que contiene un símbolo de relación binaria\(<\). Mostrar que no hay conjunto de\(\mathcal{L}\) -oraciones\(\Sigma\) tal que\(\Sigma\) tenga las dos propiedades siguientes:
    (a)\(\Sigma\) tiene un modelo infinito\(\mathfrak{A}\) en el que\(<^\mathfrak{A}\) es un orden lineal de\(A\).
    (b) Si\(\mathfrak{B}\) hay algún modelo infinito de\(\Sigma\), entonces\(<^\mathfrak{B}\) es un bien ordenado de\(B\).
11. Mostrar que no\(<\) es un buen orden en ningún modelo de aritmética no estándar.
12. (a) En la estructura\(\mathfrak{A}\) que se construyó en el Ejemplo 3.3.5, explicar cómo sabemos que
    \[\mathfrak{A} \models \left( \forall x \right) \left[ \left( x \dot{>} \dot{0} \right) \rightarrow \left( x \dot{/} \dot{2} \dot{>} \dot{0} \land x \dot{>} x \dot{/} \dot{2} \right) \right].\]
    (b) Mostrar que\(<\) es un orden lineal de\(A\), el universo de\(\mathfrak{A}\).
    (c) Demostrar que no\(<\) es un buen orden en esta estructura.