Teorema de Löwenheim-Skolem - Löwenheim–Skolem theorem

En lógica matemática , el teorema de Löwenheim-Skolem es un teorema sobre la existencia y cardinalidad de modelos , llamado así por Leopold Löwenheim y Thoralf Skolem .

La formulación precisa se da a continuación. Implica que si una teoría contable de primer orden tiene un modelo infinito , entonces para cada número cardinal infinito κ tiene un modelo de tamaño κ , y que ninguna teoría de primer orden con un modelo infinito puede tener un modelo único hasta el isomorfismo . Como consecuencia, las teorías de primer orden son incapaces de controlar la cardinalidad de sus modelos infinitos.

El teorema (descendente) de Löwenheim-Skolem es una de las dos propiedades clave, junto con el teorema de la compacidad , que se utilizan en el teorema de Lindström para caracterizar la lógica de primer orden . En general, el teorema de Löwenheim-Skolem no se sostiene en lógicas más fuertes como la lógica de segundo orden .

Teorema

En su forma general, el Teorema de Löwenheim-Skolem establece que para cada firma σ , cada σ infinita - estructura M y cada número cardinal infinito κ ≥ | σ | , hay una estructura σ N tal que | N | = κ y tal que

• si κ <| M | entonces N es una subestructura elemental de M ;
• si κ > | M | entonces N es una extensión elemental de M .

El teorema a menudo se divide en dos partes correspondientes a los dos casos anteriores. La parte del teorema que afirma que una estructura tiene subestructuras elementales de todas las cardinalidades infinitas más pequeñas se conoce como el teorema descendente de Löwenheim-Skolem . La parte del teorema que afirma que una estructura tiene extensiones elementales de todas las cardinalidades mayores se conoce como el teorema ascendente de Löwenheim-Skolem .

Discusión

A continuación, elaboramos el concepto general de firmas y estructuras.

Conceptos

Firmas

Una firma consta de un conjunto de símbolos de función S _func , un conjunto de símbolos de relación S _rel y una función que representa la aridad de los símbolos de función y relación. (Un símbolo de función nula se llama símbolo constante.) En el contexto de la lógica de primer orden, una firma a veces se llama lenguaje. Se llama contable si el conjunto de símbolos de función y relación que contiene es contable y, en general, la cardinalidad de una firma es la cardinalidad del conjunto de todos los símbolos que contiene. ${\ Displaystyle \ operatorname {ar}: S _ {\ operatorname {func}} \ cup S _ {\ operatorname {rel}} \ rightarrow \ mathbb {N} _ {0}}$

Una teoría de primer orden consiste en una firma fija y un conjunto fijo de oraciones (fórmulas sin variables libres) en esa firma. Las teorías a menudo se especifican dando una lista de axiomas que generan la teoría, o dando una estructura y considerando que la teoría consiste en las oraciones satisfechas por la estructura.

Estructuras / Modelos

Dada una firma σ , una σ - estructura M es una interpretación concreta de los símbolos en σ . Consiste en un conjunto subyacente (a menudo también denotado por " M ") junto con una interpretación de los símbolos de función y relación de σ . Una interpretación de un símbolo constante de σ en M es simplemente un elemento de M . Más en general, una interpretación de un n ary símbolo de la función f es una función de M ⁿ a M . De manera similar, una interpretación de un símbolo de relación R es una relación n -aria en M , es decir, un subconjunto de  M ⁿ .

Una subestructura de una σ -estructura M se obtiene tomando un subconjunto N de M que está cerrado bajo las interpretaciones de todos los símbolos de función en σ (por lo tanto, incluye las interpretaciones de todos los símbolos constantes en σ ), y luego restringiendo las interpretaciones de la símbolos relación a N . Una subestructura elemental es un caso muy especial de esto; en particular, una subestructura elemental satisface exactamente las mismas oraciones de primer orden que la estructura original (su extensión elemental).

Consecuencias

El enunciado dado en la introducción sigue inmediatamente tomando M como un modelo infinito de la teoría. La demostración de la parte ascendente del teorema también muestra que una teoría con modelos finitos arbitrariamente grandes debe tener un modelo infinito; a veces esto se considera parte del teorema.

Una teoría se llama categórica si tiene un solo modelo, hasta el isomorfismo. Este término fue introducido por Veblen (1904) , y durante algún tiempo los matemáticos esperaban poder poner las matemáticas sobre una base sólida al describir una teoría categórica de primer orden de alguna versión de la teoría de conjuntos. El teorema de Löwenheim-Skolem asestó un primer golpe a esta esperanza, ya que implica que una teoría de primer orden que tiene un modelo infinito no puede ser categórica. Más tarde, en 1931, la esperanza se hizo añicos por completo por el teorema de incompletitud de Gödel .

