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

Ilustração do teorema de Löwenheim – Skolem

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 cc ' 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
  • 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 (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

links externos