Teorema de Löwenheim-Skolem

Existencia y cardinalidad de modelos de teorías lógicas.

En lógica matemática , el teorema de Löwenheim-Skolem es un teorema sobre la existencia y cardinalidad de modelos , que lleva el nombre de Leopold Löwenheim y Thoralf Skolem .

La formulación precisa se proporciona 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 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 cumple en lógicas más fuertes como la lógica de segundo orden .

Teorema

Ilustración del teorema de Löwenheim-Skolem

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

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

El teorema suele dividirse 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 teorema de Löwenheim-Skolem descendente . ^{[1] : 160–162} La parte del teorema que afirma que una estructura tiene extensiones elementales de todas las cardinalidades mayores se conoce como teorema ascendente de Löwenheim-Skolem . ^[2]

Discusión

A continuación detallamos 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 denomina símbolo constante). En el contexto de la lógica de primer orden, una firma a veces se denomina 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 consta de una firma fija y un conjunto fijo de oraciones (fórmulas sin variables libres) en esa firma. ^{[3] : 40} 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 indicado por " M ") junto con una interpretación de la función y los símbolos de relación de σ . Una interpretación de un símbolo constante de σ en M es simplemente un elemento de M. De manera más general, una interpretación de un símbolo de función n -aria 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 de relación con N . Un caso muy especial de esto es una subestructura elemental ; en particular, una subestructura elemental satisface exactamente las mismas oraciones de primer orden que la estructura original (su extensión elemental).

Consecuencias

La afirmación dada en la introducción sigue inmediatamente al tomar M como un modelo infinito de la teoría. La prueba de la parte superior 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. ^[1]

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 después los matemáticos esperaban poder dar a las matemáticas una base sólida describiendo 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 quedó completamente destrozada por el teorema de incompletitud de Gödel . ^[1]

Muchas consecuencias del teorema de Löwenheim-Skolem parecían contraintuitivas para los lógicos de principios del siglo XX, ya que aún no se entendía la distinción entre propiedades de primer orden y de no primer orden. Una de esas consecuencias es la existencia de innumerables 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. Del teorema se deduce que la teoría de ( N , +, ×, 0, 1) (la teoría de la aritmética verdadera de primer orden) tiene innumerables modelos, y que la teoría de ( R , +, ×, 0, 1) (la teoría de 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 . ^{[1] : 161}

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 frase que dice que los números reales son incontables. El teorema de Cantor establece que algunos conjuntos son incontables. Esta situación contraintuitiva llegó a conocerse como la paradoja de Skolem ; muestra que la noción de contabilidad no es absoluta . ^[4]

Bosquejo 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}\to M}$

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

${\displaystyle M\models \varphi (f_{\varphi }(a_{1},\dots ,a_{n}),a_{1},\dots ,a_{n})}$

o

${\displaystyle M\models \neg \exists y\,\varphi (y,a_{1},\dots ,a_{n})\,.}$

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

La familia de funciones da lugar a un operador de precierre sobre 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\}}$

para ${\displaystyle A\subseteq M\,.}$

Iterar contablemente muchas veces da como resultado un operador de cierre. Toma un subconjunto arbitrario tal que y una vez 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 prueba se debe esencialmente a Skolem, quien introdujo símbolos de función para las funciones de Skolem en el lenguaje. También se podrían definir funciones parciales tales que se definen si y solo si. El único punto importante es que es un operador de precierre 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\models \exists 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 hacia arriba

Primero, se extiende la firma agregando un nuevo símbolo constante para cada elemento de M. La teoría completa de M para la firma extendida σ' se llama diagrama elemental de M. En el siguiente paso se agregan κ muchos símbolos constantes nuevos a la firma y se agrega al diagrama elemental de M las oraciones c ≠ c' para dos nuevos símbolos constantes distintos c y c' . Utilizando el teorema de la compacidad , se ve fácilmente que la teoría resultante es 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 isomórfica de M como subestructura elemental. ^{[5] [6] : 100–102}

En otras lógicas