Muchas consecuencias del teorema de Löwenheim-Skolem parecían contradictorias para los lógicos a principios del siglo XX, ya que aún no se entendía la distinción entre propiedades de primer orden y propiedades que no eran de primer orden. Una de esas consecuencias es la existencia de incontables modelos de aritmética verdadera , que satisfacen todos los axiomas de inducción de primer orden pero tienen subconjuntos no inductivos.

Sea N los números naturales y R los reales. Se deduce del teorema que la teoría de ( N , +, ×, 0, 1) (la teoría de la verdadera aritmética de primer orden) tiene modelos incontables, y que la teoría de ( R , +, ×, 0, 1) (la teoría de los campos cerrados reales ) tiene un modelo contable. Existen, por supuesto, axiomatizaciones que caracterizan ( N , +, ×, 0, 1) y ( R , +, ×, 0, 1) hasta el isomorfismo. El teorema de Löwenheim-Skolem muestra que estas axiomatizaciones no pueden ser de primer orden. Por ejemplo, en la teoría de los números reales, la integridad de un orden lineal utilizado para caracterizar a R como un campo ordenado completo es una propiedad que no es de primer orden .

Otra consecuencia que se consideró particularmente preocupante es la existencia de un modelo contable de teoría de conjuntos, que sin embargo debe satisfacer la oración que dice que los números reales son incontables. El teorema de Cantor establece que algunos conjuntos son incontables. Esta situación contraria a la intuición llegó a conocerse como la paradoja de Skolem ; muestra que la noción de contabilidad no es absoluta .

Boceto de prueba

Parte hacia abajo

Para cada fórmula de primer orden, el axioma de elección implica la existencia de una función ${\ Displaystyle \ sigma}$${\ Displaystyle \ varphi (y, x_ {1}, \ ldots, x_ {n}) \ ,,}$

${\ Displaystyle f _ {\ varphi}: M ^ {n} \ a M}$

tal que, para todos , tampoco ${\ Displaystyle a_ {1}, \ ldots, a_ {n} \ in M}$

${\ Displaystyle M \ modelos \ varphi (f _ {\ varphi} (a_ {1}, \ dots, a_ {n}), a_ {1}, \ dots, a_ {n})}$

o

${\ Displaystyle M \ modelos \ neg \ existe y \, \ varphi (y, a_ {1}, \ dots, a_ {n}) \ ,.}$

Aplicando el axioma de elección nuevamente obtenemos una función de las fórmulas de primer orden a tales funciones${\ Displaystyle \ varphi}$${\ Displaystyle f _ {\ varphi} \ ,.}$

La familia de funciones da lugar a un operador de precierre en el conjunto de potencia de${\ Displaystyle f _ {\ varphi}}$ ${\ Displaystyle F}$${\ Displaystyle M}$

${\ Displaystyle F (A) = \ {f _ {\ varphi} (a_ {1}, \ dots, a_ {n}) \ in M ​​\ mid \ varphi \ in \ sigma; \, a_ {1}, \ dots , a_ {n} \ in A \}}$

por ${\ Displaystyle A \ subseteq M \ ,.}$

Iterar numerablemente muchas veces da como resultado un operador de cierre. Tomando un subconjunto arbitrario tal que , y habiendo definido, se puede ver que también Then es una subestructura elemental de según la prueba de Tarski-Vaught . ${\ Displaystyle F}$ ${\ Displaystyle F ^ {\ omega} \ ,.}$${\ Displaystyle A \ subseteq M}$${\ Displaystyle \ left \ vert A \ right \ vert = \ kappa}$${\ Displaystyle N = F ^ {\ omega} (A) \ ,,}$${\ Displaystyle \ left \ vert N \ right \ vert = \ kappa \ ,.}$${\ Displaystyle N}$${\ Displaystyle M}$

El truco utilizado en esta demostración se debe esencialmente a Skolem, quien introdujo símbolos de función para las funciones de Skolem en el lenguaje. También se podría definir como funciones parciales de tal manera que se define si y solo si El único punto importante es que es un operador de cierre previo tal que contiene una solución para cada fórmula con parámetros en los que tiene una solución en y que ${\ Displaystyle f _ {\ varphi}}$${\ Displaystyle f _ {\ varphi}}$${\ Displaystyle f _ {\ varphi}}$${\ Displaystyle M \ modelos \ existe y \, \ varphi (y, a_ {1}, \ dots, a_ {n}) \ ,.}$${\ Displaystyle F}$${\ Displaystyle F (A)}$${\ Displaystyle A}$${\ Displaystyle M}$

