Essa lista pressupõe um conhecimento básico sobre modelos. Talvez seja interessante ver a seguinte [[lista:modelos|lista]]. ===== O Jogo de Ehrenfeucht ===== Dadas $L$ e $L'$ vocabulários, dizemos que $L'$ é uma //expansão// de $L$ se $L \subset L'$. \\ Se $L' \setminus L$ consiste apenas de símbolos de constantes, dizemos que $L'$ é uma //expansão simples// de $L$. Sendo $\mathcal{A}$ um $L$-modelo e $\mathcal{B}$ $L'$-modelo de modo que $A=B$, dizemos que $\mathcal{B}$ é uma $L'$-expansão de $\mathcal{A}$ Seja $\mathcal{A}$ um $L$-modelo e $L'=L \cup \{\textbf{c}_1,\textbf{c}_2,...,\textbf{c}_n\}$. Denota-se como a expansão simples de $\mathcal{A}$ que interpreta $\textbf{c}_i$ como $a_i$ $\left( \mathcal{A}, a_1, a_2,..., a_n\right)$. Sejam $\mathcal{A}$ e $\mathcal{B}$ $L$-modelos, $a_1,...,a_n \in A$ e $b_1,...,b_n \in B$. Dizemos que $\{(a_1,b_1),...,(a_n,b_n)\}$ é um isomorfismo local entre $\mathcal{A}$ e $\mathcal{B}$ se as expansões simples $(\mathcal{A},a_1,...,a_n)$ e $(\mathcal{B},b_1,...,b_n)$ satisfazem as mesmas fórmulas atômicas. **~~#~~** Mostre que $\{(2,e),(8, \pi),(-5,0)\}$ é um isomorfismo local entre $(\mathbb{Z},<)$ e $(\mathbb{R},<)$. **~~#~~** Defina sobre $\mathbb{C}$ uma relação $\prec$ de modo que $\forall n \in \mathbb{N} \ \{(1,1-i),(2,2+2i),...,(n,+(-1)^n n \cdot i)\}$ seja um isomorfismo local entre $(\mathbb{N},<)$ e $(\mathbb{C},\prec)\}$ **~~#~~** Mostre que todo isomorfismo local é uma injeção. Dados os modelos $\mathcal{A}$ e $\mathcal{B}$, chamamos de {{entry> jogo/ de Ehrenfeucht;jogo de Ehrenfeucht}} o seguinte jogo finito (de tamanho $n$) entre os jogadores I e II, denotado por $E(\mathcal{A},\mathcal{B},n)$: * Na i-ésima rodada, $1 \leq i \leq n$, o jogador I escolhe um elemento $a_i \in A$ ou $b_i \in B$ * Então, o jogador II escolhe $a_i \in A$ caso o jogador tenha escolhido $b_i \in B$ ou escolhe $b_i \in B$, caso contrário. O jogador II ganha, denota-se $II \uparrow (\mathcal{A},\mathcal{B},n)$, se $\{(a_1,b_1),...,(a_n,b_n)\}$ é um isomorfismo local entre as expansões simples $\mathcal{A}$ e $\mathcal{B}$ **~~#~~** Diga se o jogador I ou o jogador II tem estratégia vencedora nos casos que seguem: $E(\mathbb{Z},\mathbb{Q},n)$, $E(\mathbb{N},\mathbb{Z},n)$, $E(\mathbb{Q},\mathbb{B},n)$, para $n=2$ e $n=3$. Há aqui um abuso de notação. Com $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ dizemos esses conjuntos com as ordens usuais. **~~#~~** Sejam $\mathcal{A}=(A,R)$ e $\mathcal{B}=(B,S)$. Sejam $\mathcal{A}$ e $\mathcal{B}$ modelos para $L$. Mostre que: **~~#.#~~** Se $II \uparrow (\mathcal{A}, \mathcal{B}, 2)$ e $R^{\mathcal{A}}$ é simétrica, então $R^{\mathcal{B}}$ é simétrica. **~~#.#~~** Se $II \uparrow (\mathcal{A}, \mathcal{B}, 3)$ e $R^{\mathcal{A}}$ é transitiva, então $R^{\mathcal{B}}$ é transitiva. **~~#.#~~** Se $II \uparrow (\mathcal{A}, \mathcal{B}, 3)$ e $R^{\mathcal{A}}$ é densa, então $R^{\mathcal{B}}$ é densa. (uma relação é densa se $aRb \Rightarrow \exists c \ aRc \land cRb$) **~~#~~** Mostre que se $II \uparrow (\mathcal{A}, \mathcal{B}, n)$ e $II \uparrow (\mathcal{B}, \mathcal{C}, n)$, então $II \uparrow (\mathcal{A}, \mathcal{C}, n)$ Você pode dar sequência a esses exercícios vendo a lista [[lista:nequivalencia|o Jogo de Ehrenfeucht e a $n$-equivalência]].