Equivalência elementar

Na teoria dos modelos, uma vertente da lógica matemática, duas estruturas M and N da mesma assinatura σ são chamadas elementarmente equivalentes se elas satisfazem as mesmas σ-sentenças de primeira ordem.

Se N é uma subestrutura de M, é preciso de uma condição mais forte. Nesse caso N é chamada de subestrutura elementar de M se toda σ-formula de primeira ordem φ(a₁, …, a_n) com parâmetros a₁, …, a_n de N é verdade em N se e somente se for verdade em M. Se N é uma subestrutura elementarde M, M é chamada uma extensão elementar de N. Uma imersão h: N → M é chamada de imersão elementar de N em M se h(N) é uma subestrutura elementar de M.

Uma subestrutura N de M é elementar se e somente se ela passa no Tarski-Vaught test: Toda fórmula de primeira ordem φ(x, b₁, …, b_n) com parâmetros em N que tem uma solução em M também tem uma solução em N quando avaliadas em M. É possível provar que duas estruturas são elementares equivalentes com os jogos de Ehrenfeucht–Fraïssé.

Estruturas elementarmente equivalentes

Duas estruturas M e N da mesma assinatura σ são elementarmente equivalentes se toda sentença de primeira ordem (fórmula sem variáveis livres) sobre σ é verdade em M se e somente se é verdade em N, i.e. se M e N tem a mesma teoria de primeira ordem completa. Se M e N são elementarmente equivalentes, escreve-se M ≡ N.

Uma teoria de primeira ordem é completa se e somente se qualquer dois dos seus modelos são elementarmente equivalentes.

Por exemplo, considere a linguagem com uma relação binária de símbolo '<'. O modelo R de números reais com sua ordem usual a o modelo Q de números racionais com sua ordem usual são elementarmente equivalentes, uma vez que ambos interpretam '<' como uma relação de ordem sem limites. Isso é suficiente para assegurar a equivalência elementar, porque a teoria da relação de ordem sem limites é completa, como pode ser mostrado pelo teste de Vaught.

Mais geralmente, qualquer teoria de primeira ordem tem modelos não-isomórficos, elementarmente equivalentes, que podem ser obitidos via o Teorema Löwenheim–Skolem. Assim, por exemplo, existem modelos não-padrão da aritmética de Peano, que contém outros objetos além dos números 0, 1, 2, etc., e ainda são elementarmente equivalentes para o modelo padrão.

Subestruturas equivalentes e extensões equivalentes

N é uma subestrutura elementar de M se N e M são estruturas das mesma assinatura σ de forma que para todas as σ-fórmulas de primeira ordem φ(x₁, …, x_n) com variáveis livres x₁, …, x_n, e todos os elementos a₁, …, a_n de N, φ(a₁, …, a_n) está em N se e somente se está em M:

N $\models$ φ(a₁, …, a_n) sse M $\models$ φ(a₁, …, a_n).

Segue-se que N é uma subestrutura de M.

Se N é uma subestrutura de M, assim ambos N e M podem ser interpretados como estruturas na assinatura σ_N consistindo de σ juntamente com um símbolo constante para cada elemento de N. N é uma subestrutura elementar de M se e somente se N se a subestrutura de M e N e M são elementarmente equivalentes como σ_N-estruturas.

Se N é um elemento estrutura de M, escreve-se N $\preceq$ M e diz-se que M é uma extensão elementar de N: M $\succeq$ N.

A sessão Top-Down do teorema de Löwenheim–Skolem dá contáveis subestruturas elementares para todo qualquer estrutura de primeira ordem finita; a sessão Down-Top do teorema dá extensões elementares de qualquer estrutura de primeira ordem infinita de cardinalidade arbitrariamente larga.

O teste Tarski–Vaught

O teste Tarski-Vaught é uma condição necessária e suficiente para uma subestrutura N de uma subestrutura M ser uma subestrutura elementar. Pode ser útil para construir uma subestrutura elementar de uma estrutura grande.

Seja M uma estrutura de assinatura σ e N uma subestrutura de M. N é uma subestrutura elementar de M se e somente se para toda fórmula de primeira ordem φ(x, y₁, …, y_n) sobre σ e todos os elementos b₁, …, b_n de N, se M $\models$ x φ(x, b₁, …, b_n), então existe um elemento a em N tal que M $\models$φ(a, b₁, …, b_n).

Imersões elementares

Uma imersão elementar de uma estrutura N em uma estrutura M de mesma assinatura σ é uma função h: N → M tal que para toda σ-fórmula de primeira ordem φ(x₁, …, x_n) e todos os elementos a₁, …, a_n de N,

N $\models$ φ(a₁, …, a_n) implica M $\models$ φ(h(a₁), …, h(a_n)).

Todsa imersão elementar é um homomorfismo forte, e sua imagem é uma subestrutura elementar.

Imersões elementares são as funções mas importantes na teoria dos modelos. Na teoria dos conjuntos, imersões elementares cujos domínios são U (o universo da teoria dos conjuntos) têm um papel importante na teoria dos grandes cardinais.

Referências

• Chang, Chen Chung; Keisler, H. Jerome (1990) [1973], Model Theory, ISBN 978-0-444-88054-3, Studies in Logic and the Foundations of Mathematics 3rd ed. , Elsevier .
• Hodges, Wilfrid (1997), A shorter model theory, ISBN 978-0-521-58713-6, Cambridge: Cambridge University Press .
• Monk, J. Donald (1976), Mathematical Logic, ISBN 0-387-90170-1, Graduate Texts in Mathematics, New York • Heidelberg • Berlin: Springer Verlag