Teorema da compactação - Compactness theorem

Na lógica matemática , o teorema da compacidade afirma que um conjunto de sentenças de primeira ordem tem um modelo se e somente se cada subconjunto finito dele tem um modelo. Este teorema é uma ferramenta importante na teoria de modelos , pois fornece um método útil (mas geralmente não eficaz) para construir modelos de qualquer conjunto de sentenças que seja finitamente consistente .

O teorema da compactação para o cálculo proposicional é uma consequência do teorema de Tychonoff (que diz que o produto de espaços compactos é compacto) aplicado a espaços de Stone compactos , daí o nome do teorema. Da mesma forma, é análogo à caracterização da propriedade de interseção finita de compactação em espaços topológicos : uma coleção de conjuntos fechados em um espaço compacto tem uma interseção não vazia se cada subcoleção finita tem uma interseção não vazia.

O teorema da compactação é uma das duas propriedades principais, junto com o teorema de Löwenheim – Skolem descendente , que é usado no teorema de Lindström para caracterizar a lógica de primeira ordem. Embora existam algumas generalizações do teorema da compactação para lógicas não de primeira ordem, o teorema da compactação em si não se aplica a elas, exceto por um número muito limitado de exemplos.

História

Kurt Gödel provou o teorema da compactação contável em 1930. Anatoly Maltsev provou o caso incontável em 1936.

Formulários

O teorema da compactação tem muitas aplicações na teoria de modelos; alguns resultados típicos são esboçados aqui.

O teorema da compactação implica o princípio de Robinson : Se uma sentença de primeira ordem vale para todos os campos de característica zero, então existe uma constante p tal que a frase vale para todos os campos de características maiores que p . Isso pode ser visto da seguinte forma: suponha que φ seja uma sentença válida em todos os campos da característica zero. Então, sua negação ¬φ, juntamente com os axiomas de campo e a sequência infinita de sentenças 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0, ..., não é satisfatória (porque não há campo de característica 0 em que ¬φ é válido , e a sequência infinita de sentenças garante que qualquer modelo seria um campo de característica 0). Portanto, há um subconjunto finito A dessas sentenças que não pode ser satisfeito. Podemos supor que A contém ¬φ, os axiomas de campo e, para alguns k , as primeiras k sentenças da forma 1 + 1 + ... + 1 ≠ 0 (porque adicionar mais sentenças não altera a insatisfação). Deixe B conter todas as sentenças de A, exceto ¬φ. Então, qualquer campo com uma característica maior que k é um modelo de B , e ¬φ junto com B não é satisfatório. Isso significa que φ deve ser válido em todo modelo de B , o que significa precisamente que φ é válido em todo campo de característica maior que k .

Uma segunda aplicação do teorema da compactação mostra que qualquer teoria que tenha modelos finitos arbitrariamente grandes, ou um único modelo infinito, tem modelos de cardinalidade grande arbitrária (este é o teorema Upward de Löwenheim-Skolem ). Assim, por exemplo, existem modelos não padronizados da aritmética de Peano com incontáveis ​​"números naturais". Para conseguir isso, seja T a teoria inicial e seja κ qualquer número cardinal . Adicione à linguagem de T um símbolo constante para cada elemento de κ. Em seguida, adicione a T uma coleção de sentenças que digam que os objetos denotados por quaisquer dois símbolos constantes distintos da nova coleção são distintos (esta é uma coleção de κ ² sentenças). Uma vez que cada subconjunto finito dessa nova teoria pode ser satisfeito por um modelo finito de T suficientemente grande , ou por qualquer modelo infinito, toda a teoria estendida é satisfatória. Mas qualquer modelo da teoria estendida tem cardinalidade de pelo menos κ

