Artículos

3.4: Subestructuras y teoremas de Löwenheim-Skolem - Matemáticas

3.4: Subestructuras y teoremas de Löwenheim-Skolem - Matemáticas



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

En esta sección discutiremos una relación entre estructuras. Comenzamos por definir la noción de subestructura.

Definición 3.4.1.

Si ( mathfrak {A} ) y ( mathfrak {B} ) son dos ( mathcal {L} ) - estructuras, diremos que ( mathfrak {A} ) es una infraestructura de ( mathfrak {B} ), y escriba ( mathfrak {A} subseteq mathfrak {B} ), si:

  1. (A subseteq B ).
  2. Para cada símbolo constante (c ), (c ^ mathfrak {A} = c ^ mathfrak {B} ).
  3. Para cada (n ) - símbolo de relación aria (R ), (R ^ mathfrak {A} = R ^ mathfrak {B} cap A ^ n ).
  4. Para cada (n ) - símbolo de función aria (f ), (f ^ mathfrak {A} = f ^ mathfrak {B} upharpoonright_ {A ^ n} ). En otras palabras, para cada (n ) - símbolo de función aria (f ) y cada (a in A ), (f ^ mathfrak {A} left (a right) = f ^ mathfrak {B} left (a right) ). (Esto se llama 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 de (B ) que contenga las constantes y esté cerrado bajo cada función (f ).

Ejemplo 3.4.2:

Supongamos que intentamos construir una subestructura ( mathfrak {A} ) de la estructura ( mathfrak {N} = left ( mathbb {N}, 0, S, +, cdot, E, < derecho)). Dado que (A ) debe cerrarse 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 ), está claro que todo número natural debe ser un elemento de (A ). Por tanto, ( mathfrak {N} ) no tiene subestructuras adecuadas.

Ejemplo 3.4.3:

Ahora, suponga que intentamos encontrar algunas subestructuras de la estructura ( mathfrak {B} = left ( mathbb {N}, 0, < right) ), con las interpretaciones habituales de 0 y (< ). Dado que no hay símbolos de función, cualquier subconjunto no vacío de ( mathbb {N} ) que incluya el número 0 puede servir como el universo de una subestructura ( mathfrak {A} subseteq mathfrak {B} ).

