lista:nequivalencia

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

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$

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}$.

1 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)$

2 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.

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

4 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$ Solução

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

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

7 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).

8 Seja $\{ (a_1, b,_1),\ldots,(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,\ldots,a_k] \Leftrightarrow \mathcal{B} \models \varphi [b_1,\ldots,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),\ldots,(a_k,b_k) \}$

9 Mostre que quaisquer duas ordens totais densas e limitadas satisfazem as mesmas fórmulas Dica