Dado um modelo $\mathcal{M}$, definimos o //grafo de Gaifman de // $\mathcal{M}$, $\mathcal{G}(\mathcal{M})$, da seguinte forma: * O universo (vértices) de $\mathcal{G}(\mathcal{M})$ é $M$ (o mesmo do modelo) * Dois vértices $a$ e $b$ estão ligados por uma aresta se: - $a=b$ - Para alguma relação $n$-ária $R$, $a$ e $b$ aparecem em alguma $n$-upla $\overline{x}$ de modo que $\mathcal{M} \models R(\overline{x})$, isto é, $\overline{x} \in R^\mathcal{M}$. Por exemplo, se $\mathcal{M}$ é um modelo com a relação $<$, há uma aresta ligando $a$ a $b$ se $a=b$, $a **~~#~~** Descreva o grafo de Gaifman para cada um dos modelos a seguir: **~~#.#~~** $\mathcal{M}$ é um grafo orientado. **~~#.#~~** $\mathcal{M}$ é um grafo não orientado. **~~#.#~~** $\mathcal{M}$ é munido de uma ordem total. **~~#.#~~** $\mathcal{M}$ é $\mathbb{F}_p$ com a relação $R(x,y,z) \Leftrightarrow z=x+y$ **~~#.#~~** $\mathcal{M}$ é $\mathbb{F}_p$ com a relação $R(x,y,z) \Leftrightarrow z=xy$ Seja $\mathcal{M}$ um $L$-modelo. Dado $a \in M$ e $r \in \mathbb{N}$, definimos $B_r(a) = \{ x \in M : d(x,a) < r\}$, em que $d$ é a distância no grafo $\mathcal{G}(\mathcal{M})$. Acrescentando uma nova constante $\mathbf{c}$ à linguagem $L$, definimos o modelo $\mathcal{N}_r(a)$: * O universo é $B_r(a)$; * Cada relação é interpretada como a restrição das relações a $B_r(a)$; * $\mathbf{c}$ é interpretada como $a$. **~~#~~** Seja $A$ um grafo conexo e $B$ um grafo não conexo. Mostre que, se não há um mergulho de $A$ em $B$, então existe $r \in \mathbb{N}, a \in A, b \in B$ tais que $II \uparrow G(N_r(a),N_r(b),r)$. Como podemos enfraquecer essa hipótese? **~~#~~** Dê um exemplo de grafos $\mathcal{A}$ e $\mathcal{B}$ não isomorfos de modo que, para qualquer $r$, $a \in A$ e $b \in B$, $N_r(a)$ e $N_r(b)$ são isomorfos. **~~#~~** Escrevemos $\mathcal{A} \rightleftarrows_r \mathcal{B}$ quando existe uma bijeção $f: A \rightarrow B$ tal que para todo $c \in A$, $N_r(c) \cong N_r(f(c))$. Dê um exemplo de grafos não isomorfos em que isso acontece. Qual a diferença em relação ao exercício anterior? Chamamos $Q$ uma $k$-propriedade sobre um modelo $\mathcal{M}$ quando $Q$ define um subconjunto de $M^k$. - O conjunto dos números pares em $\mathbb{N}$ é uma $1$-propriedade; - Os pares de números relativamente primos é uma $2$-propriedade; - Conexidade de grafos é uma 0-propriedade (ou propriedade Booleana). Isso ocorre pois $M^0$ é um conjunto com um elemento apenas, assim $Q(\mathcal{M})$ leva $\mathcal{M}$ em um subconjunto de $M^0$, portanto, há dois elementos. Assim, $Q$ decide se essa propriedade é verdadeira ou não em todo $M$. Propriedades são mantidas em modelos isomorfos. **~~#~~** Seja $\omega = \{ \mathbb{N}, < \}$. Seja $Q$ a $1$-propriedade que define os números pares. **~~#.#~~** Suponha que existe uma fórmula de primeira ordem $\varphi(x)$ tal que $$x\in Q(\mathcal{M}) \Leftrightarrow \varphi(x)$$ **~~#.#~~**Escreva uma fórmula que diga que o sucessor de um número par é ímpar. **~~#.#~~** Considere $\zeta = \{ \mathbb{Z}, <\}$. Seja $\omega + \zeta$ a concatenação de $\omega$ e $\zeta$, em que $x < y$ se $x \in \omega, y \in \zeta$ ou $\omega \models x Podemos generalizar as definições anteriores para $n$-uplas de elementos. Considere $\overline{a}=(a_1,...,a_n)$: * $B_r(\overline{a}) = \{ x \in M \, : \, \underset{i \leq n}{\min} \{d(x,a_i)\} < r\}$; * $N_r(\overline{a})$ define-se da mesma forma com o universo $B_r(\overline{a})$, mas agora com $n$ novas constantes $\mathbf{c_1}^\mathcal{M}=a_1,...,\mathbf{c_n}^\mathcal{M}=a_n$; * $(\mathcal{A},\overline{a}) \rightleftarrows_r (\mathcal{B},\overline{b})$ quando existe uma bijeção $f: A \rightarrow B$ tal que, para todo $c \in A$, $N_r(a_1,...,a_n,c) \cong N_r(b_1,...,b_n,f(c))$. **~~#~~** Considere a propriedade $\mathcal{Q}$ sobre grafos que determina se um grafo contém ou não um clique (um conjunto de vértices em que todos são conectados entre si). Determine $d$ de modo que, se $\mathcal{A}$ contém um clique e $\mathcal{A} \rightleftarrows_r \mathcal{B}$, então $\mathcal{B}$ contém um clique.