# 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$_1$, …, a$_n$) com parâmetros a$_1$, …, 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$_1$, …, 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$_1$, …, x$_n$) com variáveis livres x$_1$, …, x$_n$, e todos os elementos a$_1$, …, a$_n$ de N, φ(a$_1$, …, a$_n$) está em N se e somente se está em M:
    N $\models$ φ(a$_1$, …, a$_n$) sse M $\models$ φ(a$_1$, …, 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$_1$, …, y$_n$) sobre σ e todos os elementos b$_1$, …, b$_n$ de N, se M $\models$ x φ(x, b$_1$, …, b$_n$), então existe um elemento a em N tal que M $\models$φ(a, b$_1$, …, 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$_1$, …, x$_n$) e todos os elementos a$_1$, …, a$_n$ de N,
    N $\models$ φ(a$_1$, …, a$_n$) implica M $\models$ φ(h(a$_1$), …, 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.