Teorema de Löwenheim–Skolem – Wikipédia, a enciclopédia livre

Foi proposta a fusão deste artigo ou se(c)ção com Teorema_Löwenheim–Skolem (pode-se discutir o procedimento aqui). Editor, considere adicionar mês e ano na marcação. Isso pode ser feito automaticamente, substituindo esta predefinição por {{subst:fu|Teorema_Löwenheim–Skolem}}.

Na lógica matemática, o teorema Löwenheim-Skolem, assim denominado em referência a Leopold Löwenheim e Thoralf Skolem, afirma que, se uma teoria de primeira ordem contável tem um modelo infinito, então para cada número cardinal infinito κ, existe um modelo de tamanho κ. O resultado implica que as teorias de primeira ordem são incapazes de controlar a cardinalidade de seus modelos infinitos, e que nenhuma teoria de primeira ordem com um modelo infinito pode ter um modelo único, a menos de isomorfismo.

O teorema de Löwenheim-Skolem (descendente) é uma das duas principais propriedades, juntamente com o teorema da compacidade, que são utilizadas no teorema de Lindström para caracterizar a lógica de primeira ordem. Em geral, o teorema de Löwenheim-Skolem não se sustenta numa lógica mais forte, como a lógica de segunda ordem.

Contexto[editar | editar código-fonte]

A assinatura consiste de um conjunto de símbolos de S_func, um conjunto de símbolos de relação S_rel, e uma função ${\displaystyle \operatorname {ar} :S_{\operatorname {func} }\cup S_{\operatorname {rel} }\rightarrow \mathbb {N} _{0}}$ representando a aridade de símbolos de função e de relação. (Um símbolo de função nulário é chamado um símbolo de constante.) No contexto da lógica de primeira ordem, uma assinatura é por vezes chamada de uma linguagem. Ela é chamada de contável se o conjunto de símbolos de função e de relação é contável, e, em geral, a cardinalidade de uma assinatura é a cardinalidade do conjunto de todos os símbolos que ela contém.

A teoria de primeira ordem consiste de uma assinatura fixa e um conjunto fixo de sentenças (fórmulas sem variáveis ​​livres) nessa assinatura. As teorias são muitas vezes especificadas dando uma lista de axiomas que geram a teoria, ou dando uma estrutura e tendo a teoria consistente ante as sentenças satisfeitas pela estrutura.

Dada uma assinatura σ, uma σ-estrutura M é uma interpretação concreta dos símbolos σ. É composto por um conjunto de base (muitas vezes também denotado por "M"), juntamente com uma interpretação dos símbolos de função e relação de σ. Uma interpretação de um símbolo constante de σ em M é simplesmente um elemento de M. De modo mais geral, uma interpretação de um símbolo da função n-ary, f é uma função de Mⁿ para M. Da mesma forma, uma interpretação de um símbolo de relação R é um relação n-ary em M, ou seja, um subconjunto de Mⁿ.

A substrutura 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 σ (daí inclui as interpretações de todos os símbolos de constante σ), e depois restringindo as interpretações dos símbolos de relação a N. Uma subestrutura elementar é um caso muito especial deste; em especial, uma subestrutura elementar satisfaz exatamente as mesmas sentenças de primeira ordem que a estrutura original (a sua extensão elementar).

Enunciado Formal[editar | editar código-fonte]

A afirmação moderna do teorema é tanto mais geral e mais forte do que a versão para assinaturas referidas na introdução

Na sua forma mais geral, o teorema de Löwenheim-Skolem indica que, para cada assinatura σ, cada σ-estrutura infinita M e cada número cardinal infinito κ ≥ | σ |, existe uma σ-estrutura N tal que | N | = κ e

• se κ < | M | então N é uma subestrutura elementar de M;
• se κ > | M | então N é uma extensão elementar de M.

