==== O Jogo de Ehrenfeucht e a $n$-equivalência ====

<WRAP info>
Dada uma fórmula $\varphi$, definimos o seu rank de quantificadores, denotado $qr(\varphi)$ como:
  * Se $\varphi$ é atômica, $qr(\varphi)=0$
  * $qr(¬\varphi)=qr(\varphi)$
  * $qr(\varphi \wedge \psi)=\max \{ \varphi , \psi \}$
  * $qr(\exists x \varphi)=qr(\varphi)+1$

Dizemos que dois $L$-modelos $\mathcal{A}$ e $\mathcal{B}$ são $n$-equivalentes, denota-se $\mathcal{A} \equiv ^n\mathcal{B}$ se satisfazem as mesmas fórmulas de rank menor ou igual a $n$
</WRAP>

Os exercícios a seguir são um roteiro para mostrar que $II \uparrow (\mathcal{A},\mathcal{B},n) \Leftrightarrow \mathcal{A} \equiv ^n \mathcal{B}$.

**~~#~~** Mostre que $II \uparrow (\mathcal{A}, \mathcal{B}, n+1)$ é equivalente às condições:
  * $\forall a \in A \ \exists \, b \in B$ tal que $II \uparrow((\mathcal{A},a),(\mathcal{B},b),n)$
  * $\forall b \in B \ \exists \, a \in A$ tal que $II \uparrow((\mathcal{A},a),(\mathcal{B},b),n)$

**~~#~~** Mostre que se $\mathcal{A}$ e $\mathcal{B}$ satisfazem as mesmas fórmulas atômicas, então $\mathcal{A}$ e $\mathcal{B}$ satisfazem as mesmas fórmulas de rank $0$, isto é, satisfazem as mesmas fórmulas sem quantificadores.

**~~#~~** Mostre que $\mathcal{A} \equiv ^0 \mathcal{B} \Leftrightarrow II \uparrow (\mathcal{A},\mathcal{B},0)$

**~~#~~** Suponha para dado $n$ que $\mathcal{A} \equiv ^n \mathcal{B} \Leftrightarrow II \uparrow (\mathcal{A},\mathcal{B},n)$ e $II \uparrow (\mathcal{A}, \mathcal{B}, n+1)$ para mostrar que, se $\varphi$ tem rank $n$ e $\mathcal{A} \models \exists x \varphi$, então $\mathcal{B} \models \exists x \varphi$  <wrap help>[[solucao:nequiv4 | Solução]]</wrap>

**~~#~~** Mostre que $\mathcal{A} \equiv ^n \mathcal{B} \Rightarrow II \uparrow (\mathcal{A}, \mathcal{B}, n)$

**~~#~~** Complete a prova de $\mathcal{A} \equiv ^n \mathcal{B} \Leftrightarrow II \uparrow (\mathcal{A}, \mathcal{B}, n)$

**~~#~~** Sejam $\mathcal{A}$ e $\mathcal{B}$ ordens. Mostre que $II \uparrow (\mathcal{A}, \mathcal{B}, n+1)$ é equivalente a:
  * $\forall a \in A \ \ \exists b \in B \ \ II \uparrow (\uparrow a, \uparrow b, n) \wedge II (\downarrow a, \downarrow b, n)$
  * $\forall b \in B \ \ \exists a \in A \ \ II \uparrow (\uparrow a, \uparrow b, n) \wedge II (\downarrow a, \downarrow b, n)$
Use o seguinte resultado: Se $\textbf{a}_1, \textbf{a}_2, \textbf{b}_1, \textbf{b}_2$ são ordens totais e $II \uparrow (\textbf{a}_1, \textbf{b}_1,n), II \uparrow (\textbf{a}_2, \textbf{b}_2, n)$, então $II \uparrow (\textbf{a}_1 +\textbf{a}_2, \textbf{b}_1 + \textbf{b}_2, n)$ (prove, também).

**~~#~~** Seja $\{ (a_1, b,_1),...,(a_k,b_k) \}$ um isomorfismo local entre $\mathcal{A}$ e $\mathcal{B}$. Então, são equivalentes:
  * Se $\varphi$ é uma fórmula de rank $\leq n$, então $\mathcal{A} \models \varphi [a_1,...,a_k] \Leftrightarrow \mathcal{B} \models \varphi [b_1,...,b_k]$
  * O jogador $II$ tem estratégia vencedora em $E(\mathcal{A}, \mathcal{B}, n)$ sendo que já foram feitas as jogadas $\{ (a_1, b,_1),...,(a_k,b_k) \}$

**~~#~~** Mostre que quaisquer duas ordens totais densas e limitadas satisfazem as mesmas fórmulas <wrap tip> [[dica:nequivalencia9 | Dica]] </wrap>