Uma terceira aplicação do teorema da compactação é a construção de modelos não padronizados dos números reais, ou seja, extensões consistentes da teoria dos números reais que contêm números "infinitesimais". Para ver isso, seja Σ uma axiomatização de primeira ordem da teoria dos números reais. Considere a teoria obtida adicionando um novo símbolo constante ε à linguagem e juntando a Σ o axioma ε> 0 e os axiomas ε <1 / n para todos os inteiros positivos n . Claramente, os números reais padrão R são um modelo para cada subconjunto finito desses axiomas, porque os números reais satisfazem tudo em Σ e, por escolha adequada de ε, podem ser feitos para satisfazer qualquer subconjunto finito dos axiomas sobre ε. Pelo teorema da compactação, existe um modelo * R que satisfaz Σ e também contém um elemento infinitesimal ε. Um argumento semelhante, axiomas adjacentes ω> 0, ω> 1, etc., mostra que a existência de inteiros infinitamente grandes não pode ser descartada por qualquer axiomatização Σ dos reais.

Provas

Pode-se provar o teorema da compactação usando o teorema da completude de Gödel , que estabelece que um conjunto de sentenças é satisfatório se e somente se nenhuma contradição puder ser provada a partir dele. Como as provas são sempre finitas e, portanto, envolvem apenas finitamente muitas das sentenças fornecidas, segue-se o teorema da compactação. Na verdade, o teorema da compactação é equivalente ao teorema da completude de Gödel, e ambos são equivalentes ao teorema do ideal primo Booleano , uma forma fraca do axioma da escolha .

Gödel originalmente provou o teorema da compacidade exatamente dessa maneira, mas mais tarde algumas provas "puramente semânticas" do teorema da compacidade foram encontradas, isto é, provas que se referem à verdade, mas não à provabilidade . Uma dessas provas depende de ultraprodutos que dependem do axioma de escolha da seguinte forma:

Prova: Fixe uma linguagem L de primeira ordem e seja Σ uma coleção de frases L de modo que toda subcoleção finita de frases L, i  ⊆ Σ dela tenha um modelo . Seja também o produto direto das estruturas e I seja a coleção de subconjuntos finitos de Σ. Para cada i em , deixe A _i  : = { j ∈ I  : j ⊇ i }. A família de todos esses conjuntos A _i gera um filtro apropriado , então existe um ultrafiltro U contendo todos os conjuntos da forma A _i . ${\ displaystyle {\ mathcal {M}} _ {i}}$${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i}}$

Agora, para qualquer fórmula φ em Σ temos:

• o conjunto A _{φ} está em U
• sempre que j  ∈ A _{φ} , então φ ∈  j , portanto φ é válido ${\ displaystyle {\ mathcal {M}} _ {j}}$
• o conjunto de todo j com a propriedade que φ mantém em é um superconjunto de A _{φ} , portanto, também em U${\ displaystyle {\ mathcal {M}} _ {j}}$

Usando o teorema de Łoś , vemos que φ é válido no ultraproduto . Portanto, este ultraproduto satisfaz todas as fórmulas em Σ. ${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i} / U}$

Veja também

• Teorema da compactação de Barwise
• Teorema de Herbrand
• Lista de tópicos de álgebra booleana  - artigo da lista da Wikimedia
• Teorema de Löwenheim – Skolem  - Teorema matemático

Notas

Referências

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computabilidade e lógica (quarta edição). Cambridge University Press.
• Chang, CC; Keisler, H. Jerome (1989). Teoria do modelo (terceira ed.). Elsevier. ISBN   0-7204-0692-7 .
• Dawson, John W. junior (1993). "A compactação da lógica de primeira ordem: De Gödel a Lindström". História e filosofia da lógica . 14 : 15–37. doi : 10.1080 / 01445349308837208 .
• Hodges, Wilfrid (1993). Teoria do modelo . Cambridge University Press. ISBN   0-521-30442-3 .
• Marker, David (2002). Teoria do modelo: uma introdução . Textos de Pós-Graduação em Matemática 217. Springer. ISBN   0-387-98760-6 .
• Truss, John K. (1997). Fundamentos da Análise Matemática . Imprensa da Universidade de Oxford. ISBN   0-19-853375-6 .