O teorema é muitas vezes dividido em duas partes que correspondem aos dois pontos acima. A parte do teorema, afirmando que uma estrutura tem subestruturas elementares de todos os cardinais infinitos menores, é conhecida como o Teorema de Löwenheim–Skolem decrescente. A parte do teorema afirmando que uma estrutura tem extensões elementares de todas as cardinalidades maiores é conhecida como Teorema de Löwenheim Skolem ascendente.

A instrução dada na introdução segue imediatamente, sendo M um modelo infinito da teoria. A prova da parte ascendente do teorema mostra também que uma teoria com arbitrariamente grandes modelos finitos deve ter um modelo infinito; Às vezes isso é considerado como parte do teorema. Para variantes históricas do teorema, veja as notas abaixo.

Exemplos e Consequencias[editar | editar código-fonte]

Seja N os números naturais e R os reais, sendo N e R símbolos para esses conjuntos. Decorre do teorema que a teoria de (N, +, ×, 0, 1) (a teoria da verdadeira aritmética de primeira ordem) tem inúmeros modelos, e que a teoria de (R, +, ×, 0, 1) (a teoria de corpos reais fechados) tem um modelo contável. Existem, naturalmente, axiomatizações caracterizando (N, +, ×, 0, 1) e (R, +, ×, 0, 1) a menos de isomorfismo. O teorema de Löwenheim-Skolem mostra que essas axiomatizações não podem ser de primeira ordem. Por exemplo, a completude de uma ordem linear, que é utilizada para caracterizar os números reais como um corpo ordenado completo, não é uma propriedade de primeira ordem.

Uma teoria é chamada de categórica se tem apenas um modelo, a menos de isomorfismo. Este termo foi introduzido por Veblen (1904), e tempos depois, matemáticos esperavam que eles pudessem colocar a matemática sobre uma base sólida, descrevendo uma teoria de primeira ordem categórica, de alguma versão da teoria dos conjuntos. O teorema de Löwenheim-Skolem desferiu um primeiro golpe nesta esperança, uma vez que implica que uma teoria de primeira ordem que tem 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 Löwenheim-Skolem parecia absurdo para os lógicos no início do século XX, como a distinção entre propriedades de primeira ordem e não de primeira ordem, que ainda não foi compreendido. Uma delas, é a existência de modelos de incontáveis ​​da verdade aritmética, que satisfazem toda indução axiomática de primeira ordem, mas têm subconjuntos não-indutivos. Outra consequência que foi considerado particularmente preocupante é a existência de um modelo contável da teoria dos conjuntos, que, no entanto, deve cumprir a sentença dizendo que os números reais são incontáveis​​. Essa situação contra-intuitiva veio a ser conhecido como o paradoxo de Skolem; isso mostra que a noção de contabilidade não é absoluta.

Esboço das provas[editar | editar código-fonte]

Parte descendente[editar | editar código-fonte]

Para cada ${\displaystyle \sigma \,}$-fórmula de primeira ordem ${\displaystyle \varphi (y,x_{1},\ldots ,x_{n})\,,}$o axioma da escolha implica a existência de uma função

${\displaystyle f_{\varphi }:M^{n}\to M}$

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

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

ou

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

Aplicando o axioma da escolha de novo, temos uma função a partir das fórmulas de primeira ordem ${\displaystyle \varphi }$ para funções ${\displaystyle f_{\varphi }\,.}$

A família de funções ${\displaystyle f_{\varphi }}$ dá origem a um operador de pré-fecho ${\displaystyle F\,}$ no conjunto das partes de ${\displaystyle M\,}$

${\displaystyle F(A)=\{b\in M\mid b=f_{\varphi }(a_{1},\dots ,a_{n});\,\varphi \in \sigma ;\,a_{1},\dots ,a_{n}\in A\}}$ para ${\displaystyle A\subseteq M\,.}$

