3.4: Las subestructuras y los teoremas de Löwenheim-Skolem
- Page ID
- 113476
En esta sección discutiremos una relación entre estructuras. Un conjunto dado de oraciones puede tener muchos modelos diferentes, y resultará que en algunos casos esos modelos están relacionados de maneras sorprendentes. Comenzamos definiendo la noción de una subestructura.
Si\(\mathfrak{A}\) y\(\mathfrak{B}\) son dos\(\mathcal{L}\) -estructuras, diremos que\(\mathfrak{A}\) es una subestructura de\(\mathfrak{B}\), y escribiremos\(\mathfrak{A} \subseteq \mathfrak{B}\), si:
- \(A \subseteq B\).
- Por cada símbolo constante\(c\),\(c^\mathfrak{A} = c^\mathfrak{B}\).
- Por cada símbolo de relación\(n\) -aria\(R\),\(R^\mathfrak{A} = R^\mathfrak{B} \cap A^n\).
- Para cada símbolo de función\(n\) -aria\(f\),\(f^\mathfrak{A} = f^\mathfrak{B} \upharpoonright_{A^n}\). En otras palabras, para cada símbolo\(n\) -ario de función\(f\) y cada\(a \in A\),\(f^\mathfrak{A} \left( a \right) = f^\mathfrak{B} \left( a \right)\). (Esto se llama la restricción de la función\(f^\mathfrak{B}\) al conjunto\(A^n\).)
Así, una subestructura de\(\mathfrak{B}\) está completamente determinada por su universo, y este universo puede ser cualquier subconjunto no vacío del\(B\) que contenga las constantes y esté cerrado bajo cada función\(f\).
Supongamos que tratamos de construir una subestructura\(\mathfrak{A}\) de la estructura\(\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right)\). Ya que se\(A\) debe cerrar bajo las funciones y contener las constantes, el número 0 debe ser un elemento del universo\(A\). Pero ahora, dado que la subestructura debe cerrarse bajo la función\(S\), es evidente que cada número natural debe ser un elemento de\(A\). Por lo tanto, no\(\mathfrak{N}\) tiene subestructuras adecuadas.
Ahora, supongamos que tratamos de encontrar algunas subestructuras de la estructura\(\mathfrak{B} = \left( \mathbb{N}, 0, < \right)\), con las interpretaciones habituales de 0 y\(<\). Como no hay símbolos de función, cualquier subconjunto no vacío del\(\mathbb{N}\) que incluya el número 0 puede servir como universo de una subestructura\(\mathfrak{A} \subseteq \mathfrak{B}\).
Supongamos que dejamos\(\mathfrak{A} = \left( \{ 0 \}, 0, < \right)\). Entonces note que aunque\(\mathfrak{A} \subseteq \mathfrak{B}\), hay un montón de frases que son verdaderas en una estructura que no son ciertas en la otra estructura. Por ejemplo,\(\left( \forall x \right) \left( \exists y \right) x < y\) es falso en\(\mathfrak{A}\) y verdadero en\(\mathfrak{B}\). No va a ser difícil para ti encontrar un ejemplo de una oración que sea verdadera en\(\mathfrak{A}\) y falsa en\(\mathfrak{B}\).
Como muestra el Ejemplo 3.4.3, si se nos dan dos estructuras tales que\(\mathfrak{A} \subseteq \mathfrak{B}\), la mayoría de las veces se\(\mathfrak{B}\) esperaría eso\(\mathfrak{A}\) y sería muy diferente, y habría muchas oraciones que serían ciertas en una de las estructuras que no serían ciertas en la otra.
A veces, sin embargo, la verdad en la estructura más pequeña está más estrechamente ligada a la verdad en la estructura más grande.
Supongamos que\(\mathfrak{A}\) y\(\mathfrak{B}\) son\(\mathcal{L}\) -estructuras y\(\mathfrak{A} \subseteq \mathfrak{B}\). Decimos que\(\mathfrak{A}\) es una subestructura elemental de\(\mathfrak{B}\) (equivalentemente,\(\mathfrak{B}\) es una extensión elemental de\(\mathfrak{A}\)), y escribimos\(\mathfrak{A} \prec \mathfrak{B}\), si por cada\(s : Vars \rightarrow A\) y para cada\(\mathcal{L}\) -fórmula\(\phi\),
\[\mathfrak{A} \models \phi \left[ s \right] \: \text{if and only if} \: \mathfrak{B} \models \phi \left[ s \right].\]
Chaff:Observe que si queremos probar\(\mathfrak{A} \prec \mathfrak{B}\), sólo necesitamos probarlo\(\mathfrak{A} \models \phi \left[ s \right] \rightarrow \mathfrak{B} \models \phi \left[ s \right]\), ya que una vez que lo hemos hecho, la otra dirección viene de forma gratuita utilizando el contrapositivo y las negaciones.
Supongamos que\(\mathfrak{A} \prec \mathfrak{B}\). Entonces una oración\(\sigma\) es verdadera en\(\mathfrak{A}\) si y sólo si es verdad en\(\mathfrak{B}\).
Ejercicio 5.
Vimos antes que la estructura\(\mathfrak{B} = \left( \mathbb{N}, 0, < \right)\) tiene muchas subestructuras. Sin embargo, no\(\mathfrak{B}\) tiene subestructuras elementales adecuadas. Por supongamos que\(\mathfrak{A} \prec \mathfrak{B}\). Ciertamente,\(0 \in A\), como\(\mathfrak{A}\) es una subestructura. Dado que la oración\(\left( \exists y \right) \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right]\) es verdadera en\(\mathfrak{B}\), debe ser verdad\(\mathfrak{A}\) también en. Entonces
\[\mathfrak{A} \models \left( \exists y \right) \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right].\]
Así, para cualquier función de asignación\(s : Vars \rightarrow A\) hay alguna\(a \in A\) tal que
\[\mathfrak{A} \models \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right] \left[ s \left[ y | a \right] \right].\]
Arreglar tal\(s\) y tal\(a \in A\). Ahora volvemos a usar la elementaridad. Desde\(\mathfrak{A} \prec \mathfrak{B}\) y\(s \left[ y | a \right] : Vars \rightarrow A\), sabemos que
\[\mathfrak{B} \models \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right] \left[ s \left[ y | a \right] \right].\]
Pero en la estructura\(\mathfrak{B}\), hay un elemento único que hace\(\left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right]\) verdadera la fórmula, es decir, el número 1. Entonces\(a\) debe ser el número 1, y así 1 debe ser un elemento de\(A\). Del mismo modo, se puede demostrar eso\(2 \in A\)\(3 \in A\),, y así sucesivamente. Así\(\mathbb{N} \subseteq A\), y no\(\mathfrak{A}\) será una adecuada subestructura elemental de\(\mathfrak{B}\).
Este ejemplo muestra que al construir una subestructura elemental de una estructura dada\(\mathfrak{B}\), necesitamos asegurarnos de que los testigos de cada oración existencial verdadera en\(\mathfrak{B}\) deben incluirse en el universo de la subestructura elemental\(\mathfrak{A}\). Esa idea será el núcleo de la prueba del Teorema de Löwenheim-Skolem hacia abajo, Teorema 3.4.8. De hecho, el siguiente lema dice que asegurarse de que tales testigos sean elementos de\(\mathfrak{A}\) es todo lo que se necesita para asegurar que\(\mathfrak{A}\) sea una subestructura elemental de\(\mathfrak{B}\).
Supongamos eso\(\mathfrak{A} \subseteq \mathfrak{B}\) y aquello para cada fórmula\(\alpha\) y cada\(s : Vars \rightarrow A\) tal que\(\mathfrak{B} \models \exists x \alpha \left[ s \right]\) haya\(a \in A\) tal eso\(\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]\). Entonces\(\mathfrak{A} \prec \mathfrak{B}\).
Vamos a mostrar, dados los supuestos del lema, que si\(\phi\) es alguna fórmula y\(s\) es cualquier función de asignación de variables en\(A\),\(\mathfrak{A} \models \phi \left[ s \right]\) si y sólo si\(\mathfrak{B} \models \phi \left[ s \right]\), y así\(\mathfrak{A} \prec \mathfrak{B}\).
Esta es una prueba fácil por inducción sobre la complejidad de\(\phi\), lo que haremos aún más fácil al señalar que podemos reemplazar el paso\(\forall\) inductivo por un paso\(\exists\) inductivo, como se\(\forall\) puede definir en términos de\(\exists\).
Entonces, para el caso base, supongamos que eso\(\phi\) es atómico. Por ejemplo, si\(\phi\) es\(R \left( x, y \right)\), entonces\(\mathfrak{A} \models \phi \left[ s \right]\) si y solo si\(\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{A}\). Pero\(R^\mathfrak{A} = R^\mathfrak{B} \cap A^2\), así\(\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{A}\) si y sólo si\(\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{B}\). Pero\(\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{B}\) si y sólo si\(\mathfrak{B} \models \phi \left[ s \right]\), según sea necesario.
Para las cláusulas inductivas, supongamos que\(\phi\) es\(\neg \alpha\). Entonces
\[\begin{array}{rll} \mathfrak{A} \models \phi \left[ s \right] & \text{if and only if} \: \mathfrak{A} \models \neg \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{A} \not\models \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{B} \not\models \alpha \left[ s \right] & \text{inductive hypothesis \\ & \text{if and only if} \: \mathfrak{B} \models \neg \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{B} \models \phi \left[ s \right]. \end{array}\]
La segunda cláusula inductiva, si\(\phi\) es\(\alpha \lor \beta\), es similar.
Para la última cláusula inductiva, supongamos que\(\phi\) es\(\exists x \alpha\). Supongamos también eso\(\mathfrak{A} \models \phi \left[ s \right]\); en otras palabras,\(\mathfrak{A} \models \exists x \alpha \left[ s \right]\). Entonces, para algunos\(a \in A\),\(\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]\). Dado que\(s \left[ x | a \right]\) es una función que mapea variables en\(A\), por nuestra hipótesis inductiva,\(\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]\). Pero entonces\(\mathfrak{B} \models \exists x \alpha \left[ s \right]\), según sea necesario. Para la otra dirección, supongamos que\(\mathfrak{B} \models \exists x \alpha \left[ s \right]\), dónde\(s : Vars \rightarrow A\). Utilizamos la suposición del lema para encontrar un\(a \in A\) tal que\(\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]\). Como\(s \left[ x | a \right]\) es una función con codominio\(A\), por la hipótesis inductiva\(\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]\), y así\(\mathfrak{B} \models \exists x \alpha \left[ s \right]\), y la prueba es completa.
Chaff: Ahora vamos a ver los Teoremas de Löwenheim-Skolem, que se publicaron en 1915. Para entender estos teoremas, es necesario tener al menos una comprensión básica de la cardinalidad, tema que se esboza en el Apéndice. No obstante, si tienes prisa, bastará si simplemente recuerdas que hay muchos tamaños diferentes de conjuntos infinitos. Un conjunto infinito\(A\) es contable si hay una biyección entre\(A\) y el conjunto de números naturales\(\mathbb{N}\), de lo contrario, el conjunto es incontable. Ejemplos de conjuntos contables incluyen los enteros y el conjunto de números racionales. El conjunto de números reales es incontable, en que no hay bijección entre\(\mathbb{R}\) y\(\mathbb{N}\). Entonces hay más reales que números naturales. Hay infinitamente muchos tamaños diferentes de conjuntos infinitos. El tamaño infinito más pequeño es contable.
Supongamos que\(\mathcal{L}\) es un lenguaje contable y\(\mathfrak{B}\) es una\(\mathcal{L}\) -estructura. Entonces\(\mathfrak{B}\) tiene una subestructura elemental contable.
Si\(B\) es finito o infinito contable, entonces\(\mathfrak{B}\) es su propia subestructura elemental contable, así que supongamos que\(B\) es incontable. Como el lenguaje\(\mathcal{L}\) es contable, solo hay contablemente muchas\(\mathcal{L}\) -fórmulas, y por lo tanto solo contabilizadamente muchas fórmulas de la forma\(\exists x \alpha\).
Dejar\(A_0\) ser cualquier subconjunto contable no vacío de\(B\). Mostramos cómo construir\(A_1\) tal que\(A_0 \subseteq A_1\), y\(A_1\) es contable. La idea es sumar a\(A_0\) los testigos de la verdad (in\(\mathfrak{B}\)) de las declaraciones existenciales.
Observe que como\(A_0\) es contable, solo hay contabilizadamente muchas funciones\(s^\prime : Vars \rightarrow A_0\) que eventualmente son constantes, con lo que queremos decir que hay un número natural\(k\) tal que si\(i, j > k\), entonces\(s^\prime \left( v_i \right) = s^\prime \left( v_j \right)\). (Este es un buen ejercicio para aquellos de ustedes que han tenido un curso de teoría de conjuntos o se sienten razonablemente cómodos con los argumentos de cardinalidad). También, si nos dan alguna\(\phi\) y alguna\(s : Vars \rightarrow A_0\), podemos encontrar una eventual constante\(s^\prime : Vars \rightarrow A_0\) tal que\(s\) y\(s^\prime\) ponernos de acuerdo en las variables libres de\(\phi\), y así\(\mathfrak{B} \models \phi \left[ s \right]\) si y sólo si\(\mathfrak{B} \models \phi \left[ s^\prime \right]\).
La construcción de\(A_1\): Para cada fórmula de la forma\(\exists x \alpha\) y cada uno\(s : Vars \rightarrow A_0\) tal que\(\mathfrak{B} \models \exists x \alpha \left[ s \right]\), encontrar una eventual constante\(s^\prime : Vars \rightarrow A_0\) tal que\(s\) y\(s^\prime\) ponerse de acuerdo en las variables libres de\(\exists x \alpha\). Escoge un elemento\(a_{\alpha, s^\prime} \in B\) tal que\(\mathfrak{B} \models \alpha \left[ s \left[ x | a_{\alpha, s^\prime} \right] \right]\), y deja
\[A_1 = A_0 \cup \{ a_{\alpha, s^\prime} \}_{\text{all} \: \alpha, s : Vars \rightarrow A_0}.\]
Observe que\(A_1\) es contable, ya que solo hay contabilizadamente muchos\(\alpha\) y contablemente muchos\(s^\prime\).
Continuar esta construcción, construyendo iterativamente\(A_{n+1}\) desde\(A_n\). Vamos\(A = \cup_{n=0}^\infty A_n\). Como\(A\) es una unión contable de conjuntos contables,\(A\) es contable.
Ahora hemos construido un universo potencial\(A\) para una subestructura para\(\mathfrak{B}\). Tenemos que probar que\(A\) se cierra bajo las funciones de\(\mathfrak{B}\) (por las observaciones que siguen a la Definición 3.4.1 esto demuestra que\(\mathfrak{A}\) es una subestructura de\(\mathfrak{B}\)), y tenemos que demostrar que\(\mathfrak{A}\) satisface los criterios establecidos en Lemma 3.4.7, así sabremos que\(\mathfrak{A}\) es una subestructura elemental de\(\mathfrak{B}\).
Primero, para mostrar que\(A\) se cierra bajo las funciones de\(\mathfrak{B}\), supongamos que\(a \in A\) y\(f\) es un símbolo de función unario (el caso general es idéntico) y eso\(b = f^\mathfrak{B} \left( a \right)\). Debemos demostrarlo\(b \in A\). Fijar un\(n\) tan grande que\(a \in A_n\), dejar\(\phi\) ser la fórmula\(\left( \exists y \right) y = f \left( x \right)\), y dejar\(s\) ser cualquier función de asignación en\(A\) tal que\(s \left( x \right) = a\). Eso lo sabemos\(\mathfrak{B} \models \left( \exists y \right) y = f \left( x \right) \left[ s \right]\), y sabemos que si\(\mathfrak{B} \models \left( y = f \left( x \right) \right) \left[ s \left[ y | d \right] \right]\), entonces\(d = b\). Entonces, en nuestra construcción de\(A_{n+1}\) debemos haber utilizado\(a_{y = f \left( x \right), s} = b\), así\(b \in A_{n+1}\), y\(b \in A\), según sea necesario.
Para poder utilizar Lemma 3.4.7, debemos demostrar que si\(\alpha\) es una fórmula y\(s : Vars \rightarrow A\) es tal que\(\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]\). Entonces, arregle tal\(\alpha\) y tal\(s\). Encontrar una eventual constante\(s^\prime : Vars \rightarrow A\) tal que\(s\) y\(s^\prime\) ponerse de acuerdo en todas las variables libres de\(\alpha\). Así\(\mathfrak{B} \models \exists x \alpha \left[ s^\prime \right]\), y todos los valores de\(s^\prime\) son elementos de algunos fijos\(A_n\), ya que\(s^\prime\) toma sólo un número finito de valores. Pero luego por la construcción de\(A_{n+1}\) tal que\(\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]\), según sea necesario.
Entonces hemos cumplido con las hipótesis de Lema 3.4.7, y así\(\mathfrak{A}\) es una subestructura elemental contable de\(\mathfrak{B}\), según sea necesario.
Chaff: Nos gustaría ver un poco más de esta prueba un poco más de cerca. En la construcción de\(A_1\), lo que hicimos fue encontrar una\(a_{\infty, s^\prime}\) para cada fórmula\(\exists x \alpha\) y cada una\(s : Vars \rightarrow A\), y el punto era que\(a_{\infty, s^\prime}\) sería testigo de la verdad en\(\mathfrak{B}\) del enunciado existencial\(\exists x \alpha\). Así que hemos construido una función que, dada una fórmula existencial\(\exists x \alpha\) y una función de asignación, encuentra un valor para\(x\) que la fórmula sea\(\alpha\) verdadera. Una función de este tipo se llama función de Skolem, y la construcción de\(A\) en la prueba del Teorema de Löwenheim-Skolem hacia abajo se puede resumir así: Let\(A_0\) be a countable subset of\(B\), and form the closure of\(A_0\) under the set of all Skolem functions. Entonces mostrar que este cierre es una subestructura elemental de\(\mathfrak{B}\).
Vimos una indicación en el Ejercicio 4 en la Sección 2.8 de que los axiomas de la teoría de conjuntos de Zermelo-Fraenkel (conocida como ZF) pueden formalizarse en lógica de primer orden. Aceptando eso como cierto (lo que es), sabemos que si los axiomas son consistentes tienen un modelo, y luego por el Teorema de Löwenheim-Skolem hacia abajo, debe haber un modelo contable para la teoría de conjuntos. Pero esto es interesante, ya que los siguientes son todos los teoremas de ZF:
- Hay un conjunto contablemente infinito.
- Si\(a\) existe un conjunto, entonces la colección de subconjuntos de\(a\) existe.
- Si\(a\) es contablemente infinito, entonces la colección de subconjuntos de\(a\) es incontable. (Este es el Teorema de Cantor).
Ahora, supongamos que ese\(\mathfrak{A}\) es nuestro modelo contable de ZF, y supongamos que\(a\) es un elemento de\(A\) y es contablemente infinito. Si\(b\) es el conjunto de todos los subconjuntos de\(a\), sabemos que\(b\) es incontable (según el Teorema de Cantor) y sin embargo\(b\) debe ser contable, ya que todos los elementos de\(b\) están en el modelo\(\mathfrak{A}\), ¡y\(\mathfrak{A}\) es contable! ¡Así que\(b\) debe ser tanto contable como incontable! Esto se llama (algo incorrectamente) la paradoja de Skolem, y el Ejercicio 8 te pide que descubras la solución a la paradoja
Probablemente la manera de pensar sobre el Teorema de Löwenheim-Skolem hacia abajo es que garantiza que si hay modelos infinitos de un conjunto dado de fórmulas, entonces hay un modelo pequeño (contablemente infinito significa pequeño) de ese conjunto de fórmulas. Parece razonable preguntar si hay una garantía similar sobre los modelos grandes, y la hay.
Supongamos que\(\Sigma\) es un conjunto de\(\mathcal{L}\) -fórmulas con un modelo infinito. Si\(\kappa\) es un cardenal infinito, entonces hay un modelo\(\Sigma\) de cardinalidad mayor o igual a\(\kappa\).
Esta es una aplicación fácil del Teorema de Compacidad. Expandir\(\mathcal{L}\) para incluir\(\kappa\) nuevos símbolos constantes\(c_i\), y dejar\(\Gamma = \Sigma \cup \{ c_i \neq c_j | i \neq j \}\). Entonces\(\Gamma\) es finitamente satisfecha, ya que podemos tomar nuestro modelo infinito dado\(\Sigma\) e interpretar el\(c_i\) en ese modelo de tal manera que\(c_i \neq c_j\) para cualquier conjunto finito de símbolos constantes. Por el Teorema de la Compacidad, existe una estructura\(\mathfrak{A}\) que es un modelo de\(\Gamma\), y así ciertamente la cardinalidad de\(A\) es mayor o igual a\(\kappa\). Si nos restringimos\(\mathfrak{A}\) al idioma original, obtenemos un modelo\(\Sigma\) de la cardinalidad requerida.
Si\(\Sigma\) es un conjunto de fórmulas de un lenguaje contable con un modelo infinito, y si\(\kappa\) es un cardenal infinito, entonces hay un modelo\(\Sigma\) de cardinalidad\(\kappa\).
Primero, usa la Proposición 3.4.10 para obtener\(\mathfrak{B}\), un modelo\(\Sigma\) de cardinalidad mayor o igual a\(\kappa\). Entonces, imitar la prueba del Teorema de Löwenheim-Skolem hacia abajo, comenzando con un conjunto\(A_0 \subseteq B\) de cardinalidad exactamente\(\kappa\). Entonces el\(A\) que se construye en esa prueba también tendrá cardinalidad\(\kappa\), y como\(\mathfrak{A} \prec \mathfrak{B}\),\(\mathfrak{A}\) será un modelo\(\Sigma\) de cardinalidad\(\kappa\).
Si\(\mathfrak{A}\) es una\(\mathcal{L}\) estructura infinita, entonces no hay un conjunto de fórmulas de primer orden que caractericen\(\mathfrak{A}\) hasta el isomorfismo.
Más precisamente, el corolario dice que no hay un conjunto de fórmulas\(\Sigma\) tales que\(\mathfrak{B} \models \Sigma\) si y sólo si\(\mathfrak{A} \cong \mathfrak{B}\). Sabemos que hay modelos\(\Sigma\) de todas las cardinalidades, y sabemos que no hay bijecciones entre conjuntos de diferentes cardinalidades. Por lo que debe haber muchos modelos de\(\Sigma\) que no son isomórficos a\(\mathfrak{A}\).
Chaff: Hay conjuntos de axiomas que sí caracterizan estructuras infinitas. Por ejemplo, los axiomas de segundo orden de la Aritmética Peano incluyen axiomas para asegurar que la suma y la multiplicación se comporten normalmente, y también incluyen el principio de inducción matemática: Si\(M\) es un conjunto de números, si\(0 \in M\), y si\(S \left( n \right) \in M\) para cada uno de\(n\) tales que\(n \in M\), entonces\(\left( \forall n \right) \left( n \in M \right)\).
Cualquier modelo de Aritmética Peano es isomórfico a los números naturales, pero fíjense que utilizamos dos nociones (conjuntos de números y la relación elementhood) que no forman parte de nuestra descripción de\(\mathfrak{N}\). Al introducir conjuntos de números hemos dejado el mundo de la lógica de primer orden y hemos entrado en la lógica de segundo orden, y es solo usando la lógica de segundo orden que somos capaces de caracterizar\(\mathfrak{N}\). Para una agradable discusión de este tema, véase [Campana y Machover 77, Capítulo 7, Sección 2].
Los resultados de la Proposición 3.4.10 al Corolario 3.4.12 nos dan modelos que son grandes, pero tienen un sabor ligeramente diferente al del Teorema de Löwenheim-Skolem hacia abajo, en que no garantizan que el modelo pequeño sea una subestructura elemental del modelo grande. Ese es el contenido del Teorema de Löwenheim-Skolem hacia arriba, prueba del cual se esboza en los Ejercicios.
Si\(\mathcal{L}\) es un lenguaje contable,\(\mathfrak{A}\) es una\(\mathcal{L}\) infinita-estructura, y\(\kappa\) es un cardinal, entonces\(\mathfrak{A}\) tiene una extensión elemental\(\mathfrak{B}\) tal que la cardinalidad de\(B\) es mayor o igual a\(\kappa\).
Ejercicios
- Supongamos que\(\mathfrak{B} \subseteq \mathfrak{A}\), eso\(\phi\) es de la forma\(\left( \forall x \right) \psi\), dónde\(\psi\) está libre de cuantificadores, y eso\(\mathfrak{A} \models \phi\). \(\mathfrak{B} \models \phi\)Demuéstralo. La versión corta de este hecho es, “Las oraciones universales se conservan a la baja”. Formular y probar el hecho correspondiente para oraciones existenciales.
- Justificar la Chaff siguiendo la Definición 3.4.4.
- \(\mathfrak{A} \prec \mathfrak{B}\)Demuéstralo si\(\mathfrak{C} \prec \mathfrak{B}\) y y\(\mathfrak{A} \subseteq \mathfrak{C}\), entonces\(\mathfrak{A} \prec \mathfrak{C}\).
- Supongamos que tenemos una cadena elemental, un conjunto de\(\mathcal{L}\) -estructuras tales que
\[\mathfrak{A}_1 \prec \mathfrak{A}_2 \prec \mathfrak{A}_3 \prec \cdots\]
y dejar\(\mathfrak{A} = \bigcup^\infty_{i=1} \mathfrak{A}_i\). Entonces el universo\(A\) de\(\mathfrak{A}\) es la unión de los universos\(A_i\),\(R^\mathfrak{A} = \bigcup^\infty_{i=1} R^{\mathfrak{A}_i}\), etc. Demuéstralo\(\mathfrak{A}_i \prec \mathfrak{A}\) para cada uno\(i\). [Sugerencia: Demostrar eso\(\mathfrak{A}_i \subseteq \mathfrak{A}\) es bastante fácil por la definición. Para conseguir que\(\mathfrak{A}\) sea una extensión elemental, hay que utilizar la inducción sobre la complejidad de las fórmulas. Observe por los comentarios que siguen a la Definición 3.4.4 que solo necesita acreditar una dirección. Puede resultarle más fácil de usar\(\forall\) en\(\exists\) lugar de en la parte cuantificadora del paso inductivo de la prueba.] - Demostrar Proposición 3.4.5.
- Demostrar que si\(\mathfrak{A} \prec \mathfrak{B}\) y si hay un elemento\(b \in B\) y una fórmula\(\phi \left( x \right)\) tal que\(\mathfrak{B} \models \phi \left[ s \left[ x | b \right] \right]\) y para todos los demás\(\hat{b} \in B\),\(\mathfrak{B} \not\models \phi \left[ s \left[ x | \hat{b} \right] \right]\), entonces\(b \in A\). [Sugerencia: Esto es muy similar al Ejemplo 3.4.6.]
- Supongamos eso\(\mathfrak{B} = \{ \mathbb{N}, +, \cdot \}\), y vamos\(A_0 = \{ 2, 3 \}\). Dejar\(F\) ser el conjunto de funciones de Skolem\(\{ f_{\alpha, s} \}\) correspondientes a\(\alpha\)'s de la forma\(\left( \exists x \right) x = yz\). Encuentra el cierre de\(A_0\) under\(F\). [Sugerencia: No olvide que las funciones de asignación\(s\) que necesita considerar son funciones mapeadas\(A_0\) al principio, luego\(A_1\), y así sucesivamente. Probablemente quieras escribir explícitamente\(A_1\), entonces\(A_2\), etc. Estamos usando la notación aquí correspondiente a la prueba del Teorema 3.4.8.]
- Decir que un conjunto\(a\) es contable significa que hay una función con dominio los números naturales y codominio\(a\) que es una biyección. Observe que se trata de una afirmación existencial, diciendo que existe cierto tipo de función. Ahora, piense en el Ejemplo 3.4.9 y vea si puede averiguar por qué no es realmente una contradicción que el conjunto\(b\) sea a la vez contable e incontable. En particular, piense en lo que significa que una afirmación existencial sea verdadera en una estructura\(\mathfrak{A}\), en contraposición a la verdad en el mundo real (¡lo que sea que eso signifique!).
- (Hacia la Prueba del Teorema de Löwenheim-Skolem Hacia Arriba) Si\(\mathfrak{A}\) es una (\ mathcal {L}\) -estructura, let\(\mathcal{L} \left( A \right) = \mathcal{L} \cup \{ \bar{a} | a \in A \}\), donde cada uno\(\bar{a}\) es un nuevo símbolo constante. Entonces, dejemos\(\bar{\mathfrak{A}}\) ser la\(\mathcal{L} \left( A \right)\) -estructura teniendo el mismo universo como\(\mathfrak{A}\) y la misma interpretación de los símbolos de\(\mathcal{L}\) como\(\mathfrak{A}\), e interpretando cada uno\(\bar{a}\) como\(a\). Entonces definimos el diagrama completo de\(\mathfrak{A}\) como
\[Th \left( \bar{\mathfrak{A}} \right) = \{ \sigma | \sigma \: \text{is an} \: \mathcal{L} \left( A \right) \text{-formula such that} \: \bar{\mathfrak{A}} \models \sigma \}.\]
Mostrar que si\(\bar{\mathfrak{B}}\) es algún modelo de\(Th \left( \bar{\mathfrak{A}} \right)\), y si\(\mathfrak{B} = \bar{\mathfrak{B}} \upharpoonright_\mathcal{L}\), entonces\(\mathfrak{A}\) es isomorfo a una subestructura elemental de\(\mathfrak{B}\). [Sugerencia:\(h : A \rightarrow B\) Déjese dar por\(h \left( a \right) = \bar{a}^\mathfrak{B}\). Deja\(C\) ser el rango de\(h\). \(C\)El espectáculo está cerrado bajo\(f^\mathfrak{B}\) para cada\(f\) en\(\mathcal{L}\), y así\(C\) es el universo de\(\mathfrak{C}\), una subestructura de\(\mathfrak{B}\). Entonces el espectáculo\(h\) es un isomorfismo entre\(\mathfrak{A}\) y\(\mathfrak{C}\). Por último,\(\mathfrak{C} \prec \mathfrak{B}\) demuéstralo.] - Utilice el Ejercicio 9 para probar el Teorema de Löwenheim-Skolem hacia arriba encontrando un modelo\(\bar{\mathfrak{B}}\) del diagrama completo del modelo dado\(\mathfrak{A}\) tal que la cardinalidad de\(\bar{B}\) sea mayor o igual a\(\kappa\).
- Ahora podemos rellenar algunos de los detalles de nuestra discusión del análisis no estándar del Ejemplo 3.3.5. Como el lenguaje\(\mathcal{L}_\mathbb{R}\) de ese ejemplo ya incluye símbolos constantes para cada número real, el diagrama completo de no\(\mathfrak{R}\) es más que\(Th \left( \mathfrak{R} \right)\). Explique cómo el Ejercicio 9 muestra que existe una copia isomórfica de la línea real que vive dentro de la estructura\(\mathfrak{A}\).