Teorema de Löwenheim – Skolem - Löwenheim–Skolem theorem
Em lógica matemática , o teorema de Löwenheim – Skolem é um teorema sobre a existência e cardinalidade de modelos , nomeado após Leopold Löwenheim e Thoralf Skolem .
A formulação precisa é fornecida abaixo. Isso implica que, se uma teoria de primeira ordem contável tem um modelo infinito , então para cada número cardinal infinito κ ela tem um modelo de tamanho κ , e que nenhuma teoria de primeira ordem com um modelo infinito pode ter um modelo único até o isomorfismo . Como consequência, as teorias de primeira ordem são incapazes de controlar a cardinalidade de seus modelos infinitos.
O teorema de Löwenheim – Skolem (descendente) é uma das duas propriedades principais, junto com o teorema da compactação , que são usados no teorema de Lindström para caracterizar a lógica de primeira ordem . Em geral, o teorema de Löwenheim-Skolem não se aplica a lógicas mais fortes, como a lógica de segunda ordem .
Teorema
Em sua forma geral, o Teorema de Löwenheim – Skolem afirma que para cada assinatura σ , cada σ infinito - estrutura M e cada número cardinal infinito κ ≥ | σ | , existe uma σ -estrutura N tal que | N | = κ e tal que
- se κ <| M | então N é uma subestrutura elementar de M ;
- se κ > | M | em seguida, N representa uma extensão primária de H .
O teorema é freqüentemente dividido em duas partes correspondentes aos dois casos acima. A parte do teorema que afirma que uma estrutura tem subestruturas elementares de todas as cardinalidades infinitas menores é conhecida como teorema de Löwenheim-Skolem descendente . A parte do teorema que afirma que uma estrutura tem extensões elementares de todas as cardinalidades maiores é conhecida como teorema de Löwenheim-Skolem ascendente .
Discussão
Abaixo, elaboramos o conceito geral de assinaturas e estruturas.
Conceitos
Assinaturas
Uma assinatura consiste em um conjunto de símbolos de função S func , um conjunto de símbolos de relação S rel e uma função que representa a aridade de símbolos de função e relação. (Um símbolo de função nula é chamado de símbolo constante.) No contexto da lógica de primeira ordem, uma assinatura às vezes é chamada de linguagem. É denominado contável se o conjunto de símbolos de função e relação nele contido e, em geral, a cardinalidade de uma assinatura é a cardinalidade do conjunto de todos os símbolos que ela contém.
Uma teoria de primeira ordem consiste em uma assinatura fixa e um conjunto fixo de sentenças (fórmulas sem variáveis livres) nessa assinatura. As teorias são frequentemente especificadas fornecendo uma lista de axiomas que geram a teoria ou fornecendo uma estrutura e considerando que a teoria consiste nas sentenças satisfeitas pela estrutura.
Estruturas / Modelos
Dada uma assinatura σ , uma σ - estrutura M é uma interpretação concreta dos símbolos em σ . Consiste em um conjunto subjacente (freqüentemente também denotado por " M ") junto com uma interpretação dos símbolos de função e relação de σ . Uma interpretação de um símbolo constante de σ em H é simplesmente um elemento de M . Mais geralmente, uma interpretação de um n símbolo função -ary F é uma função de M n a M . Da mesma forma, uma interpretação de um símbolo de relação R é uma relação n -ary em M , ou seja, um subconjunto de M n .
Uma subestrutura de uma σ -estrutura M é obtida tomando um subconjunto N de M que é fechado sob as interpretações de todos os símbolos de função em σ (portanto, inclui as interpretações de todos os símbolos constantes em σ ), e então restringindo as interpretações do símbolos relação ao N . Uma subestrutura elementar é um caso muito especial disso; em particular, uma subestrutura elementar satisfaz exatamente as mesmas sentenças de primeira ordem que a estrutura original (sua extensão elementar).
Consequências
A declaração dada na introdução segue imediatamente, tomando M como um modelo infinito da teoria. A prova da parte ascendente do teorema também mostra que uma teoria com modelos finitos arbitrariamente grandes deve ter um modelo infinito; às vezes, isso é considerado parte do teorema.
Uma teoria é chamada de categórica se possuir apenas um modelo, até o isomorfismo. Esse termo foi introduzido por Veblen (1904) e, por algum tempo depois disso, os matemáticos esperaram poder colocar a matemática em uma base sólida, descrevendo uma teoria categórica de primeira ordem de alguma versão da teoria dos conjuntos. O teorema de Löwenheim-Skolem desferiu um primeiro golpe nesta esperança, pois implica que uma teoria de primeira ordem com um modelo infinito não pode ser categórica. Mais tarde, em 1931, a esperança foi destruída completamente pelo teorema da incompletude de Gödel .
Muitas consequências do teorema de Löwenheim-Skolem pareciam contra-intuitivas para os lógicos no início do século 20, pois a distinção entre propriedades de primeira ordem e não de primeira ordem ainda não era compreendida. Uma dessas consequências é a existência de incontáveis modelos de aritmética verdadeira , que satisfazem todos os axiomas de indução de primeira ordem, mas têm subconjuntos não indutivos.
Seja N os números naturais e R os reais. Decorre do teorema que a teoria de ( N , +, ×, 0, 1) (a teoria da verdadeira aritmética de primeira ordem) tem modelos incontáveis, e que a teoria de ( R , +, ×, 0, 1) (a teoria dos campos fechados reais ) tem um modelo contável. Existem, é claro, axiomatizações que caracterizam ( N , +, ×, 0, 1) e ( R , +, ×, 0, 1) até isomorfismo. O teorema de Löwenheim – Skolem mostra que essas axiomatizações não podem ser de primeira ordem. Por exemplo, na teoria dos números reais, a integridade de uma ordem linear usada para caracterizar R como um campo ordenado completo é uma propriedade não de primeira ordem .
Outra consequência que foi considerada particularmente preocupante é a existência de um modelo contável da teoria dos conjuntos, que, no entanto, deve satisfazer a frase que diz que os números reais são incontáveis. O teorema de Cantor afirma que alguns conjuntos são incontáveis. Essa situação contra-intuitiva veio a ser conhecida como o paradoxo de Skolem ; mostra que a noção de contabilidade não é absoluta .
Esboço de prova
Parte descendente
Para cada fórmula de primeira ordem, o axioma de escolha implica a existência de uma função
de tal forma que, para todos , qualquer um
ou
Aplicando o axioma da escolha novamente, obtemos uma função das fórmulas de primeira ordem para tais funções
A família de funções dá origem a um operador de pré - fechamento no conjunto de energia de
para
A iteração contável muitas vezes resulta em um operador de fechamento Tomando um subconjunto arbitrário tal que , e tendo definido, pode-se ver que também Then é uma subestrutura elementar de pelo teste de Tarski-Vaught .
O truque usado nesta prova é essencialmente devido a Skolem, que introduziu símbolos de função para as funções Skolem na linguagem. Pode-se também definir as funções como parciais tais que são definidas se e somente se O único ponto importante é que é um operador de pré-fechamento tal que contém uma solução para cada fórmula com parâmetros em que tem uma solução em e que
Parte para cima
Primeiro, se estende a assinatura adicionando um novo símbolo constante para cada elemento da M . A teoria completa de M para a assinatura estendida σ' é chamado o diagrama elementar de M . Na próxima etapa, adiciona-se κ muitos novos símbolos constantes à assinatura e adiciona-se ao diagrama elementar de M as sentenças c ≠ c ' para quaisquer dois novos símbolos de constantes distintos c e c' . Usando o teorema da compactação , a teoria resultante é facilmente considerada consistente. Como seus modelos devem ter cardinalidade pelo menos κ , a parte descendente deste teorema garante a existência de um modelo N que possui cardinalidade exatamente κ . Ele contém uma cópia isomórfica de M como uma subestrutura elementar.
Em outras lógicas
Embora o teorema de Löwenheim – Skolem (clássico) esteja intimamente ligado à lógica de primeira ordem, as variantes são válidas para outras lógicas. Por exemplo, toda teoria consistente na lógica de segunda ordem tem um modelo menor do que o primeiro cardeal supercompacto (assumindo que exista). O tamanho mínimo no qual um teorema do tipo Löwenheim – Skolem (para baixo) se aplica em uma lógica é conhecido como o número de Löwenheim e pode ser usado para caracterizar a força dessa lógica. Além disso, se formos além da lógica de primeira ordem, devemos abrir mão de uma de três coisas: compactação contável, o teorema de Löwenheim-Skolem descendente ou as propriedades de uma lógica abstrata .
Notas históricas
Esse relato é baseado principalmente em Dawson (1993) . Para entender a história inicial da teoria do modelo, deve-se distinguir entre consistência sintática (nenhuma contradição pode ser derivada usando as regras de dedução para lógica de primeira ordem) e satisfatibilidade (existe um modelo). Surpreendentemente, mesmo antes de o teorema da completude tornar desnecessária a distinção, o termo consistente foi usado às vezes em um sentido e às vezes no outro.
O primeiro resultado significativo no que mais tarde se tornou a teoria modelo foi o teorema de Löwenheim em Leopold Löwenheim da publicação 'Über Möglichkeiten im Relativkalkül' (1915):
- Para cada assinatura contável σ , cada sentença σ que é satisfazível é satisfazível em um modelo contável.
O artigo de Löwenheim estava realmente preocupado com o cálculo mais geral de Peirce –Schröder de parentes ( álgebra de relação com quantificadores). Ele também usou as notações agora antiquadas de Ernst Schröder . Para um resumo do artigo em inglês e usando notações modernas, ver Brady (2000 , capítulo 8).
De acordo com a visão histórica recebida, a prova de Löwenheim era falha porque implicitamente usou o lema de Kőnig sem prová-lo, embora o lema ainda não fosse um resultado publicado na época. Em um relato revisionista , Badesa (2004) considera que a prova de Löwenheim estava completa.
Skolem (1920) deu uma prova (correta) usando fórmulas no que mais tarde seria chamado de forma normal de Skolem e baseando-se no axioma da escolha:
- Toda teoria contábil que é satisfiable em um modelo M , é satisfeita em uma subestrutura contável de M .
Skolem (1922) também provou a seguinte versão mais fraca sem o axioma de escolha:
- Cada teoria contável que pode ser satisfeita em um modelo também pode ser satisfeita em um modelo contável.
Skolem (1929) simplificou Skolem (1920) . Finalmente, Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) provou o teorema de Löwenheim-Skolem em sua generalidade completa ( Maltsev 1936 ). Ele citou uma nota de Skolem, segundo a qual o teorema havia sido provado por Alfred Tarski em um seminário em 1928. Portanto, o teorema geral é às vezes conhecido como teorema de Löwenheim-Skolem-Tarski . Mas Tarski não se lembrava de sua prova, e permanece um mistério como ele poderia fazer isso sem o teorema da compactação .
É um tanto irônico que o nome de Skolem esteja conectado com a direção para cima do teorema, bem como com a direção para baixo:
- "Eu sigo o costume ao chamar o Corolário 6.1.4 de teorema de Löwenheim-Skolem ascendente. Mas, na verdade, Skolem nem mesmo acreditou, porque ele não acreditava na existência de conjuntos incontáveis." - Hodges (1993) .
- "Skolem rejeitou o resultado como sem sentido; Tarski [...] muito razoavelmente respondeu que o ponto de vista formalista de Skolem deveria considerar o teorema de Löwenheim-Skolem descendente sem sentido assim como o teorema ascendente." - Hodges (1993) .
- "Diz a lenda que Thoralf Skolem, até o fim da vida, ficava escandalizado com a associação de seu nome a um resultado desse tipo, que considerava um absurdo, conjuntos inumeráveis sendo, para ele, ficções sem existência real." - Poizat (2000) .
Referências
Fontes
O teorema de Löwenheim – Skolem é tratado em todos os textos introdutórios sobre teoria de modelos ou lógica matemática .
Publicações 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 as possibilidades no cálculo dos parentes", De Frege a 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( cópia online , p. 228, no Google Livros )
- 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 théorème über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse , 4 : 1-36
- Skolem, Thoralf (1977), "Investigações lógico-combinatórias na satisfatibilidade ou provabilidade de proposições matemáticas: uma prova simplificada de um teorema de L. Löwenheim e generalizações do teorema", De Frege a 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( cópia online , p. 252, no Google Livros )
-
Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre", Mathematikerkongressen I Helsingfors den 4–7 de julho de 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217–232
- Skolem, Thoralf (1977), "Some remarks on axiomatized set theory", 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( cópia online , p. 290, no Google Livros )
- 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
Fontes secundárias
- Badesa, Calixto (2004), The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives , Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5; Um relato mais conciso aparece no capítulo 9 de Leila Haaparanta , ed. (2009), The Development of Modern Logic , Oxford University Press, ISBN 978-0-19-513731-6
- Brady, Geraldine (2000), From Peirce to Skolem: A Neglected Chapter in the History of Logic , Elsevier, ISBN 978-0-444-50334-3
- Crossley, JN ; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972), O que é lógica matemática? , Londres / Oxford / Nova York: Oxford University Press , pp. 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), Teoria do modelo , Cambridge: Cambridge Univ. Pr., ISBN 978-0-521-30442-9
- Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic , Berlim, Nova York: Springer, ISBN 978-0-387-98655-5
links externos
- Sakharov, A .; Weisstein, EW "Teorema de Löwenheim-Skolem" . MathWorld .
- Burris, Stanley N., Contributions of the Logicians, Part II, From Richard Dedekind to Gerhard Gentzen
- Burris, Stanley N., teorema de Downward Löwenheim – Skolem
- Simpson, Stephen G. (1998), Teoria do Modelo