Supongamos que dejamos ( mathfrak {A} = left ( {0 }, 0, < right) ). Luego observe que aunque ( mathfrak {A} subseteq mathfrak {B} ), hay muchas oraciones que son verdaderas en una estructura que no lo son en la otra estructura. Por ejemplo, ( left ( forall x right) left ( exist y right) x

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 esperaría que ( mathfrak {A} ) y ( mathfrak {B} ) sería muy diferente, y habría muchas oraciones que serían verdaderas en una de las estructuras que no serían verdaderas en la otra.

A veces, sin embargo, la verdad en la estructura más pequeña está más estrechamente vinculada a la verdad en la estructura más grande.

Definición 3.4.4.

Suponga 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 escriba ( mathfrak {A} prec mathfrak {B} ), si para cada (s: Vars rightarrow A ) y para cada ( mathcal {L} ) - fórmula ( phi ),

[ mathfrak {A} modelos phi left [s right] : text {si y solo si} : mathfrak {B} models phi left [s right]. ]

Paja: Note que si queremos probar ( mathfrak {A} prec mathfrak {B} ), solo necesitamos probar ( mathfrak {A} models phi left [s right] rightarrow mathfrak {B} models phi left [s right] ), ya que una vez que hemos hecho eso, la otra dirección viene gratis usando el contrapositivo y las negaciones.

Proposición 3.4.5.

Suponga que ( mathfrak {A} prec mathfrak {B} ). Entonces una oración ( sigma ) es verdadera en ( mathfrak {A} ) si y solo si es verdadera en ( mathfrak {B} ).

Ejemplo 3.4.6:

Vimos anteriormente que la estructura ( mathfrak {B} = left ( mathbb {N}, 0, < right) ) tiene muchas subestructuras. Sin embargo, ( mathfrak {B} ) no tiene subestructuras elementales adecuadas. Supongamos que ( mathfrak {A} prec mathfrak {B} ). Ciertamente, (0 in A ), ya que ( mathfrak {A} ) es una subestructura. Dado que la oración ( left ( exist y right) left [0

[ mathfrak {A} modelos left ( existe y right) left [0

Por lo tanto, para cualquier función de asignación (s: Vars rightarrow A ) hay alguna (a in A ) tal que

[ mathfrak {A} models left [0

Arregle tal (s ) y tal (a en A ). Ahora usamos la elementariedad nuevamente. Desde ( mathfrak {A} prec mathfrak {B} ) y (s left [y | a right]: Vars rightarrow A ), sabemos que

[ mathfrak {B} models left [0

Pero en la estructura ( mathfrak {B} ), hay un elemento único que hace que la fórmula ( left [0

Este ejemplo muestra que cuando se construye una subestructura elemental de una estructura dada ( mathfrak {B} ), debemos 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 demostración del Teorema descendente de Löwenheim-Skolem, 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} ).

Lema 3.4.7.

Suponga que ( mathfrak {A} subseteq mathfrak {B} ) y que para cada fórmula ( alpha ) y cada (s: Vars rightarrow A ) tal que ( mathfrak {B} modelos existe x alpha left [s right] ) hay una (a in A ) tal que ( mathfrak {B} models alpha left [s left [x | a ien bien]). Entonces ( mathfrak {A} prec mathfrak {B} ).

prueba

Demostraremos, dados los supuestos del lema, que si ( phi ) es cualquier fórmula y (s ) es cualquier función de asignación de variable en (A ), ( mathfrak {A} modelos phi left [s right] ) si y solo si ( mathfrak {B} models phi left [s right] ), y por lo tanto ( mathfrak {A} prec mathfrak {B } ).

Ésta es una demostración fácil por inducción de la complejidad de ( phi ), que haremos aún más fácil al señalar que podemos reemplazar el paso inductivo ( forall ) por un paso inductivo ( existe ), como ( forall ) se puede definir en términos de ( existe ).

Entonces, para el caso base, asuma que ( 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 ), entonces ( left (s left (x right), s left (y right) derecha) en R ^ mathfrak {A} ) si y solo 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 solo si ( mathfrak {B} models phi left [s right] ), según sea necesario.

Para las cláusulas inductivas, suponga que ( phi ) es ( neg alpha ). Luego

[ begin {array} {rll} mathfrak {A} models phi left [s right] & text {si y solo si} : mathfrak {A} models neg alpha left [s right] & & text {si y solo si} : mathfrak {A} not models alpha left [s right] & & text {si y solo si} : mathfrak {B} not models alpha left [s right] & text {hipótesis inductiva & text {si y solo si} : mathfrak {B} models neg alpha left [s right] & & text {si y solo si} : mathfrak {B} models phi left [s right]. end {matriz} ]

La segunda cláusula inductiva, si ( phi ) es ( alpha lor beta ), es similar.

Para la última cláusula inductiva, suponga que ( phi ) es ( existe x alpha ). Supongamos también que ( mathfrak {A} modelos phi left [s right] ); en otras palabras, ( mathfrak {A} modelos existe 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 asigna variables a (A ), según nuestra hipótesis inductiva, ( mathfrak {B} models alpha left [s left [ x | a derecha] derecha] ). Pero luego ( mathfrak {B} modelos existe x alpha left [s right] ), según sea necesario. Para la otra dirección, suponga que ( mathfrak {B} modelos existe x alpha left [s right] ), donde (s: Vars rightarrow A ). Usamos 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 ), según la hipótesis inductiva ( mathfrak {A} models alpha left [s left [x | a right] right] ), y por lo tanto ( mathfrak {B} models existe x alpha left [s right] ), y la demostración está completa.

Paja: Ahora veremos los Teoremas de Löwenheim-Skolem, que se publicaron en 1915. Para comprender estos teoremas, es necesario tener al menos una comprensión básica de la cardinalidad, un tema que se describe en el Apéndice. Sin embargo, si tiene prisa, será suficiente si simplemente recuerda 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. Los ejemplos de conjuntos contables incluyen los números enteros y el conjunto de números racionales. El conjunto de números reales es incontable, ya que no hay biyección entre ( mathbb {R} ) y ( mathbb {N} ). Entonces, hay más reales que números naturales. Hay infinitos tamaños diferentes de conjuntos infinitos. El tamaño infinito más pequeño es contable.

Teorema 3.4.8: Teorema descendente de löwenheim-skolem

Suponga que ( mathcal {L} ) es un lenguaje contable y que ( mathfrak {B} ) es una estructura ( mathcal {L} ). Entonces ( mathfrak {B} ) tiene una subestructura elemental contable.

prueba

Si (B ) es finito o infinito contable, entonces ( mathfrak {B} ) es su propia subestructura elemental contable, así que suponga que (B ) es incontable. Como el lenguaje ( mathcal {L} ) es contable, solo hay un número contable de ( mathcal {L} ) - fórmulas y, por lo tanto, solo un número contable de fórmulas de la forma ( existe x alpha ) .

Sea (A_0 ) cualquier subconjunto numerable no vacío de (B ). Mostramos cómo construir (A_1 ) tal que (A_0 subseteq A_1 ), y (A_1 ) sea contable. La idea es agregar a (A_0 ) testigos de la verdad (en ( mathfrak {B} )) de los enunciados existenciales.

Observe que como (A_0 ) es contable, solo hay muchas funciones (s ^ prime: Vars rightarrow A_0 ) que son eventualmente constantes, por 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 en teoría de conjuntos o se sienten razonablemente cómodos con los argumentos de cardinalidad). Además, si se nos da cualquier ( phi ) y cualquier (s: Vars rightarrow A_0 ), podemos encontrar una constante (s ^ prime: Vars rightarrow A_0 ) tal que (s ) y (s ^ prime ) concuerdan en las variables libres de ( phi ), y así ( mathfrak {B} models phi left [s right] ) si y solo si ( mathfrak {B} models phi left [s ^ prime right] ).

La construcción de (A_1 ): Para cada fórmula de la forma ( existe x alpha ) y cada (s: Vars rightarrow A_0 ) tal que ( mathfrak {B} modelos existe x alpha left [s right] ), encuentre una constante (s ^ prime: Vars rightarrow A_0 ) tal que (s ) y (s ^ prime ) coincidan en las variables libres de ( existe x alpha ). Elija 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 un número contable de ( alpha ) y un número contable de (s ^ prime ).

Continúe esta construcción, construyendo iterativamente (A_ {n + 1} ) desde (A_n ). Sea (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 ) está cerrado bajo las funciones de ( mathfrak {B} ) (mediante las observaciones que siguen a la Definición 3.4.1 esto muestra que ( mathfrak {A} ) es una subestructura de ( mathfrak {B} )), y tenemos que demostrar que ( mathfrak {A} ) satisface los criterios establecidos en el Lema 3.4.7, por lo que sabremos que ( mathfrak {A} ) es una subestructura elemental de ( mathfrak {B} ).

Primero, para mostrar que (A ) está cerrado bajo las funciones de ( mathfrak {B} ), suponga que (a in A ) y (f ) es un símbolo de función unaria (el símbolo general caso es idéntico) y que (b = f ^ mathfrak {B} left (a right) ). Debemos demostrar que (b in A ). Arregle un (n ) tan grande que (a in A_n ), sea ( phi ) la fórmula ( left ( existe y right) y = f left (x right) ), y sea (s ) cualquier función de asignación en (A ) tal que (s left (x right) = a ). Sabemos que ( mathfrak {B} modelos left ( existe y right) y = f left (x right) left [s right] ), y sabemos que si ( mathfrak {B} modelos left (y = f left (x right) right) left [s left [y | d right] right] ), luego (d = b ). Entonces, en nuestra construcción de (A_ {n + 1} ) debemos haber usado (a_ {y = f left (x right), s} = b ), entonces (b in A_ { n + 1} ) y (b in A ), según sea necesario.

Para usar el Lema 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 ). Encuentre una eventual constante (s ^ prime: Vars rightarrow A ) tal que (s ) y (s ^ prime ) concuerden en todas las variables libres de ( alpha ). Por lo tanto, ( mathfrak {B} modelos existe x alpha left [s ^ prime right] ), y todos los valores de (s ^ prime ) son elementos de algunos (A_n ), ya que (s ^ prime ) toma solo un número finito de valores. Pero luego, mediante la construcción de (A_ {n + 1} ) tal que ( mathfrak {B} models alpha left [s left [x | a right] right] ), según sea necesario.

Así que hemos cumplido con las hipótesis del Lema 3.4.7 y, por tanto, ( mathfrak {A} ) es una subestructura elemental contable de ( mathfrak {B} ), según sea necesario.

Paja: Nos gustaría ver un poco 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 ( existe x alpha ) y cada (s: Vars rightarrow A ), y el punto era que (a _ { infty, s ^ ​​ prime} ) sería un testigo de la verdad en ( mathfrak {B} ) del enunciado existencial ( existe x alpha ). Así que hemos construido un función que, dada una fórmula existencial ( existe x alpha ) y una función de asignación, encuentra un valor para (x ) que hace que la fórmula ( alpha ) sea verdadera. Una función de este tipo se llama Función Skolem, y la construcción de (A ) en la demostración del Teorema descendente de Löwenheim-Skolem se puede resumir así: Sea (A_0 ) un subconjunto contable de (B ), y forme el cierre de (A_0 ) en el conjunto de todas las funciones de Skolem. Luego demuestre que este cierre es una subestructura elemental de ( mathfrak {B} ).

Ejemplo 3.4.9:

En el ejercicio 4 de la sección 2.8 vimos una indicación de que los axiomas de la teoría de conjuntos de Zermelo-Fraenkel (conocida como ZF) se pueden formalizar en lógica de primer orden. Aceptando eso como cierto (que es), sabemos que si los axiomas son consistentes tienen un modelo, y luego por el Teorema hacia abajo de Löwenheim-Skolem, debe haber un modelo contable para la teoría de conjuntos. Pero esto es interesante, ya que los siguientes son todos teoremas de ZF:

  • Hay un conjunto infinito contable.
  • Si existe un conjunto (a ), entonces existe la colección de subconjuntos de (a ).
  • Si (a ) es infinito numerable, entonces la colección de subconjuntos de (a ) es incontable. (Este es el teorema de Cantor).

Ahora, supongamos que ( mathfrak {A} ) es nuestro modelo contable de ZF, y supongamos que (a ) es un elemento de (A ) y es numerablemente 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! ¡Entonces (b ) debe ser tanto contable como incontable! Esto se llama (algo incorrectamente) la paradoja de Skolem, y el ejercicio 8 le pide que encuentre la solución a la paradoja.

Probablemente la forma de pensar sobre el teorema descendente de Löwenheim-Skolem 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 existe una garantía similar para los modelos grandes, y la hay.

Proposición 3.4.10.

Suponga que ( Sigma ) es un conjunto de ( mathcal {L} ) - fórmulas con un modelo infinito. Si ( kappa ) es un cardinal infinito, entonces hay un modelo de ( Sigma ) de cardinalidad mayor o igual que ( kappa ).

prueba

Ésta es una aplicación sencilla del Teorema de la compacidad. Expanda ( mathcal {L} ) para incluir ( kappa ) nuevos símbolos constantes (c_i ), y deje ( Gamma = Sigma cup {c_i neq c_j | i neq j } ). Entonces ( Gamma ) es finitamente satisfactorio, ya que podemos tomar nuestro modelo infinito dado de ( Sigma ) e interpretar (c_i ) en ese modelo de tal manera que (c_i neq c_j ) para cualquier conjunto finito de símbolos constantes. Según el Teorema de la compacidad, existe una estructura ( mathfrak {A} ) que es un modelo de ( Gamma ), y por lo tanto, ciertamente la cardinalidad de (A ) es mayor o igual que ( kappa). Si restringimos ( mathfrak {A} ) al idioma original, obtenemos un modelo de ( Sigma ) de la cardinalidad requerida.

corolario 3.4.11.

Si ( Sigma ) es un conjunto de fórmulas de un lenguaje contable con un modelo infinito, y si ( kappa ) es un cardinal infinito, entonces hay un modelo de ( Sigma ) de cardinalidad ( kappa).

prueba

Primero, use la Proposición 3.4.10 para obtener ( mathfrak {B} ), un modelo de ( Sigma ) de cardinalidad mayor o igual que ( kappa ). Luego, imite la demostración del Teorema descendente de Löwenheim-Skolem, 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 de ( Sigma ) de cardinalidad ( kappa ).

corolario 3.4.12

Si ( mathfrak {A} ) es una estructura ( mathcal {L} ) infinita, entonces hay No conjunto de fórmulas de primer orden que caracterizan ( mathfrak {A} ) hasta el isomorfismo.

prueba

Más precisamente, el corolario dice que no hay un conjunto de fórmulas ( Sigma ) tal que ( mathfrak {B} modelos Sigma ) si y solo si ( mathfrak {A} cong mathfrak { B}). Sabemos que hay modelos de ( Sigma ) de todas las cardinalidades, y sabemos que no hay biyecciones entre conjuntos de diferentes cardinalidades. Entonces debe haber muchos modelos de ( Sigma ) que no sean isomorfos a ( mathfrak {A} ).

Paja: Hay conjuntos de axiomas que caracterizan estructuras infinitas. Por ejemplo, los axiomas de segundo orden de la aritmética de 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 (n ) tal que (n in M ​​), entonces ( left ( forall n right ) left (n in M ​​ right) ).

Cualquier modelo de Aritmética de Peano es isomórfico a los números naturales, pero observe que usamos dos nociones (conjuntos de números y la relación de elemento) que no son parte de nuestra descripción de ( mathfrak {N} ). Al introducir conjuntos de números, hemos abandonado el mundo de la lógica de primer orden y hemos entrado en la lógica de segundo orden, y solo mediante el uso de la lógica de segundo orden podemos caracterizar ( mathfrak {N} ). Para una buena discusión de este tema, vea [Bell 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 del Teorema hacia abajo de Löwenheim-Skolem, en el sentido de que no garantizan que el modelo pequeño sea una subestructura elemental del modelo grande. Ese es el contenido del Teorema ascendente de Löwenheim-Skolem, cuya prueba se describe en los Ejercicios.

teorema 3.4.13: Teorema ascendente de löwenheim-Skolem

Si ( mathcal {L} ) es un lenguaje contable, ( mathfrak {A} ) es una estructura ( mathcal {L} ) infinita, 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 que ( kappa ).

Ejercicios

  1. Suponga que ( mathfrak {B} subseteq mathfrak {A} ), que ( phi ) tiene la forma ( left ( forall x right) psi ), donde ( psi ) no tiene cuantificadores, y eso ( mathfrak {A} models phi ). Demuestre que ( mathfrak {B} models phi ). La versión corta de este hecho es: "Las oraciones universales se conservan hacia abajo". Formular y probar el hecho correspondiente para oraciones existenciales.
  2. Justifica el Paja siguiente Definición 3.4.4.
  3. Muestre que si ( mathfrak {A} prec mathfrak {B} ) y ( mathfrak {C} prec mathfrak {B} ) y ( mathfrak {A} subseteq mathfrak {C } ), luego ( mathfrak {A} prec mathfrak {C} ).
  4. Supongamos que tenemos un cadena elemental, un conjunto de ( mathcal {L} ) - estructuras tales que
    [ mathfrak {A} _1 prec mathfrak {A} _2 prec mathfrak {A} _3 prec cdots ]
    y deje ( 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. Muestre que ( mathfrak {A} _i prec mathfrak {A} ) para cada (i ). [Sugerencia: Demostrar que ( mathfrak {A} _i subseteq mathfrak {A} ) es bastante fácil según la definición. Para obtener que ( mathfrak {A} ) es un elemental extensión, tienes que usar 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 probar una dirección. Puede que le resulte más fácil usar ( existe ) en lugar de ( forall ) en la parte del cuantificador del paso inductivo de la demostración.]
  5. Demuestre la Proposición 3.4.5.
  6. Muestre que si ( mathfrak {A} prec mathfrak {B} ) y si hay un elemento (b en B ) y una fórmula ( phi left (x right) ) tales que ( mathfrak {B} modelos 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] ), luego (b in A ). [Sugerencia: Esto es muy similar al ejemplo 3.4.6.]
  7. Suponga que ( mathfrak {B} = { mathbb {N}, +, cdot } ), y sea (A_0 = {2, 3 } ). Sea (F ) el conjunto de funciones de Skolem ( {f _ { alpha, s} } ) correspondientes a ( alpha ) 's de la forma ( left ( exist x right ) x = yz ). Encuentra el cierre de (A_0 ) debajo de (F ). [Sugerencia: No olvide que las funciones de asignación (s ) que debe considerar son funciones que se asignan a (A_0 ) al principio, luego a (A_1 ), y así sucesivamente. Probablemente desee escribir explícitamente (A_1 ), luego (A_2 ), etc. Aquí estamos usando la notación correspondiente a la demostración del Teorema 3.4.8.]
  8. Decir que un conjunto (a ) es contable significa que hay una función con dominio de los números naturales y codominio (a ) que es una biyección. Tenga en cuenta que esta es una declaración existencial, que dice que cierto tipo de función existe. 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 tanto contable como incontable. En particular, piensa en lo que significa que un enunciado existencial sea verdadero en una estructura ( mathfrak {A} ), en oposición a verdadero en el mundo real (lo que sea que ¡medio!).
  9. (Hacia la prueba del teorema ascendente de Löwenheim-Skolem) Si ( mathfrak {A} ) es una estructura ( mathcal {L} ) -, sea ( mathcal {L} left (A right) = mathcal {L} cup { bar {a} | a in A } ), donde cada ( bar {a} ) es un nuevo símbolo constante. Entonces, sea ( bar { mathfrak {A}} ) la estructura ( mathcal {L} left (A right) ) que tiene el mismo universo que ( mathfrak {A} ) y la misma interpretación de los símbolos de ( mathcal {L} ) como ( mathfrak {A} ), e interpretando cada ( bar {a} ) como (a ). Entonces definimos el diagrama completo de ( mathfrak {A} ) como
    [Th left ( bar { mathfrak {A}} right) = { sigma | sigma : text {es una} : mathcal {L} left (A right) text {-formula tal que} : bar { mathfrak {A}} models sigma }. ]
    Demuestre que si ( bar { mathfrak {B}} ) es cualquier 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: Sea (h: A rightarrow B ) dado por (h left (a right) = bar {a} ^ mathfrak {B} ). Sea (C ) el rango de (h ). Demuestre que (C ) está cerrado bajo (f ^ mathfrak {B} ) para cada (f ) en ( mathcal {L} ), y por lo tanto (C ) es el universo de ( mathfrak {C} ), una subestructura de ( mathfrak {B} ). Entonces demuestre que (h ) es un isomorfismo entre ( mathfrak {A} ) y ( mathfrak {C} ). Finalmente, demuestre que ( mathfrak {C} prec mathfrak {B} ).]
  10. Utilice el ejercicio 9 para demostrar el teorema ascendente de Löwenheim-Skolem encontrando un modelo ( bar { mathfrak {B}} ) del diagrama completo del modelo dado ( mathfrak {A} ) tal que la cardinalidad de ( bar {B} ) es mayor o igual que ( kappa ).
  11. Ahora podemos completar 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 ( mathfrak {R} ) no es más que (Th izquierda ( mathfrak {R} derecha) ). Explique cómo el ejercicio 9 muestra que hay una copia isomórfica de la línea real que vive dentro de la estructura ( mathfrak {A} ).

- Teoremas de Löwenheim-Skolem

Este capítulo proporciona una descripción general de los teoremas de Löwenheim-Skolem. Este capítulo ofrece una imagen de lo que se ha obtenido con respecto a los fenómenos de Löwenheim-Skolem. Este capítulo introduce alguna terminología básica, seguida de una descripción del resultado original de Löwenheim y Skolem junto con extensiones inmediatas a algunas otras lógicas. Este capítulo trata los teoremas de transferencia más sólidos para la lógica de primer orden y los lenguajes infinitarios. Son variantes del llamado teorema de Löwenheim-Skolem-Tarski. Luego se elabora el problema del espectro para la lógica de primer orden. El capítulo investiga transferencias especiales de “grande” a “pequeño” y trata de los principios de reflexión en la teoría de conjuntos. Se discute la propiedad del modelo finito, que proporciona una transferencia de "infinito" a "finito". El capítulo pregunta por la validez de los teoremas de transferencia para lógicas, que contienen operadores para fijar cardinalidades. La pregunta conduce a un tipo más general de teoremas de transferencia de primer orden, que involucran varias cardinalidades. Después de considerar varias lógicas con respecto a la validez de los teoremas de transferencia, se trata el tema de los números de Löwenheim y los números de Hanf como un medio para medir hasta qué punto son válidos los teoremas de transferencia. La presentación de los resultados va acompañada de información específica sobre la literatura.


1. Lenguajes y estructuras de primer orden

La teoría de modelos matemáticos conlleva una gran cantidad de notación, y HTML no es el mejor contenedor para ello. En lo que sigue, los objetos sintácticos (idiomas, teorías, oraciones) se escriben generalmente en letras romanas o griegas (por ejemplo, L, T y phi), y los objetos de teoría de conjuntos, como las estructuras y sus elementos, se escriben en cursiva (A, a). Dos excepciones son que las variables están en cursiva (X, y) y que las secuencias de elementos se escriben con letras romanas minúsculas (a, b).

Recordamos y refinamos algunas definiciones de las entradas sobre lógica clásica y teoría de modelos. A firma es un conjunto de constantes individuales, símbolos de predicado y símbolos de función, cada uno de los símbolos de predicado y símbolos de función tiene un aridad (por ejemplo, es binario si su aridad es 2). Cada firma K da lugar a un lenguaje de primer orden, mediante la construcción de fórmulas a partir de los símbolos de la firma junto con símbolos lógicos (incluido =) y puntuación.

Si K es una firma, entonces un estructura de la firma K, di A, consta de los siguientes elementos:

  1. Un conjunto llamado dominio de A y escrito domA) generalmente se asume que no está vacío
  2. para cada constante individual C en K, un elemento c A de domA)
  3. para cada símbolo de predicado PAG de aridad norte, un norte-relación P A en domA)
  4. para cada símbolo de función F de aridad norte, un norte-función F A de domA) dom (A).

La elementos de A son los elementos de dom (A). Asimismo el cardinalidad o energía de A es la cardinalidad de su dominio. Dado que podemos recuperar la firma K del lenguaje de primer orden L que genera, podemos y nos referiremos a las estructuras de la firma K como L-estructuras. Pensamos en C como nombre del elemento C A en la estructura A, y lo mismo con los demás símbolos.

Por ejemplo, el campo de los números reales forma una estructura. R cuyos elementos son los números reales, con la firma que consiste en la constante individual 0 para nombrar el número cero, un símbolo de función 1-aria y menos para menos, y dos símbolos de función 2-aria + y. por más y veces. A primera vista podemos agregar un símbolo para expresar 1 /X, ya que todas las funciones nombradas deben definirse en todo el dominio de la estructura, y no existe un número real como 1/0. Pero pensándolo bien, este no es un problema grave, ningún matemático competente pone la condición y lsquoX no es cero y rsquo antes de dividir por X, por lo que nunca importa cuál es el valor de 1/0, y podemos tomarlo sin causar daño como 42. Pero la mayoría de los teóricos de modelos se sienten incómodos con cualquier tipo de división por cero, por lo que se apegan a más, tiempos y menos.

Si L es el lenguaje de primer orden de la firma K, entonces la definición de verdad de la teoría del modelo de Tarski & rsquos nos dice cuándo una oración de L es verdadera en A, y cuando una asignación de elementos de A a variables satisface una fórmula de L en A. En lugar de hablar de asignaciones que satisfacen una fórmula, los teóricos del modelo a menudo hablan del conjunto de norte-tuplas de elementos de A es decir definido por una fórmula & phi (v1, & hellip,vnorte) la conexión es que un norte-tupla (a1, & hellip,anorte) está en el conjunto definido si y solo si la asignación que toma cada vI a aI satisface la fórmula.

Si & phi es una oración, escribimos

para significar que & phi es cierto en A, o en otras palabras, A es un modelo de & phi. Si & phi (v1, & hellip,vnorte) es una fórmula con variables libres como se muestra, escribimos

para significar que el norte-tupla a está en el conjunto definido por & phi. (La entrada sobre lógica clásica usa la notación & lsquoComo & # 8872 & phi & rsquo, donde s es cualquier asignación a todas las variables de L que asigna a cada variable vI gratis en & phi el I-th elemento en el norte-tupla a.)

Se dice que dos estructuras L que son modelos de exactamente las mismas oraciones de L son elementalmente equivalente. La equivalencia elemental es una relación de equivalencia en la clase de todas las estructuras L.El conjunto de todas las oraciones de L que son verdaderas en la estructura L A se llama el teoría completa de A, en símbolos Th (A). Una teoría que es Th (A) para alguna estructura A se ha dicho completo. (Según el teorema de completitud para la lógica de primer orden, para el cual ver la entrada sobre lógica clásica, una teoría es completa si y solo si es máxima sintácticamente consistente). A y B son elementalmente equivalentes si y solo si Th (A) = Th (B).

Para continuar con el ejemplo del campo R de números reales: a menudo no es del todo obvio si dos estructuras dadas son o no elementalmente equivalentes. Uno de los mayores logros de la prehistoria de la teoría de modelos fue la descripción de Tarski & rsquos en 1930 de Th (R) (que publicó en su totalidad solo después de la guerra, consulte su libro en la Bibliografía a continuación). Esta descripción implicaba, entre otras cosas, que las estructuras elementalmente equivalentes a R son exactamente los campos cerrados reales, una clase de campos que los algebristas ya conocían por derecho propio.

Cuando los matemáticos introducen una clase de estructuras, les gusta definir lo que cuentan como mapas básicos entre estas estructuras. Los mapas básicos entre estructuras de la misma firma K se denominan homomorfismos, definido como sigue. A homomorfismo de la estructura A a la estructura B es una función F de domA) dom (B) con la propiedad de que para cada fórmula atómica & phi (v1, & hellip,vnorte) y cualquier norte-tupla a = (a1, & hellip,anorte) de elementos de A,

donde b es (F(a1) y hellip,F(anorte)). Si tenemos & lsquo & hArr & rsquo en lugar de & lsquo & rArr & rsquo en la condición citada, decimos que F es un incrustación de A en B. Dado que el lenguaje incluye =, una incrustación de A en B es siempre uno a uno, aunque no necesita estar en el dominio de B. Si está activado, entonces el mapa inverso de dom (B) dom (A) es también un homomorfismo, y se dice que tanto la incrustación como su inverso son isomorfismos. Decimos que dos estructuras son isomorfo si hay un isomorfismo de uno a otro. El isomorfismo es una relación de equivalencia en la clase de todas las estructuras de una firma fija K. Si dos estructuras son isomorfas, entonces comparten todas las propiedades teóricas del modelo, en particular, son elementalmente equivalentes.

Si A y B son estructuras de la firma K con dom (A) un subconjunto de dom (B), y las interpretaciones en A de los smbolos en K son slo las restricciones de sus interpretaciones en B, entonces decimos que A es un infraestructura de B y por el contrario B es un extensión de A. Si ademas B tiene algunos elementos que no están en A, Nosotros decimos eso A es un subestructura adecuada de B y B es un extensión adecuada de A. Si B es una estructura y X es un subconjunto no vacío de dom (B), entonces hay una subestructura única más pequeña de B cuyo dominio contiene todos los X. Es conocido como el subestructura de B generada por X, y lo encontramos agregando primero a X todos los elementos c B donde C son constantes individuales de K, y luego se cierran bajo las funciones F B donde F son símbolos de función de K.

Por ejemplo, la subestructura del campo. R generado por el número 1 consta de 1, 0 (ya que es nombrado por la constante 0), 1 + 1, 1 + 1 + 1 etc., & minus1, & minus2 etc., en otras palabras, el anillo de números enteros. (No es necesario cerrar con la multiplicación también, ya que el conjunto de enteros ya está cerrado con la multiplicación). Si hubiéramos incluido un símbolo para 1 /X además, la subestructura generada por 1 habría sido el campo de los números racionales. Por tanto, la noción de subestructura es sensible a la elección de la firma.


B1.1 Lógica (2019-2020)

Dar un tratamiento matemático riguroso de las ideas fundamentales y los resultados de la lógica que sea adecuado para los matemáticos no especialistas y proporcionará una base sólida para estudios más avanzados. La cohesión se logra centrándose en los teoremas de completitud y la relación entre demostrabilidad y verdad. La consideración de algunas implicaciones del Teorema de la compacidad da una idea del desarrollo posterior de la teoría de modelos. Proporcionar un sistema deductivo concreto para el cálculo de predicados y demostrar el teorema de completitud, incluidas aplicaciones sencillas en la teoría básica de modelos.

Los estudiantes podrán usar el lenguaje formal del cálculo proposicional y de predicados y familiarizarse con sus sistemas deductivos y teoremas relacionados. Por ejemplo, conocerán y podrán utilizar los teoremas de solidez, integridad y compacidad de los sistemas deductivos para el cálculo de predicados.

La notación, significado y uso del cálculo proposicional y de predicados. El lenguaje formal del cálculo proposicional: funciones de verdad conjuntivas y disyuntivas de forma normal tautologías y consecuencia lógica. El lenguaje formal del cálculo de predicados: satisfacción, verdad, validez, consecuencia lógica.

Sistema deductivo para cálculo proposicional: demostraciones y teoremas, demostraciones a partir de hipótesis, el teorema de la solidez del teorema de la deducción. Conjuntos máximos consistentes de completitud de fórmulas prueba constructiva de completitud.

Declaración de Teoremas de Solidez y Completitud para un sistema deductivo para la derivación del cálculo de predicados del Teorema de Compacidad Aplicaciones simples del Teorema de Compacidad.

Un sistema deductivo para pruebas de cálculo de predicados y forma de prenex de teoremas. Teorema de la prueba de integridad. Existencia de modelos contables, el teorema de L & oumlwenheim-Skolem descendente.

  1. R. Cori y D. Lascar, Lógica matemática: un curso con ejercicios (Parte I) (Oxford University Press, 2001), secciones 1, 3, 4.
  2. A. G. Hamilton, Lógica para matemáticos (2da edición, Cambridge University Press, 1988), págs. 1-69, págs. 73-76 (para la declaración del Teorema de Completitud (Adecuación)), págs. 99-103 (para el Teorema de Compacidad).
  3. W. B. Enderton, Una introducción matemática a la lógica (Academic Press, 1972), págs. 101-144.
  4. D. Goldrei, Cálculo proposicional y de predicados: un modelo de argumentación (Springer, 2005).
  5. A. Prestel y C. N. Delzell, Lógica matemática y teoría de modelos (Springer, 2010).

Tenga en cuenta que las versiones de libros electrónicos de muchos libros en las listas de lectura se pueden encontrar en SOLO y ORLO.


Adámek, J., Rosický, J .: Categorías localmente presentables y accesibles. Número 189 en London Mathematical Society Lecture Notes. Prensa de la Universidad de Cambridge (1994)

Ahmed T.S .: Omitir tipos para extensiones algebraizables de lógica de primer orden. J. Appl. Lógicas no clásicas. 15(4), 465–489 (2005)

Ahmed T.S., Andréka H., Németi I .: Omitir tipos para fragmentos de variables finitas y representaciones completas de álgebras. J. Symb. Tronco. 73(1), 65–89 (2008)

Ahmed T.S., Samir B .: Un teorema de tipos omitidos para lógica de primer orden con símbolos de relación infinita. Matemáticas. Tronco. Q. 53(6), 564–570 (2007)

Astesiano E., Bidoit M., Kirchner H., Krieg-Brückner B., Mosses P.D., Sannella D., Tarlecki A .: CASL: the Common Algebraic Specification Language. Theor. Computación. Sci. 286(2), 153–196 (2002)

Barwise J .: Notas sobre forzamiento y fragmentos contables. Mimeografiado (1970)

Chang, C.C., Keisler, H.J .: Teoría de modelos. Holanda Septentrional, Amsterdam (1990)

Church A .: Una formulación de la teoría simple de tipos. J. Symb. Tronco., 5(2), 56–68 (1940)

Codescu, M .: La teoría del modelo de lógica de orden superior. Tesis de maestría, Şcoala Normală Superioară Bucureşti (2007)

Codescu M., Găină D .: Completitud Birkhoff en Instituciones. Logica Universalis 2(2), 277–309 (2008)

Cohen, P.J .: La hipótesis de la independencia del continuo. En: actas de la Academia Nacional de Ciencias de los Estados Unidos de América, 50(6): 1143-1148, diciembre de 1963

Cohen, P.J .: La hipótesis de la independencia del continuo, II. Actas de la Academia Nacional de Ciencias de los Estados Unidos de América, 51(1): 105–110, enero de 1964

Diaconescu R .: Lógica de restricción basada en categorías. Estructuras matemáticas en informática 10(3), 373–407 (2000)

Diaconescu R .: Ultraproductos independientes de la institución. Fundamenta Informaticæ 55(3-4):321–348 (2003)

Diaconescu R .: Una prueba independiente de la institución del teorema de interpolación de Craig. Studia Logica 77(1), 59–79 (2004)

Diaconescu R .: Diagramas elementales en instituciones. J. Log. Computación. 14(5), 651–674 (2004)

Diaconescu R .: Teoremas de Herbrand en instituciones arbitrarias. Inf. Proceso. Letón. 90, 29–37 (2004)

Diaconescu R .: Un estudio categórico sobre la finitud de las especificaciones. Inf. Proceso. Letón., 108(2), 75–80 (2008)

Diaconescu, R .: Teoría de modelos independientes de la institución. Estudios en lógica universal. Birkhäuser (2008)

Diaconescu, R., Futatsugi, K.L .: CafeOBJ Informe: El lenguaje, las técnicas de prueba y las metodologías para la especificación algebraica orientada a objetos, vol. 6 de la Serie AMAST en Computación. World Scientific (1998)

Diaconescu R., Futatsugi K .: Fundamentos lógicos de CafeOBJ. Theor. Computación. Sci., 285(2), 289–318 (2002)

Diaconescu, R., Futatsugi, K., Ogata, K .: CafeOBJ: Fundamentos lógicos y metodologías. Computadoras e inteligencia artificial 22(3) (2003)

Goguen J., Burstall R .: Instituciones: Teoría de modelos abstractos para la especificación y programación. J. Assoc. Computadora Mach 39(1), 95–146 (1992)

Goguen J.A., Diaconescu R .: An Oxford Survey of Order Sorted Algebra. Estructuras matemáticas en informática 4(3), 363–392 (1994)

Goguen J.A., Meseguer J .: Álgebra I ordenada por orden: Deducción ecológica para herencia múltiple, sobrecarga, excepciones y operaciones parciales. Theor. Computación. Sci. 105(2), 217–273 (1992)

Goguen J.A., Rosu G .: Morfismos institucionales. Asp formal. Computación. 13(3-5), 274–307 (2002)

Găină D., Petria M .: Completitud forzando. J. Log. Computación. 20(6), 1165–1186 (2010)

Găină D., Popescu A .: Una generalización independiente de la institución del teorema de la cadena elemental de Tarski. J. Logic. Computación. 16(6), 713–735 (2006)

Găină D., Popescu A .: Una prueba independiente de la institución del teorema de coherencia de Robinson. Studia Logica 85(1), 41–73 (2007)

Henkin L .: Integridad en la teoría de tipos. J. Symb. Tronco. 15(2), 81–91 (1950)

Henkin L .: Una generalización del concepto de consistencia ω. J. Symb. Tronco. 19(3), 183–196 (1954)

Keisler, H .: Forzar y teorema de tipos omitidos. En: Morley, M., (ed), estudios en teoría de modelos, estudios MAA en matemáticas, vol. 8, págs. 96-133 (1973)

Mac Lane, S .: Categorías para el matemático que trabaja. Springer, 2.a ed. (1998)

Meseguer, J .: Lógicas generales. En Logic Colloquium 87, págs. 275–329. Holanda Septentrional (1989)

Meseguer J., Goguen J.A .: El álgebra ordenada por orden resuelve los problemas de constructor-selector, representación múltiple y coerción. Inf. Computación. 103(1), 114–158 (1993)

Möller, B., Tarlecki, A., Wirsing, M .: Especificaciones algebraicas de álgebras de orden superior alcanzables. En: Sannella, D., Tarlecki, A. (eds.) ADT, Lecture notes in computer science, vol: 332 pp. 154-169. Springer (1987)

Mossakowski T .: Relacionar casl con otros lenguajes de especificación: el nivel institucional. Theor. Computación. Sci. 286(2), 367–475 (2002)

Orey S .: Sobre la consistencia ω y propiedades relacionadas. J. Symb. Tronco. 21(3), 246–252 (1956)

Petria, M .: Una versión institucional del teorema de integridad de Gödel. En: Mossakowski, T., Montanari, U., Haveraaen, M., (eds.), Calco Lecture Notes in Computer Science, vol. 4624 páginas 409–424. Springer (2007)

Petria M., Diaconescu R .: Resumen La definición de Beth en las instituciones. J. Symb. Lógica. 71(3), 1002–1028 (2006)

Robinson A .: Forzar en la teoría de modelos. Simposios Mathematica, 5, 69–82 (1971)

Tarlecki A .: Sobre la existencia de modelos libres en instituciones algebraicas abstractas. Theor. Computación. Sci. 37, 269–304 (1985)

Tarlecki, A .: Bits y piezas de la teoría de las instituciones. En Pitt, D., Abramsky, S., Poigné, A., Rydeheard, D., (eds.), Actas del taller de verano sobre teoría de categorías y programación de computadoras, Lecture notes in computer science, vol. 240, págs. 334–360. Springer (1986)

Tarlecki A .: Cuasi-variedades en instituciones algebraicas abstractas. J. Comput. Syst. Sci. 33(3), 333–360 (1986)

Tarlecki, A .: Moverse entre sistemas lógicos. En tendencias recientes en la especificación de tipos de datos, págs. 478–502. Springer (1998)


Libro de texto en línea de lógica básica e intermedia

Para facilitar la notación, comenzamos por introducir algunas abreviaturas.

Suponga que t es un término con variables entre u0 , & # 8230, un-1.

Podríamos escribir t (u0 , & # 8230, un-1 ) ot (u & # 773) para enfatizar esto.

Suponga que & phi es una fórmula con variables libres entre u0 , & # 8230, un-1.

Podríamos escribir & phi (u0 , & # 8230, un-1 ) o & phi (u & # 773) para enfatizar esto.

Además, si tenemos un modelo A y x0 , & # 8230, xn-1 & en | A |, entonces podríamos escribir

A veces, si estamos trabajando con un u & # 773 fijo, entonces podríamos abreviar esto más a solo

(Necesitamos tanto u & # 773 como x & # 773 para saber qué constante se sustituye por qué variable).

Con estas abreviaturas, podemos reescribir el resultado del ejercicio 3.5 de la siguiente manera.

Lema 4.1

Sea & pi: A & asymp B un isomorfismo entre estructuras.

Entonces, para cada fórmula & phi, si & phi tiene variables libres u0, & # 8230, un-1,

La forma habitual de expresar la conclusión del Lema 4.1 es decir que & pi es un incrustación elemental de A a B. Por tanto, todo isomorfismo es una incrustación elemental. Lo contrario es falso porque las incrustaciones elementales no necesitan ser sobreyecciones.

& secta 4.1 Abajo L & oumlwenheim-Skolem

Ya hemos visto dos formas en que las estructuras pueden estar relacionadas. Al final de la demostración del teorema 3.14 de la existencia del modelo, tomamos la reducción de una estructura en un lenguaje expandido para obtener una estructura en el lenguaje original. En los ejercicios del Capítulo 3, definimos el isomorfismo entre estructuras y vimos varios casos y consecuencias. Aquí hay otra forma de comparar estructuras.

  • | A | & subseteq | B |
  • c A = c B para cada símbolo constante c
  • F A = ​​F B & # x21BE | A | n para cada símbolo de función n-aria F
  • R A = R B & cap | A | n para cada símbolo de función n-aria R

(No hay riesgo de confundir esto con "A es un subconjunto de B" porque se supone que A y B son estructuras).

c B & in | A | para cada símbolo constante c

F B (x & # 773) y en | A | para cada símbolo de función n-aria F y cada x & # 773 & in | A | norte

En particular, no todos los subconjuntos de | B | es el universo de una subestructura de B.

Lema 4.2

Sea B una estructura infinita en un lenguaje contable.

Sea X un subconjunto contable de | B |.

Entonces existe una subestructura contable A de B tal que X & subseteq | A |.

Prueba de Lema 4.2

Definir una secuencia creciente de conjuntos

Por inducción en i & in & omega, vemos que ZI es un subconjunto contable de | B |.

Entonces Z es un subconjunto contable de B.

Y, c B & en Z0 & subseteq Z para cada símbolo constante c.

Además, para cada símbolo de función n-aria F y cada x & # 773 & en Z n, existe i & in & omega tal que x & # 773 & in ZI n y F B (x & # 773) & en Zyo + 1 & subseteq Z.

Por lo tanto, F B & # x21BE Z n es una función n-aria en Z.

Así obtenemos una subestructura contable A de B estableciendo

c A = c B para cada símbolo constante

F A = ​​F B & # x21BE Z n para cada símbolo de función n-aria F

R A = R B & cap Z n para cada símbolo de función n-aria R

Lema 4.3

Sea & phi una fórmula sin cuantificadores.

Digamos que u & # 773 es una n-tupla de variables libres de & phi.

Bosquejo del Lema 4.3

Primero afirmamos que para cada término t (u & # 773) con n variables libres, si x & # 773 & in | A | n, luego t (u & # 773 / x & # 773) A = t (u & # 773 / x & # 773) B.

La prueba de la afirmación es una inducción fácil utilizando el supuesto de que A es una subestructura de B.

Usando esta suposición nuevamente, vemos que el Lema 4.3 es válido para fórmulas atómicas.

Ahora completamos la demostración del Lema 4.3 por inducción.

Los casos de conjunción, disyunción, condicional y bicondicional utilizan la hipótesis de inducción y son triviales.

No existe un caso de cuantificador.

En general, no podemos esperar obtener mejores resultados que el Lema 4.3. Por ejemplo, considere las estructuras

A = (& # x211A, 0, 1, +, & veces, A, d A, F A, G A, R A)

B = (& # x211D, 0, 1, +, & veces, B, d B, F B, G B, R B)

Entonces A es una subestructura de B.

Sin embargo, debido a que la raíz cuadrada de 2 es irracional,

Pero hay situaciones especiales en las que podemos hacerlo mejor que el Lema 4.3.

Decimos que A es un elemental subestructura de B y escriba A & # x227C B iff

para cada fórmula & phi con n variables libres u & # 773 y cada x & # 773 & in | A | n,

Prueba de Tarski-Vaught 4.4

Sea A una subestructura de B.

Suponga que para cada fórmula & psi con variables libres u & # 773 yv, y cada x & # 773 de | A |,

Entonces A es una subestructura elemental de B.

Prueba del teorema 4.4

El lema 4.3 dice que (*) es válido para & phi, que son libres de cuantificadores.

La hipótesis de inducción implica fácilmente que (*) se cumple para & phi, que son negaciones, conjunciones, disyunciones, condicionales o bicondicionales.

Ahora considere el caso en el que & phi es & exist v & psi (u & # 773, v).

Primero suponga que B & # 8872 & phi (u & # 773 / x & # 773) donde x & # 773 es de | A |.

Por el supuesto del teorema 4.4, existe y & en | A | tal que B & # 8872 & psi (u & # 773 / x & # 773, v / y).

Según la hipótesis de inducción, A & # 8872 & psi (u & # 773 / x & # 773, v / y).

Ahora suponga que A & # 8872 & phi (u & # 773 / x & # 773).

Entonces existe y & en | A | tal que A & # 8872 & psi (u & # 773 / x & # 773, y).

Según la hipótesis de inducción, B & # 8872 & psi (u & # 773 / x & # 773, y).

El caso final en el que & phi es & forall v & psi (u & # 773, v) se sigue de lo que ya hemos probado.

Teorema 4.5 de L & oumlwenheim-Skolem descendente

Sea B una estructura en un lenguaje contable.

Sea X un subconjunto contable de | B |.

Entonces existe una subestructura elemental contable A de B tal que X & subseteq | A |.

Prueba del teorema 4.5

Podemos suponer que B es infinito.

Para cada fórmula & phi (u & # 773, v) con n + 1 variables libres, elija una función f&fi : | B | n & rarr | B | así que eso,

(Dado que | B | no está vacío, podemos dar f&fi (x & # 773) algún valor predeterminado de lo contrario).

Expandir el lenguaje para incluir nuevos símbolos de función n-aria F&fi.

Expanda B a una estructura B * que interpreta F&fi como f&fi.

Según el Lema 4.2, B * tiene una subestructura contable A * tal que X & subseteq | A * |.

Sea A la reducción de A * al lenguaje de B.

Claramente, A es una subestructura de B.

También está claro que A pasa la prueba de Tarski-Vaught por ser una subestructura elemental de B.

& secta 4.2 hacia arriba L & oumlwenheim-Skolem

Como de costumbre, dejamos cX ser un nuevo símbolo constante para cada x & in | A |.

Expandir A a una estructura D = (A, x)x & in | A | que interpreta cX por x.

En otras palabras, D es la expansión de A con cX D = x para cada x & en | A |.

Por el diagrama elemental de A nos referimos a la teoría Diagrama (A) = <& phi & mid D & # 8872 & phi>.

Obviamente, D & # 8872 Diagrama (A).

En el lenguaje expandido, el Diagrama (A) es una teoría completa y cerrada por deducción.

Lema 4.6

Sea A una estructura y D = (A, x)x & in | A |.

Suponga que E es un modelo del diagrama (A).

Sea B la reducción de E al lenguaje de A.

Entonces el mapa & pi: x & rarr cX E es un isomorfismo de A a una subestructura elemental A * de B.

Prueba de Lema 4.6

Sea d un símbolo constante en el lenguaje expandido.

Prueba de reclamo A

Entonces la oración d & approx cX pertenece al diagrama (A).

Entonces d E = cX E = & pi (x) = & pi (d D).

Sea F una función n-aria arbitraria y x & # 773 & in | A | n.

Podemos definir una subestructura D * de E estableciendo:

c D * = c E para cada símbolo constante c en el lenguaje expandido.

F D * = F D * & # x21BE | corrió (& pi) | n para cada símbolo de función n-aria F.

R D * = R D * & cap | corrió (& pi) | n para cada símbolo de relación n-ario R.

Inmediato de las Reclamaciones A y B.

Sea x, y & in | A | tal que x & ne y.

Entonces la oración cX & aproximadamente & # x0338 cy pertenece al diagrama (A).

Sea R una función n-aria arbitraria y x & # 773 & in | A | n.

Similar a las pruebas anteriores.

Sea A * la reducción de D * al lenguaje de A.

& pi es una biyección de | A | = | D | a | A * | = | A * | por Claim D.

& pi conserva constantes, funciones y relaciones mediante las reivindicaciones A, B y E.

Sea & phi (u & # 773) una fórmula en el lenguaje de A.

En particular, & pi es una incrustación elemental de A a B.

La condición 1 es una abreviatura de la condición 2.

La condición 5 es una abreviatura de la condición 4.

La condición 2 se cumple si la oración & phi (u0 / CX0 , & # 8230, un-1 / CXn-1 ) pertenece al diagrama (A).

Lo mismo ocurre con la Condición 3, por lo que es equivalente a la Condición 2.

El significado de la cuarta condición necesita cierta elaboración.

Imagina que tenemos solo una x en lugar de una n-tupla x & # 773.

que se interpreta como & pi (x) en (E, & pi (x)).

En otras palabras, c& pi (x) (E, & pi (x)) = & pi (x)

Por el lema de sustitución 3.2, concluimos que (E, & pi (x)) & # 8872 & phi (u / cX ) y harr y phi (u / c& pi (x) ) .

Tenga en cuenta que & phi (u / cX ) es una oración en el idioma de E.

También eso & phi (u / c& pi (x) ) es una oración en el lenguaje de (B, & pi (x)).

Y tanto E como (B, & pi (x)) son reducciones de (E, & pi (x)).

Esto muestra que las condiciones 3 y 4 son equivalentes cuando n = 1.

Para n> 1, realice los cambios obvios.

Sea & phi (u & # 773) una fórmula en el lenguaje de A *, que es el lenguaje de A.

iff (según la afirmación F y el lema 4.1)

Vale la pena señalar que, en la demostración del Lema 4.6, podríamos haber probado la Reclamación G primero, luego la usamos para probar las Reclamaciones A, B, D y E considerando las cuatro fórmulas:

Lema 4.7

Cada estructura infinita tiene una extensión elemental adecuada.

Prueba de Lema 4.7

Afirmamos que & Sigma tiene modelo.

Según el Teorema de la compacidad 3.16, basta con mostrar que cada subteoría finita de & Sigma tiene un modelo.

Desde | A | es infinito, existe y & en | A | tal que y & ne xI para todo i * & # x227C B donde B es la reducción de E al lenguaje de A y & pi: x & map cX E.

Como E es un modelo de & Sigma, tenemos que d E & en T.

En particular, T no está vacío.

Podemos "reemplazar" cada y & en T con una x distinta que no pertenece a | A |.

Más precisamente, hay un conjunto S que es disjunto de | A | junto con una biyección f: S & rarr T.

En otras palabras, & sigma (x) = & pi (x) si x & in | A | y & sigma (x) = f (x) si x & en S.

Entonces & sigma: | A | & cup S & rarr | B | es una biyección y & sigma & # x21BE | A | = & pi.

A continuación, definimos una estructura B 'tal que & sigma: B' & asymp B.

¡Solo hay una forma obvia de hacer esto y funciona!

Considere cualquier x & # 773 & in | A | ny fórmula & phi con n variables libres.

La equivalencia entre la primera y la última línea del cálculo anterior implica directamente que A es una subestructura elemental de B '.

Hacia arriba L & oumlwenheim-Skolem 4.8

Cada estructura infinita tiene una extensión elemental incontable.

Prueba del teorema 4.8

Entonces, cada subconjunto finito de & Sigma tiene un modelo.

Para ver esto, considere cualquier x & # 773 & in | A | my nuevas constantes d0 , & # 8230, dn-1.

Sea B la expansión de (A, x & # 773) que interpreta dj como yj para todo j A como

donde k es el tamaño de Snorte.

Lista Tnorte en orden creciente de acuerdo con R B como

Dado que fnorte es un isomorfismo, debe ser que yI = fnorte ( XI ) para todo i A xI por todo lo que porI por todo yo A anorte para todo i B b para todo i A anorte R A xj para algunos i B b R B yj.

Elija cualquiera de tales by haga fn + 1 ( anorte ) = b.

Para esto, enumeramos Snorte & taza norte > en orden creciente según R A como

y Tnorte & taza en orden creciente de acuerdo con R B como

Caso 1. Bnorte R B y * I para todo i A x * I para todo i -1 (bnorte ) = a.

Caso 2. y * I R B bnorte por todo yo * I R A a para todo i -1 (bnorte ) = a.

Caso 3. y * I R B bnorte R B y * j para algunos yo * I R A a R A x * j.

Elija cualquiera de esos y haga fn + 1 -1 (bnorte ) = a.

Para terminar la construcción recursiva, ponga

Ya hemos determinado los valores de fn + 1 en estos conjuntos de una manera que preserva el orden. Y definimos fn + 1 extender fnorte.

Ahora terminamos la demostración del teorema.

Claramente, | A | es la unión de los conjuntos Snorte para n -1 (bnorte ) y k = max (m, n), entonces

Para ver que & pi preserva el orden, tenga en cuenta que si k = max (m, n), entonces

Una teoría y Sigma es contablemente categórico si todos los pares de modelos contables de & Sigma son isomorfos.

DLO es contablemente categórico según el teorema 4.9.

Esto no se extiende a incontables modelos de DLO.

Por ejemplo, aunque hay una biyección entre & # x211D y , las estructuras (& # x211D, * de A y B * de B.

Según el teorema 4.9, A * y B * son isomorfos.

Según el Lema 4.1, A * y B * satisfacen exactamente las mismas oraciones, lo cual es una contradicción.

Teorema 4.11

Sea & phi una fórmula cuyas variables libres se encuentran entre u & # 773 = (u0 , & # 8230, un-1 ).

Entonces existe una fórmula y psi sin cuantificador tal que

Prueba del teorema 4.11

Para x & # 773 & in | A | n, defina type (x & # 773) como el conjunto de fórmulas & psi tal que

  • & psi es atómico o negación de atómico,
  • las variables libres de & psi están entre u & # 773 y
  • A & # 8872 & psi (u & # 773 / x & # 773).

Entonces el tipo (x & # 773) es finito para cada x & # 773 & in | A | n.

La dirección de avance es obvia. La dirección inversa usa el Hecho A, parte 3.

El teorema 4.10 y el teorema de completitud 3.15 implican que cada oración satisfecha por A es satisfecha por cada modelo de DLO y, por lo tanto, es deducible de DLO.

Se dice que una teoría admite eliminación del cuantificador si cada fórmula es demostrablemente equivalente a una fórmula libre de cuantificadores.

Por tanto, DLO admite la eliminación del cuantificador por el teorema 4.11.

Propiedad de límite superior mínimo

Al comienzo de esta sección, dijimos que & # x211A es contable mientras que & # x211D es incontable, por lo que no hay biyección entre ellos.

Otra razón por la que (& # x211A, 2 2 in & # x211D

Considere un orden lineal arbitrario A.

Si S & subseteq | A | y y & en | A |, entonces y es una límite superior para S en A sif x R A y o x = y para todo x & en | A |.

y es el mínimo límite superior para S sif y es un límite superior para S y y R A z o y = z para cada límite superior z para S.

A tiene el propiedad del límite superior mínimo iff para cada S & subseteq no vacío | A |, si S tiene un límite superior, entonces S tiene un límite superior mínimo.

Es un hecho básico sobre (& # x211D, B y R B z.

Suponga que B tiene la propiedad del límite superior mínimo.

Sea & pi un isomorfismo de A a (& # x211A, B y>)

donde se toma el límite superior mínimo (& # x211D, A.

Además, estamos escribiendo cX R d en lugar de R (cX , D ).

Como en la demostración del Lema 4.7, encontramos E & # 8872 & Sigma y sea B el reducido de E al lenguaje de A.

Además, definimos & pi: x & map cX E y encuentre A * & # x227C B tal que & pi: A & asymp A *.

Tenemos eso para cada fórmula & phi (u & # 773) en el idioma de A,

Dado que A * es isomorfo a A, también consideramos A * estándar.

Aunque B satisface todas las mismas oraciones que A *, no es isomórfico a A, por lo que pensamos en B como no estándar.

Para comenzar a ver cuán diferente es B de A, recuerde que B tiene un miembro d E que es mayor que todos los miembros de A *.

Defina Finito (B) como el conjunto de y & en B tal que existen x, z & en A * con x B y B z.

Además, defina Infinito (B) = | B | - Finito (B).

Entonces d E & en Infinito (B) porque E & # 8872 & Sigma.

Abusemos de la notación asumiendo que 0 y 1 son símbolos constantes que A interpreta como los números cero y uno respectivamente.

Entonces 0 A * = 0 B = & pi (0 A) y 1 A * = 1 B = & pi (1 A).

Positivo (A *) y subconjunto Positivo (B) pero d E & en Positivo (B) - Positivo (A *).

Abusa más de la notación asumiendo que A tiene símbolos de función binaria +, -, & veces y & divide que A interpreta como suma, resta, multiplicación y división. Además, A tiene un símbolo de funciones unarias escrito usando la notación extraña | & sdot | que A interpreta como valor absoluto.

(Hacemos una convención razonable sobre el valor de x & dividimos A 0 A para que & dividir A sea una función binaria total).

Ahora A satisface las versiones de primer orden de las oraciones "si 1 * y B también.

En particular, vemos que si dejamos

Para & delta & in | B |, decimos que & delta es un infinitesimal iff 0 B B | & delta | B B x para cada x & en Positivo (A *).

(Aquí | & delta | B es el valor absoluto de & delta calculado en B.)

Arriba vimos que & epsilon es un infinitesimal positivo de B porque es positivo pero menor que todos los miembros positivos de | A * |.

De hecho, mostramos que el recíproco de cualquier miembro infinito positivo de B es un miembro infinitesimal positivo de B.

Es posible que haya escuchado o visto la palabra "infinitesimal" utilizada en su curso de cálculo, ¡pero el maestro o el libro de texto casi con seguridad no justificaron su uso con lógica! De hecho, Gottfried Wilhelm Leibniz introdujo los infinitesimales con una especie de receta de libro de cocina sobre cómo usarlos en los cálculos. Isaac Newton descubrió un cálculo similar casi al mismo tiempo. Sus métodos se utilizaron para hacer predicciones correctas sobre física y astronomía, pero fueron muy controvertidos. Después de todo, ¡no hay números reales mayores que cero sino menores que todo número real positivo! Aproximadamente cuatrocientos años después, Abraham Robinson descubrió esta forma de pensar acerca de los infinitesimales como números reales no estándar y la usó para explicar por qué los cálculos que involucran infinitesimales pueden usarse para hacer afirmaciones precisas sobre números reales. Todo se reduce a & pi: A & asymp A * & # x227C B.


La prueba de Vaught

La prueba de Vaught es un lema importante para el teorema descendente de Lowenheim-Skolem. Primero debemos dar la definición de subestructura y subestructura elemental.

Definición

Definición

Dejemos y seamos dos L-estructuras. Entonces, es un elemental infraestructura de, y escribimos, si y para cada fórmula, tenemos si .

Ahora estamos listos para declarar y probar la Prueba de Vaught.

Lema (prueba de Vaught)

Dejemos y seamos dos L-estructuras tales que. Entonces, es una subestructura elemental de si para todas las fórmulas, si, dónde, entonces hay tal que.

Prueba

Primero suponemos eso. Entonces, implica que, por la definición de subestructuras elementales. Entonces, existe tal que. Luego, usando de nuevo la definición, tenemos eso.

Por el contrario, la demostración pasa por inducción sobre la complejidad de. Esto es cierto para las fórmulas libres de cuantificadores, ya que en este caso, tenemos que implica si . Esto se puede demostrar mediante la inducción de la complejidad de la fórmula.

Ahora suponga que el resultado es válido para y. Entonces, es fácil verificar que el teorema es válido para y.

Dejar . Si, entonces existe tal que. Según la hipótesis de inducción, esto implica que existe tal que. Por lo tanto, .

Por el contrario, si, entonces, utilizando el supuesto, existe tal que. Entonces, existe tal que. Por lo tanto, . Esto completa la prueba.


Aproximaciones contables y teoremas de Löwenheim-Skolem



Este sitio utiliza cookies y Google Analytics (consulte nuestros términos y condiciones para obtener detalles sobre las implicaciones de privacidad).

El uso de este sitio está sujeto a términos y condiciones.
Todos los derechos reservados por The PhilPapers Foundation

Página generada el 4 de julio 16:12:10 2021 en philpapers-web-75c4f97565-gk4zj Información de depuración

estadísticas de caché: hit = 7596, miss = 7749, save =
manipulador automático: 580 ms
componente llamado: 566 ms
entrada: 565 ms
entradas_imilares: 270 ms
entry_basics: 102 ms
encabezado de entrada: 90 ms
menú: 88 ms
citas-referencias: 82 ms
citas-citas: 55 ms
entry_stats: 16 ms
get_entry: 9 ms
prepCit: 9 ms
enlaces de entrada: 8 ms
entrada-gatos: 8 ms
lado de entrada: 4 ms
capítulos_de_entrada: 2 ms
guardar objeto de caché: 2 ms
writeLog: 1 ms
recuperar objeto de caché: 1 ms
entry_stats_query: 1 ms
procesador de inicio: 0 ms
configuración: 0 ms
autenticación: 0 ms
botones de entrada: 0 ms
stat_db: 0 ms


3.4: Subestructuras y teoremas de Löwenheim-Skolem - Matemáticas

Notas de clase para un curso de introducción (sub) de posgrado

  • Prefacio
  • Preliminares y notación
    • Estructuras
    • Tuplas
    • Condiciones
    • Subestructuras
    • Fórmulas
    • Aún más notación
    • Consecuencias lógicas
    • Equivalencia elemental
    • Incrustaciones e isomorfismos
    • Estructuras de cociente
    • Lo completo
    • La prueba de Tarski-Vaught
    • Hacia abajo Löwenheim-Skolem
    • Cadenas elementales
    • Filtros y ultrafiltros
    • Productos directos
    • Teorema de Łoś
    • Compacidad a través de la sintaxis
    • Compacidad a través de ultraproductos
    • Hacia arriba Löwenheim-Skolem
    • Axiomatizabilidad finita
    • Semilattices y filtros
    • Rejillas distributivas y filtros primarios
    • Tipos como filtros
    • Morfismos
    • Órdenes lineales densos
    • Gráficos aleatorios
    • notas y referencias
    • Modelos ricos.
    • La teoría de modelos ricos y eliminación de cuantificadores
    • Nociones más débiles de universalidad y homogeneidad
    • La propiedad de la fusión
    • Grupos abelianos
    • Grupos abelianos sin torsión
    • Grupos abelianos divisibles
    • Anillos conmutativos
    • Dominios integrales
    • Campos algebraicamente cerrados
    • Nullstellensatz de Hilbert
    • Estructuras saturadas
    • Estructuras homogéneas
    • El modelo de monstruo
    • Lema de Lyndon-Robinson
    • Eliminación del cuantificador por ida y vuelta
    • Completitud del modelo
    • Elementos algebraicos y definibles
    • Teorías fuertemente mínimas
    • Independencia y dimensión
    • El teorema de los tipos omitidos
    • Modelos primarios y atómicos
    • Categoricidad contable
    • Pequeñas teorías
    • Una versión de juguete de un teorema de Zil'ber.
    • notas y referencias
    • Estructuras de muchos ordenamientos
    • La eq-expansión
    • El cierre definible en la expansión eq
    • El cierre algebraico en la expansión eq
    • Eliminación de imaginarios
    • Imaginarios: la verdadera historia
    • Eliminación uniforme de imaginarios
    • Conjuntos y tipos invariantes
    • Invarianza desde una perspectiva dual
    • Herederos y coherederos
    • Secuencias de Morley e indiscernibles
    • Teorema de Ramsey a partir de secuencias coherentes
    • El teorema de Ehrenfeucht-Mostowski
    • Órbitas idempotentes en semigrupos
    • Teorema de Hindman
    • El teorema de Hales-Jewett
    • notas y referencias
    • Expansiones
    • Tipos fuertes de Lascar
    • El gráfico de Lascar y el teorema de Newelski
    • Tipos de Kim-Pillay
    • notas y referencias
    • Conjuntos aproximados
    • Escaleras y definibilidad
    • Teorías estables
    • Estabilidad y número de tipos.
    • Dimensión Vapnik-Chervonenkis
    • Definiciones honestas

    & # 8220¿Por qué la compacidad? & # 8221

    Notes from the Margin, la publicación semestral de CMS Studc que presenta la escritura de los estudiantes para una audiencia matemática general, ha proporcionado durante varios años una plataforma para temas que van desde el análisis de Fourier de orden superior hasta las entrevistas de trabajo en el puesto de titular. Nos complace presentar esta primera publicación en el blog Notes from the Margin, que complementará, pero no reemplazará, la publicación impresa semestral. Invitamos a enviar presentaciones durante todo el año a [email protected]

    & # 8220¿Por qué la compacidad? & # 8221

    Todd Schmid

    Con consecuencias como el Teorema ascendente de Löwenheim-Skolem, el Teorema de la compacidad es uno de los resultados más fundamentales en el estudio de la lógica de primer orden. Es común ver solo una prueba sintáctica de estilo Henkin o una prueba de ultraproducto que se coloca en el yunque de compacidad de primer orden. Por muy esclarecedoras que sean estas demostraciones, ninguna de ellas ilustra una imagen topológica de lo que representa el teorema. Como se puede suponer, esta imagen es donde el teorema ganó su nombre.

    Algunas aclaraciones antes de comenzar: definimos un /> & # 8211teoría ser un conjunto de oraciones lógicas de primer orden escritas en el lenguaje /> que se cierra bajo consecuencia lógica. Por ejemplo, la unicidad de la inversa de la teoría de grupos

    es una oración en el -teoría de grupos, porque se sigue de los axiomas de grupo. Un -teoría se llama consistente Si no pertenece al Cuándo pertenece a . Tenga en cuenta que he optado por no hacer distinciones entre dos oraciones que son lógicamente equivalentes, y que & # 8220iff & # 8221 debería leer & # 8220if y solo si & # 8221

    Teorema de compacidad. Arreglar un lenguaje de símbolos , y deja frijol -teoría. Luego es consistente si cada subconjunto finito de es consistente.

    Considerar el teorema de la compacidad es una afirmación acerca de -teorías, debería parecer sensato topologizar esta colección. Resulta que hay una forma natural de hacer esto, pero el hecho es el siguiente: el conjunto de todos los -¡Teorías es innecesariamente complicadas para nuestros propósitos! Todo lo que necesitamos para codificar en nuestros conjuntos abiertos son qué subconjuntos finitos pertenecen a un -teoría. Basta con centrar nuestra atención en una colección de mejor comportamiento -teorías.

    Definición. Un -teoría es completo si por alguna -frase , cualquiera o .

    En otras palabras, las teorías completas deciden sobre el valor de verdad de cada oración. Para motivar la atención que prestamos a esta clase especial de teorías, uno debe verificar por sí mismo las siguientes propiedades de las teorías completas, omitiendo el contenido entre paréntesis, ya sea por completo o en absoluto:

    (1) Cada (consistente) /> - teoría está contenida en alguna /> ​​- teoría completa (y consistente),

    (2) cualquier intersección de (consistente) /> - teorías es también una (consistente) /> - teoría, y

    (3) una teoría /> - está determinada precisamente por el conjunto de teorías /> - completas que la contienen.

    En particular, (3) es válido para oraciones individuales.

    Denotaré la colección de completos y consistentes -teorías con . Definimos una topología en de la siguiente manera: Para cada -frase , dejar denotar la colección de -teorías que contienen . Luego

    es una base para una topología llamada Topología de piedra activada (llamado así por el matemático M. H. Stone). Para ver que esto es cierto, observe que , ese , y eso . El teorema que sigue es exactamente la conexión entre compacidad topológica y lógica.

    Lema. Un subconjunto cubre si es inconsistente.

    Teorema. es compacto si se cumple el Teorema de la compacidad.

    Prueba. Suponga que se cumple el teorema de la compacidad, y sea ser una colección de Que cubre . Cada elemento de es de la forma , para que podamos formar un conjunto fuera de -oraciones . Por el lema, es un conjunto inconsistente de oraciones, por lo que el teorema de compacidad nos dice que hay un subconjunto finito de que es inconsistente. Nos quedamos con un subconjunto finito de Que cubre . fue elegido arbitrariamente, por lo que debe ser compacto.

    Suponer que es compacto, y deja frijol -teoría. Si es inconsistente, entonces el lema nos dice es una tapa abierta de . es compacto, por lo que un subconjunto finito cubre . La colección es un subconjunto finito de que es inconsistente. Por otro lado, si tiene un subconjunto finito inconsistente , luego es inconsistente y no hay nada que mostrar.

    Lo que me sorprende de la ilustración anterior es que se acerca a la coherencia en la lógica de primer orden desde una perspectiva puramente topológica. Se pueden encontrar más investigaciones en esta dirección en [2] y [3], y una prueba de que es compacto se puede encontrar en algún lugar en [1].

    Bibliografía.

    [1] Un punto de vista topológico de la lógica y el teorema de la compacidad (2016). T Schmid. Enlace.

    [2] Ultrafiltros, ultraproductos y el teorema de la compacidad (2009). Un Caicedo. Enlace.

    [3] Notas sobre los ultrafiltros. Un Kruckman. Enlace.

    Todd Schmid es un estudiante de la Universidad de Victoria. Le gustan los largos paseos por la playa, la superposición de la geometría y la lógica y las extrañas películas escandinavas. Entre sus citas favoritas se encuentra esta de César Vallejo: & # 8220 Amados sean los que se sienten. & # 8221


    Ver el vídeo: Resistencia de Materiales - 3x04 - Teorema de Castigliano para desplazamientos de celosías (Agosto 2022).