====== Relações entre modelos ======

<WRAP info>
Dizemos que dois L-modelos $\mathcal{M}$ e $\mathcal{N}$ são isomorfos ($\mathcal{M} \cong \mathcal{N}$) se existe uma bijeção $h: M \rightarrow N$ tal que:

- para todo símbolo relacional R e $a_1,...,a_n \in M$, temos que $R^{\mathcal{M}}(a_1,...,a_n)$ se, e somente se, $R^{\mathcal{N}}(h(a_1),...,h(a_n))$.

- para todo símbolo funcional $f$ e $a_1,...,a_n \in M$, temos que $h(f^{\mathcal{M}}(a_1,...,a_n)) = f^{\mathcal{N}}(h(a_1),...,h(a_n))$

- para toda constante c, temos que $h(c^{\mathcal{M}}) = c^{\mathcal{N}}$

Dizemos que $h$ é um homomorfismo se satisfaz a segunda e a terceira propriedade mais a ida da primeira. 
</WRAP>

<WRAP info>
Dizemos que dois modelos $\mathcal{M}$ e $\mathcal{N}$ são equivalentes ($\mathcal{M} \equiv \mathcal{N}$) se, para toda L-fórmula $\varphi$, temos que $\mathcal{M} \vDash \varphi$ se, e somente se, $\mathcal{N} \vDash \varphi.$
</WRAP>

**~~#~~** Seja $h: M \rightarrow N$ um isomorfismo entre $\mathcal{M}$ e $\mathcal{N}$. Mostre que, dado $t$ termo, $\varphi$ fórmula e $\alpha$ valoração, temos:


**~~#.#~~** $h(t^{\mathcal{M}}[\alpha]) = t^{\mathcal{N}}[h \circ \alpha]$ 

**~~#.#~~** $\mathcal M \models \varphi[\alpha]$ se, e somente se, $\mathcal{N} \vDash \varphi[h \circ \alpha]$

**~~#~~** Utilizando o resultado anterior mostre que, se $\mathcal{M} \cong \mathcal{N}$, então $\mathcal{M} \equiv \mathcal{N}$.<wrap help>[[solucao:modeloFinito|Solução]]</wrap>

**~~#~~** Mostre que se $\mathcal{M}$ é finito, então vale a volta. 

**~~#~~** Mostre que se $\mathcal{M}$ for infinito então a volta não vale. <wrap tip>[[dica:Mequivnotiso|Dica]]</wrap>

==== Submodelos Elementares ====
<WRAP info>
Dizemos que $\mathcal{M}$ é um submodelo de $\mathcal{N}$ ($\mathcal{M} \subset \mathcal{N}$) se:

- $M \subset N$

- $R^{\mathcal{M}} = R^{\mathcal{N}} \cap M^n$ se $R$ é uma relação $n$-ária. 

- $f^{\mathcal{M}} = f^{\mathcal{N}} \upharpoonright M^n$ se $f$ é uma função $n$-ária.

- $c^{\mathcal{M}} = c^{\mathcal{N}}$ se $c$ é um símbolo constante. 

</WRAP>
**~~#~~** Mostre que $(\mathbb{N},+,.,<,0,1)$ é submodelo de $(\mathbb{Q},+,.,<,0,1)$, que por sua vez é submodelo de $(\mathbb{R},+,.,<,0,1)$. 

**~~#~~** Sejam $\mathcal{M} \subset \mathcal{N}$ e $\alpha$ uma valoração em $\mathcal{M}$. Mostre que:

**~~#.#~~** para todo termo $t, t^{\mathcal{M}}[\alpha] = t^{\mathcal{N}}[\alpha]$.

**~~#.#~~** se $\varphi$ é uma fórmula sem quantificadores, $\mathcal{M} \vDash \varphi[\alpha]$ se, e somente se, $\mathcal{N} \vDash \varphi[\alpha]$. 
 
**~~#.#~~** Dê um exemplo mostrando que a hipótese de "sem quantificadores" é necessária.

<WRAP info> 

Dizemos que $\mathcal{M}$ é um submodelo elementar de $\mathcal{N}$ ($\mathcal{M} \prec \mathcal{N}$) se $\mathcal{M} \subset \mathcal{N}$ e, para toda valoração $\alpha$ sobre $\mathcal{M}$, temos que $\mathcal{M} \vDash \varphi[\alpha]$ se, e somente se, $\mathcal{N} \vDash \varphi[\alpha]$ para toda fórmula $\varphi$.  

</WRAP>

**~~#~~** (Critério de Tarski) Suponha que $\mathcal{M} \subset \mathcal{N}$ e que, para toda fórmula $\varphi(x_1,...,x_n)$ e todo $a_1,...,a_{n-1} \in M$, temos que $\mathcal{N} \vDash \exists x_n \varphi[a_1,...,a_{n-1}, x_n]$ implica que existe $a \in M$ tal que $\mathcal{N} \vDash \varphi[a_1,...,a_{n-1},a]$. Prove que $\mathcal{M}$ é submodelo elementar de $\mathcal{N}$. <wrap tip>[[dica:CritTarski|Dica]]</wrap>

**~~#~~** Seja $\mathcal{N}$ um L-modelo. Sejam $X \subset N$ e $\kappa$ cardinal tais que $\aleph_0$, $|L|$, $|X| \leq \kappa \leq |N|$. Mostre que existe submodelo $\mathcal{M} \subset \mathcal{N}$ tal que $X \subset M$ e $|M| = \kappa$.

**~~#~~** (Löweinheim-Skolem-Tarkski para baixo) Seja $\mathcal{N}$ um L-modelo. Sejam $X \subset N$ e $\kappa$ cardinal tais que $\aleph_0$, $|L|$, $|X| \leq \kappa \leq |N|$. Mostre que existe um submodelo elementar $\mathcal{M} \prec \mathcal{N}$ tal que $X \subset M$ e $|M| = \kappa$. <wrap tip>[[dica:LSTip|Dica]]</wrap>

**~~#~~** Mostre que $(\mathbb{Q},<) \prec (\mathbb{R},<)$ (Note que isso significa que a existência de supremo para conjuntos limitados não é possível de ser expressa por fórmulas como apresentadas aqui).<wrap tip>[[dica:QsubmodelR|Dica]]</wrap>