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 , llamado así en honor a Leopold Löwenheim y Thoralf Skolem .

La formulación precisa se da a continuación. Implica que si una teoría de primer orden contable 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 no pueden controlar la cardinalidad de sus modelos infinitos.

El teorema de Löwenheim-Skolem (hacia abajo) 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 signatura σ , cada σ - estructura infinita M y cada número cardinal infinito κ ≥ | σ | , existe 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 se suele dividir 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 de Löwenheim-Skolem descendente . ^{[1] : 160–162} La parte del teorema que afirma que una estructura tiene extensiones elementales de todas las cardinalidades más grandes se conoce como el teorema de Löwenheim-Skolem ascendente . ^[2]

Discusión

A continuación profundizaremos en el concepto general de firmas y estructuras.

Conceptos

Firmas

Una firma consiste en 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 de constante). En el contexto de la lógica de primer orden, a veces una firma se denomina lenguaje. Se denomina 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. ^{[3] : 40} Las teorías a menudo se especifican dando una lista de axiomas que generan la teoría, o dando una estructura y tomando la teoría como si consistiera en las oraciones satisfechas por la estructura.

Estructuras / Modelos

Dada una signatura σ , 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 . De manera más general, una interpretación de un símbolo de función n -ario 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 los símbolos de 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

La afirmación dada en la introducción se deduce inmediatamente al considerar que M es un modelo infinito de la teoría. La prueba 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 se considera que esto es parte del teorema. ^[1]

Una teoría se denomina categórica si tiene un solo modelo, salvo que se trate de un isomorfismo. Este término fue introducido por Veblen (1904), y durante algún tiempo los matemáticos tuvieron la esperanza de poder sentar unas bases sólidas para las matemáticas 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 se hizo añicos por completo con 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 comprendía la distinción entre propiedades de primer orden y propiedades que no lo son. 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 sigue 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 cuerpos reales cerrados ) tiene un modelo contable. Existen, por supuesto, axiomatizaciones que caracterizan a ( 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 completitud de un orden lineal utilizado para caracterizar a R como un cuerpo 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 numerable de la 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 contraintuitiva llegó a conocerse como la paradoja de Skolem ; muestra que la noción de numerabilidad no es absoluta . ^[4]

Boceto de prueba

Parte descendente

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}$

de modo que, para todo , o bien ${\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 en el conjunto 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}$

La iteración de una cantidad contable de veces da como resultado un operador de cierre . Si se toma un subconjunto arbitrario tal que , y se ha definido , se puede ver que también . Entonces es una subestructura elemental de mediante 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 tales que se define si y solo si . El único punto importante es que es un operador de preclusión 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},\ldots ,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 añadiendo un nuevo símbolo constante para cada elemento de . La teoría completa de para la firma extendida se llama diagrama elemental de . En el siguiente paso se añaden muchos nuevos símbolos constantes a la firma y se añade al diagrama elemental de las oraciones para dos nuevos símbolos constantes distintos y . Utilizando el teorema de compacidad , se ve fácilmente que la teoría resultante es consistente. Puesto que sus modelos deben tener cardinalidad al menos , la parte descendente de este teorema garantiza la existencia de un modelo que tiene cardinalidad exactamente . Contiene una copia isomorfa de como subestructura elemental. ^{[5] [6] : 100–102} ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \sigma '}$ ${\displaystyle M}$ ${\displaystyle \kappa }$ ${\displaystyle M}$ ${\displaystyle c\neq c'}$ ${\displaystyle c}$ ${\displaystyle c'}$ ${\displaystyle \kappa }$ ${\displaystyle N}$ ${\displaystyle \kappa }$ ${\displaystyle M}$

En otras lógicas

Aunque el teorema de Löwenheim-Skolem (clásico) está muy ligado a la lógica de primer orden, existen variantes para otras lógicas. Por ejemplo, cada 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 en el que se aplica un teorema de tipo Löwenheim-Skolem (hacia abajo) en una lógica se conoce como el 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 numerable, el teorema de Löwenheim-Skolem hacia abajo o las propiedades de una lógica abstracta . ^{[7] : 134}

Notas históricas

Esta explicación se basa principalmente en Dawson (1993). Para entender la historia temprana de la teoría de modelos, hay que 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). Resulta un tanto sorprendente que, incluso antes de que el teorema de completitud hiciera innecesaria la distinción, el término consistente se utilizaba a veces en un sentido y a veces 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 sea satisfacible es satisfacible en un modelo contable.

El artículo de Löwenheim se ocupaba en realidad del cálculo de relativos de Peirce -Schröder ( álgebra de relaciones con cuantificadores) más general. ^[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, véase Brady (2000, capítulo 8).

Según la visión histórica aceptada, la prueba de Löwenheim era errónea porque utilizaba implícitamente el lema de König sin demostrarlo, aunque el lema no era todavía un resultado publicado en ese momento. En una postura revisionista , Badesa (2004) considera que la prueba 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 satisfacible en un modelo M , es satisfacible 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 satisfacible en un modelo también es satisfacible en un modelo contable.

Skolem (1929) simplificó el teorema de 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 prueba, y sigue siendo un misterio cómo pudo hacerlo sin el teorema de compacidad .

Es un tanto irónico que el nombre de Skolem esté relacionado con la dirección ascendente del teorema tanto 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 como carente 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 carecía de 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 los conjuntos innumerables, para él, ficciones sin existencia real." – Poizat (2000).

Referencias

1. Nourani, CF, Una teoría de modelos funcionales: aplicaciones más nuevas a la topología algebraica, conjuntos descriptivos y categorías computacionales Topos ( Toronto : Apple Academic Press; Boca Raton : CRC Press , 2014), págs. 160–162.
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ág. 40.
4. Bays, T., "La paradoja de Skolem", Stanford Encyclopedia of Philosophy , invierno de 2014.
5. Church, A. y Langford, CH , eds., The Journal of Symbolic Logic ( Storrs, CT : Asociación para la lógica simbólica , 1981), pág. 529.
6. Leary, CC, y Kristiansen, L., Una introducción amigable a la lógica matemática ( Geneseo, NY : Milne Library, 2015), págs. 100–102.
7. Chang, CC y Keisler, HJ , Model Theory , 3.ª ed. ( Mineola & New York : Dover Publications , 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 relativos", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3.ª ed.), Cambridge, Massachusetts: Harvard University Press, pp. 228–251, ISBN 0-674-32449-8( copia en línea , pág. 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 en la satisfacibilidad o demostrabilidad de proposiciones matemáticas: una prueba simplificada de un teorema de L. Löwenheim y generalizaciones del teorema", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3.ª ed.), Cambridge, Massachusetts: Harvard University Press, pp. 252–263, ISBN 0-674-32449-8( copia en línea , pág. 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", From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3.ª ed.), Cambridge, Massachusetts: Harvard University Press, pp. 290–301, ISBN 0-674-32449-8( copia en línea , pág. 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 relativos, Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5; Una explicación más concisa aparece en el capítulo 9 de Leila Haaparanta , ed. (2009), The Development of Modern Logic , Oxford University Press, ISBN 978-0-852-3-372-0. 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), "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: 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