Teoremas da Compacidade e de Loewenheim-Skolem

Os teoremas da compacidade e de Loewenheim-Skolem são os dois resultados fundamentais que governam quais estruturas as teorias de primeira ordem podem descrever, revelando tanto o poder quanto as limitações inerentes da lógica de primeira ordem.

Definition

O teorema da compacidade afirma que um conjunto de sentenças de primeira ordem é satisfatível se e somente se cada subconjunto finito o for; os teoremas de Loewenheim-Skolem afirmam que qualquer teoria de primeira ordem com um modelo infinito possui modelos em toda cardinalidade infinita pelo menos igual à de sua linguagem.

Scope

Este tópico abrange o teorema da compacidade e sua prova via completude ou ultraprodutos, os teoremas descendente e ascendente de Loewenheim-Skolem sobre as cardinalidades dos modelos, suas consequências padrão, incluindo a existência de modelos não-padrão da aritmética e da análise, e o paradoxo de Skolem.

Core questions

• Por que a satisfatibilidade finita de uma teoria garante um modelo?
• Como esses teoremas produzem modelos não-padrão da aritmética e dos reais?
• Por que nenhuma teoria de primeira ordem pode caracterizar uma estrutura infinita até a cardinalidade?
• O que é o paradoxo de Skolem e como ele é resolvido?

Key theories

Teorema da compacidade

Se cada subconjunto finito de um conjunto de sentenças tem um modelo, então o conjunto inteiro tem um modelo; isso decorre da completude ou pode ser provado semanticamente com ultraprodutos.

Teorema descendente de Loewenheim-Skolem

Qualquer estrutura infinita tem uma subestrutura elementar de cardinalidade no máximo igual à de sua linguagem, de modo que teorias contáveis com modelos infinitos têm modelos contáveis.

Teorema ascendente de Loewenheim-Skolem

Qualquer modelo infinito pode ser estendido elementarmente para modelos de toda cardinalidade maior, de modo que as teorias de primeira ordem não podem fixar o tamanho de seus modelos infinitos.

Clinical relevance

Esses teoremas são os pilares da teoria dos modelos: a compacidade é usada para construir modelos não-padrão que provam ou transferem resultados, e os teoremas de Loewenheim-Skolem explicam por que as axiomatizações de primeira ordem dos números naturais ou dos reais sempre admitem modelos não intencionais, moldando a escolha dos frameworks lógicos.

History

Loewenheim provou uma versão do teorema descendente em 1915 e Skolem a generalizou e a aprimorou ao longo da década de 1920. A compacidade foi obtida por Goedel como um corolário da completude e estendida para linguagens não contáveis por Maltsev, que a explorou pela primeira vez para derivar teoremas algébricos, abrindo caminho para a teoria dos modelos aplicada.

Key figures

• Leopold Loewenheim
• Thoralf Skolem
• Kurt Goedel
• Anatoly Maltsev

Seminal works

• changkeisler1990
• marker2002
• hodges1993

Frequently asked questions

O que é um modelo não-padrão da aritmética?

Pela compacidade, pode-se adicionar aos axiomas da aritmética uma constante maior do que cada numeral; a teoria consistente resultante tem um modelo contendo elementos infinitos além dos números naturais padrão. Tais modelos satisfazem exatamente as mesmas sentenças de primeira ordem que o modelo padrão.

O que é o paradoxo de Skolem?

O teorema descendente de Loewenheim-Skolem fornece um modelo contável da teoria dos conjuntos, embora essa teoria prove que existem conjuntos não contáveis. A resolução é que a não-contabilidade é relativa ao modelo: um conjunto que o modelo considera não contável não tem uma bijeção com os naturais dentro do modelo, embora uma exista externamente.