Iteração ${\displaystyle F\,}$ contável muitas vezes resulta em um operador de fecho ${\displaystyle F^{\omega }\,.}$Tomar um subconjunto arbitrário ${\displaystyle A\subseteq M}$ tal que ${\displaystyle \left\vert A\right\vert =\kappa }$, e tendo definido ${\displaystyle N=F^{\omega }(A)\,,}$ percebe-se também que, ${\displaystyle \left\vert N\right\vert =\kappa \,.}$ ${\displaystyle N\,}$ é uma subestrutura elementar de ${\displaystyle M\,}$ 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 de Skolem ${\displaystyle f_{\varphi }}$ na linguagem. Pode-se também definir o ${\displaystyle f_{\varphi }}$ funções parciais de modo a que ${\displaystyle f_{\varphi }}$ está definida, se e somente se ${\displaystyle M\models \exists y\varphi (y,a_{1},\dots ,a_{n})\,.}$ O único ponto importante é que ${\displaystyle F\,}$ é um operador de pré-fecho tal que ${\displaystyle F(A)\,}$ contém uma solução para cada fórmula com parâmetros ${\displaystyle A\,}$ que tem uma solução de ${\displaystyle M\,}$ e que:

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

Parte Ascendente[editar | editar código-fonte]

Primeiro, estende-se a assinatura, adicionando um novo símbolo de constante para cada elemento de M. A teoria completa de M para a assinatura σ' estendida é chamada de diagrama elementar de M. No próximo passo se acrescenta κ novos símbolos de constante à assinatura e acrescenta-se que o diagrama básico de M as sentenças c ≠ c' para quaisquer dois novos símbolos distintos de constante c e c'. Utilizando o teorema da compacidade, a teoria resultante é facilmente vista como sendo consistente. Já que os seus modelos devem ter pelo menos cardinalidade κ, a parte descendente do presente teorema garante a existência do modelo N que tem exatamente cardinalidade κ. Ele contém uma cópia isomorfa de M como uma subestrutura elementar.

Notas históricas[editar | editar código-fonte]

Essa consideração é baseada principalmente em Dawson (1993). Para entender a história inicial da teoria de modelos, deve-se distinguir entre a coerência sintática (nenhuma contradição pode ser obtida usando as regras de dedução para a lógica de primeira ordem) e satisfatibilidade (existe um modelo). Surpreendentemente, mesmo antes do teorema da completude ter feito a distinção desnecessária, o termo consistente foi usado às vezes em um sentido e às vezes em outro.

O primeiro resultado significativo no que mais tarde tornou-se a teoria de modelos, e foi o teorema de Löwenheim na publicação de Leopold Löwenheim "Über Möglichkeiten im Relativkalkül" (1915):

Para cada σ assinatura contável, cada frase σ que é satisfatório pode ser satisfeita em um modelo contável.

O artigo de Löwenheim estava na verdade preocupado com o cálculo relacional de Peirce-Schröder (álgebra relacional com quantificadores). Ele também usou as anotações, agora antiquadas, de Ernst Schröder. Para um resumo do artigo em Inglês e utilizando notações modernas, ver Brady (2000, capítulo 8).

De acordo com a visão histórica recebida, a prova de Löwenheim estava com defeito, porque implicitamente usava o Lema de König, sem prová-lo, embora o lema ainda não era um resultado publicado na época. Em uma abordagem revisionista, Badesa (2004) considera que a prova de Löwenheim estava completa.

Skolem (1920) deu uma prova (correta) usando fórmulas no que viria a ser chamado de forma normal de Skolem e contando com o axioma da escolha:

Toda teoria contável que pode ser satisfeita em um modelo M, é satisfeita em uma subestrutura contável de M.

Skolem (1923) também se mostrou a seguinte versão mais fraca sem o axioma da escolha:

Toda 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 Löwenheim-Skolem em toda sua generalidade (Maltsev 1936). Ele citou uma nota por Skolem, segundo a qual o teorema foi provado por Alfred Tarski em um seminário em 1928. Portanto, o teorema geral é por vezes conhecido como o teorema Löwenheim-Skolem-Tarski. Mas Tarski não se lembrava de sua prova, e continua a ser um mistério como ele poderia fazê-lo sem o teorema de compacidade.

É irónico que o nome de Skolem esteja ligado com o sentido ascendente do teorema, bem como com o sentido descendente:

"Eu sigo costume em chamar 6.1.4 Corolário de teorema de Löwenheim-Skolem ascendente. Mas, na verdade, Skolem nem sequer acreditava, 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 do ponto de vista formalista de Skolem deve contar o teorema de Löwenheim-Skolem descendente como sem sentido assim como o ascendente" - Hodges (1993).

"Diz a lenda que Thoralf Skolem, até o fim de sua vida, se escandalizava com a associação de seu nome a um resultado deste tipo, o que ele considerava um absurdo, conjuntos não-enumeráveis seriam, para ele, ficções sem existência real." - Poizat (2000).

Referências[editar | editar código-fonte]

O teorema Löwenheim-Skolem é tratada em todos os textos introdutórios sobre a teoria de modelos ou lógica matemática.

Publicações históricas[editar | editar código-fonte]

• (1915), «Über Möglichkeiten im Relativkalkül», Mathematische Annalen, ISSN 0025-5831, 76 (4): 447–470, doi:10.1007/BF01458217 
  • Löwenheim, Leopold (1977), «On possibilities in the calculus of relatives», From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, ISBN 0-674-32449-8 3rd ed. , Cambridge, Massachusetts: Harvard University Press, pp. 228–251  (online copy, p. 228, no Google Livros)
• (1936), «Untersuchungen aus dem Gebiete der mathematischen Logik», Matematicheskii Sbornik, n.s., 1: 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, 6: 1–36 
  • Skolem, Thoralf (1977), «Logico-combinatorical investigations in the satisfiability or provabilitiy of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem», From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, ISBN 0-674-32449-8 3rd ed. , Cambridge, Massachusetts: Harvard University Press, pp. 252–263  (online copy, p. 252, no Google Livros)
• Skolem, Thoralf (1922), «Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre», Mathematikerkongressen i Helsingfors den 4–7 Juli 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, ISBN 0-674-32449-8 3rd ed. , Cambridge, Massachusetts: Harvard University Press, pp. 290–301  (online copy, 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, ISSN 0002-9947, 5 (3): 343–384, JSTOR 1986462, doi:10.2307/1986462 

Fontes secundárias[editar | editar código-fonte]

• Badesa, Calixto (2004), The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives, ISBN 978-0-691-05853-5, Princeton, NJ: Princeton University Press ; A more concise account appears in chapter 9 of Leila Haaparanta, ed. (2009), The Development of Modern Logic, ISBN 978-0-19-513731-6, Oxford University Press 
• Brady, Geraldine (2000), From Peirce to Skolem: A Neglected Chapter in the History of Logic, ISBN 978-0-444-50334-3, Elsevier 
• Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972), What is mathematical logic?, ISBN 0-19-888087-1, London-Oxford-New York: Oxford University Press, pp. 59–60, 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), Model theory, ISBN 978-0-521-30442-9, Cambridge: Cambridge Univ. Pr. 
• Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, ISBN 978-0-387-98655-5, Berlin, New York: Springer 

Ligações externas[editar | editar código-fonte]

• Sakharov, Alex and Weisstein, Eric W. «Löwenheim-Skolem Theorem» (em inglês). MathWorld  !CS1 manut: Nomes múltiplos: lista de autores (link)
• Burris, Stanley N., Contributions of the Logicians, Part II, From Richard Dedekind to Gerhard Gentzen
• Burris, Stanley N., Downward Löwenheim–Skolem theorem
• Simpson, Stephen G. (1998), Model Theory