${\ Displaystyle \ left \ vert F (A) \ right \ vert \ leq \ left \ vert A \ right \ vert + \ left \ vert \ sigma \ right \ vert + \ aleph _ {0} \ ,.}$

Parte ascendente

En primer lugar, se extiende la firma mediante la adición de un nuevo símbolo constante para cada elemento de M . La teoría completa de M para la firma extendida σ' se llama el diagrama elemental de H . En el siguiente paso uno agrega κ muchos nuevos símbolos constantes a la firma y agrega al diagrama elemental de M las oraciones c ≠ c ' para dos nuevos símbolos constantes distintos c y c' . Usando el teorema de la compacidad , la teoría resultante se ve fácilmente como consistente. Dado que sus modelos deben tener cardinalidad al menos κ , la parte descendente de este teorema garantiza la existencia de un modelo N que tiene cardinalidad exactamente κ . Contiene una copia isomorfa de M como subestructura elemental.

En otras lógicas

Aunque el teorema (clásico) de Löwenheim-Skolem está muy ligado a la lógica de primer orden, las variantes son válidas para otras lógicas. Por ejemplo, toda teoría consistente en lógica de segundo orden tiene un modelo más pequeño que el primer cardinal supercompacto (suponiendo que exista uno). El tamaño mínimo al que se aplica un teorema de tipo Löwenheim-Skolem (descendente) en una lógica se conoce como el número de Löwenheim, y se puede utilizar para caracterizar la fuerza de esa lógica. Además, si vamos más allá de la lógica de primer orden, debemos renunciar a una de tres cosas: compacidad contable, el teorema descendente de Löwenheim-Skolem o las propiedades de una lógica abstracta .

Notas históricas

Este relato se basa principalmente en Dawson (1993) . Para comprender la historia temprana de la teoría de modelos, uno debe distinguir entre consistencia sintáctica (no se puede derivar ninguna contradicción usando las reglas de deducción para la lógica de primer orden) y satisfacibilidad (hay un modelo). Sorprendentemente, incluso antes de que el teorema de completitud hiciera innecesaria la distinción, el término coherente se usaba a veces en un sentido ya veces en el otro.

El primer resultado significativo en lo que más tarde se convirtió en teoría de modelos fue el teorema de Löwenheim en la publicación de Leopold Löwenheim "Über Möglichkeiten im Relativkalkül" (1915):

Para cada firma contable σ , cada σ- oración que es satisfactoria es satisfactoria en un modelo contable.

El artículo de Löwenheim en realidad se refería al cálculo más general de parientes de Peirce- Schröder ( álgebra de relaciones con cuantificadores). También usó las ahora anticuadas notaciones de Ernst Schröder . Para obtener un resumen del artículo en inglés y utilizando notaciones modernas, consulte Brady (2000 , capítulo 8).

Según la visión histórica recibida, la prueba de Löwenheim era defectuosa porque utilizaba implícitamente el lema de Kőnig sin probarlo, aunque el lema aún no era un resultado publicado en ese momento. En un relato revisionista , Badesa (2004) considera que la demostración de Löwenheim era completa.

Skolem (1920) dio una prueba (correcta) utilizando fórmulas en lo que más tarde se llamaría forma normal de Skolem y basándose en el axioma de elección:

Toda teoría contable que es satisfiable en un modelo M , es satisfiable en una subestructura numerable de M .

Skolem (1922) también demostró la siguiente versión más débil sin el axioma de elección:

Toda teoría contable que es satisfactoria en un modelo también lo es en un modelo contable.

Skolem (1929) simplificó Skolem (1920) . Finalmente, Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) demostró el teorema de Löwenheim-Skolem en su completa generalidad ( Maltsev 1936 ). Citó una nota de Skolem, según la cual el teorema había sido probado por Alfred Tarski en un seminario en 1928. Por lo tanto, el teorema general se conoce a veces como el teorema de Löwenheim-Skolem-Tarski . Pero Tarski no recordó su demostración, y sigue siendo un misterio cómo pudo hacerlo sin el teorema de la compacidad .

Es algo irónico que el nombre de Skolem esté conectado con la dirección ascendente del teorema así como con la dirección descendente:

"Sigo la costumbre al llamar al Corolario 6.1.4 el teorema ascendente de Löwenheim-Skolem. Pero, de hecho, Skolem ni siquiera lo creyó, porque no creía en la existencia de incontables conjuntos". - Hodges (1993) .

