lista:localidade

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:
1. $a=b$
2. 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<b$ ou $b<a$.

1 Descreva o grafo de Gaifman para cada um dos modelos a seguir:

1.1 $\mathcal{M}$ é um grafo orientado.

1.2 $\mathcal{M}$ é um grafo não orientado.

1.3 $\mathcal{M}$ é munido de uma ordem total.

1.4 $\mathcal{M}$ é $\mathbb{F}_p$ com a relação $R(x,y,z) \Leftrightarrow z=x+y$

1.5 $\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$.

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

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

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

5 Seja $\omega = \{ \mathbb{N}, < \}$. Seja $Q$ a $1$-propriedade que define os números pares.

5.1 Suponha que existe uma fórmula de primeira ordem $\varphi(x)$ tal que $$x\in Q(\mathcal{M}) \Leftrightarrow \varphi(x)$$

5.2Escreva uma fórmula que diga que o sucessor de um número par é ímpar.

5.3 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<y$ ou $\zeta \models x<y$. Mostre que, para todo $n$, $II \uparrow E(\omega, \omega + \zeta,n)$.

5.4 Conclua que $\omega + \zeta$ deve satisfazer a fórmula definida no item 2.

5.5 Escolha $m \in \zeta$ e $n$ o sucessor de $m$.

5.6 Mostre que existe um isomorfismo de $\omega + \zeta$ que leva $m$ em $n$. Obtenha uma contradição.

5.7 Conclua que $Q$ não é definível em primeira ordem.

6 Considere o modelo $\omega$ e escreva uma fórmula que diga “$x$ é o terceiro elemento”. Conclua que qualquer conjunto finito de $\omega$ é definível por uma fórmula de primeira ordem. Mostre, também, que qualquer conjunto co-finito é definível em primeira ordem.

7 Mostre que todo subconjunto de $\omega$ definível em primeira ordem é finito ou cofinito.

Podemos generalizar as definições anteriores para $n$-uplas de elementos. Considere $\overline{a}=(a_1,\ldots,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,\ldots,\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,\ldots,a_n,c) \cong N_r(b_1,\ldots,b_n,f(c))$.

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