# Teorema de 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

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 $\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$^n$ 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$^n$.
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

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

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
### Parte descendente

Para cada $\sigma \,$-fórmula de primeira ordem $\varphi (y,x_{1},\ldots ,x_{n})\,,$o axioma da escolha implica a existência de uma função
    $f_{\varphi }:M^{n}\to M$
de tal modo que, para todos $a_{1},\ldots ,a_{n}\in M$, ou
    $M\models \varphi (f_{\varphi }(a_{1},\dots ,a_{n}),a_{1},\dots ,a_{n})$
ou
    $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 $\varphi$ para funções $f_{\varphi }\,.$
A família de funções $f_{\varphi }$ dá origem a um operador de pré-fecho $F\,$ no conjunto das partes de $M\,$
    $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 $A\subseteq M\,.$
Iteração $F\,$ contável muitas vezes resulta em um operador de fecho $F^{\omega }\,.$Tomar um subconjunto arbitrário $A\subseteq M$ tal que $\left\vert A\right\vert =\kappa$, e tendo definido $N=F^{\omega }(A)\,,$ percebe-se também que, $\left\vert N\right\vert =\kappa \,.$ $N\,$ é uma subestrutura elementar de $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 $f_{\varphi }$ na linguagem. Pode-se também definir o $f_{\varphi }$ funções parciais de modo a que $f_{\varphi }$ está definida, se e somente se $M\models \exists y\varphi (y,a_{1},\dots ,a_{n})\,.$ O único ponto importante é que $F\,$ é um operador de pré-fecho tal que $F(A)\,$ contém uma solução para cada fórmula com parâmetros $A\,$ que tem uma solução de $M\,$ e que:
    $\left\vert F(A)\right\vert \leq \left\vert A\right\vert +\left\vert \sigma \right\vert +\aleph _{0}\,.$

### Parte Ascendente

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

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).