Aunque el teorema (clásico) de Löwenheim-Skolem está muy vinculado a la lógica de primer orden, existen variantes 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). El tamaño mínimo en el que se aplica un teorema de tipo Löwenheim-Skolem (descendente) en una lógica se conoce como número de Löwenheim y puede usarse 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: la compacidad contable, el teorema descendente de Löwenheim-Skolem o las propiedades de una lógica abstracta . ^{[7] : 134}

Notas historicas

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

El primer resultado significativo de lo que más tarde se convirtió en la 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 satisfactible lo es en un modelo contable.

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

Según la opinión histórica recibida, la demostración de Löwenheim fue defectuosa porque implícitamente utilizó el lema de Kőnig sin demostrarlo, 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 sea satisfactible en un modelo M , lo es en una subestructura contable 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 sea 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 toda su generalidad (Maltsev 1936). Citó una nota de Skolem, según la cual el teorema había sido demostrado por Alfred Tarski en un seminario en 1928. Por lo tanto, el teorema general a veces se conoce como teorema de Löwenheim-Skolem-Tarski . Pero Tarski no recordaba 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é relacionado tanto con la dirección ascendente del teorema como con la dirección descendente:

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

"Skolem [...] rechazó el resultado por considerarlo carente de sentido; Tarski [...] respondió muy razonablemente que el punto de vista formalista de Skolem debería considerar el teorema descendente de Löwenheim-Skolem sin sentido, al igual que el teorema 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 absurdo, siendo los conjuntos no numerables, para él, ficciones sin existencia real." – Poizat (2000).

Referencias

1. Nourani, CF, Una teoría del modelo funcional: aplicaciones más nuevas a la topología algebraica, conjuntos descriptivos y categorías informáticas Topos ( Toronto : Apple Academic Press; Boca Raton : CRC Press , 2014), págs.
2. Sheppard, B., La lógica del infinito ( Cambridge : Cambridge University Press , 2014), pág. 372.
3. Haan, R. de, Complejidad parametrizada en la jerarquía polinomial: extensión de la teoría de la complejidad parametrizada a niveles superiores de la jerarquía ( Berlín / Heidelberg : Springer , 2019), p. 40.
4. Bays, T., "La paradoja de Skolem", Enciclopedia de Filosofía de Stanford , invierno de 2014.
5. Church, A. y Langford, CH , eds., The Journal of Symbolic Logic ( Storrs, CT : Association for Symbolic Logic , 1981), pág. 529.
6. Leary, CC y Kristiansen, L., Una introducción amistosa a la lógica matemática ( Geneseo, Nueva York : Milne Library, 2015), págs.
7. Chang, CC y Keisler, HJ , Teoría de modelos , 3ª ed. ( Mineola y Nueva York : Publicaciones de Dover , 1990), pág. 134.

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 parientes", 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. 251, ISBN 0-674-32449-8( copia en línea , p. 228, en Google Books )
• Maltsev, Anatoly Ivanovich (1936), "Untersuchungen aus dem Gebiete der mathematischen 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 Theoreme über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse , 4 : 1–36
  • Skolem, Thoralf (1977), "Investigaciones lógico-combinatorias sobre la satisfacibilidad o demostrabilidad de proposiciones matemáticas: una prueba 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 del 4 al 7 de julio de 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217–232
  • Skolem, Thoralf (1977), "Algunas observaciones sobre la teoría de conjuntos axiomatizados", 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. , 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), "Un sistema de axiomas para la geometría", 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 de modelos: el teorema de Löwenheim en el marco de la teoría de los parientes, 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 ; Ceniza, 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), "La compacidad de la lógica de primer orden: de Gödel a Lindström", Historia y Filosofía de la Lógica , 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". MundoMatemático .
• Burris, Stanley N., Contribuciones de los lógicos, Parte II, De Richard Dedekind a Gerhard Gentzen
• Burris, Stanley N., Teorema de Löwenheim-Skolem descendente
• Simpson, Stephen G. (1998), Teoría de modelos