"Skolem [...] rechazó el resultado por carecer de sentido; Tarski respondió [...] muy razonablemente que el punto de vista formalista de Skolem debería considerar que el teorema descendente de Löwenheim-Skolem no tiene sentido al igual que el ascendente". - Hodges (1993) .

“Cuenta la leyenda que Thoralf Skolem, hasta el final de su vida, se escandalizó por la asociación de su nombre a un resultado de este tipo, que consideraba un absurdo, siendo innumerables conjuntos, para él, ficciones sin existencia real”. - Poizat (2000) .

Referencias

Fuentes

El teorema de Löwenheim-Skolem se trata en todos los textos introductorios sobre teoría de modelos o lógica matemática .

Publicaciones históricas

• Löwenheim, Leopold (1915), "Über Möglichkeiten im Relativkalkül" (PDF) , Mathematische Annalen , 76 (4): 447–470, doi : 10.1007 / BF01458217 , ISSN  0025-5831 , S2CID  116581304
  • Löwenheim, Leopold (1977), "Sobre las posibilidades en el cálculo de los parientes", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3ª ed.), Cambridge, Massachusetts: Harvard University Press, págs. 228– 251, ISBN 0-674-32449-8( copia en línea , p. 228, en Google Books )
• Maltsev, Anatoly Ivanovich (1936), "Untersuchungen aus dem Gebiete der mathischen Logik" , Matematicheskii Sbornik , Novaya Seriya, 1 (43) (3): 323–336
• Skolem, Thoralf (1920), "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem théorème über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse , 4 : 1-36
  • Skolem, Thoralf (1977), "Investigaciones lógico-combinatorias en la satisfacibilidad o probabilidad de proposiciones matemáticas: una demostración simplificada de un teorema de L. Löwenheim y generalizaciones del teorema", De Frege a Gödel: un libro de consulta en lógica matemática, 1879-1931 (3ª ed.), Cambridge, Massachusetts: Harvard University Press, págs. 252–263, ISBN 0-674-32449-8( copia en línea , p. 252, en Google Books )
• Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre", Mathematikerkongressen I Helsingfors den 4–7 de julio de 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217-232
  • Skolem, Thoralf (1977), "Algunas observaciones sobre la teoría de conjuntos axiomatizada", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3ª ed.), Cambridge, Massachusetts: Harvard University Press, págs. 290-301 , ISBN 0-674-32449-8( copia en línea , p. 290, en Google Books )
• Skolem, Thoralf (1929), "Über einige Grundlagenfragen der Mathematik", Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematisk-naturvidenskabelig Klasse , 7 : 1–49
• Veblen, Oswald (1904), "A System of Axioms for Geometry", Transactions of the American Mathematical Society , 5 (3): 343–384, doi : 10.2307 / 1986462 , ISSN  0002-9947 , JSTOR  1986462

Fuentes secundarias

• Badesa, Calixto (2004), El nacimiento de la teoría del modelo: el teorema de Löwenheim en el marco de la teoría de los familiares , Princeton, Nueva Jersey: Princeton University Press, ISBN 978-0-691-05853-5; Un relato más conciso aparece en el capítulo 9 de Leila Haaparanta , ed. (2009), El desarrollo de la lógica moderna , Oxford University Press, ISBN 978-0-19-513731-6
• Brady, Geraldine (2000), De Peirce a Skolem: Un capítulo olvidado en la historia de la lógica , Elsevier, ISBN 978-0-444-50334-3
• Crossley, JN ; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972), ¿Qué es la lógica matemática? , Londres / Oxford / Nueva York: Oxford University Press , págs. 59–60, ISBN 0-19-888087-1, Zbl  0251.02001
• Dawson, John W., Jr. (1993), "The compactness of First-Order Logic: From Gödel to Lindström", History and Philosophy of Logic , 14 : 15–37, doi : 10.1080 / 01445349308837208
• Hodges, Wilfrid (1993), teoría de modelos , Cambridge: Cambridge Univ. Pr., ISBN 978-0-521-30442-9
• Poizat, Bruno (2000), Un curso de teoría de modelos: una introducción a la lógica matemática contemporánea , Berlín, Nueva York: Springer, ISBN 978-0-387-98655-5

enlaces externos

• Sajarov, A .; Weisstein, EW "Teorema de Löwenheim-Skolem" . MathWorld .
• Burris, Stanley N., Contribuciones de los lógicos, Parte II, De Richard Dedekind a Gerhard Gentzen
• Burris, Stanley N., teorema descendente de Löwenheim-Skolem
• Simpson, Stephen G. (1998), teoría de modelos