Equivalência elementar

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 φ(a1, …, an) com parâmetros a1, …, an 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 hN → 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 φ(xb1, …, bn) 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 φ(x1, …, xn) com variáveis livres x1, …, xn, e todos os elementos a1, …, an de N, φ(a1, …, an) está em N se e somente se está em M:

N \models φ(a1, …, an) sse M \models φ(a1, …, an).

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[editar | editar código-fonte]

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 φ(xy1, …, yn) sobre σ e todos os elementos b1, …, bn de N, se M \models Predefinição:Existx φ(xb1, …, bn), então existe um elemento a em N tal que M \modelsφ(ab1, …, bn).

Imersões elementares[editar | editar código-fonte]

Uma imersão elementar de uma estrutura N em uma estrutura M de mesma assinatura σ é uma função hN → M tal que para toda σ-fórmula de primeira ordem φ(x1, …, xn) e todos os elementos a1, …, an de N,

N \models φ(a1, …, an) implica M \models φ(h(a1), …, h(an)).

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[editar | editar código-fonte]