Topologia e conjuntos em exercícios

<WRAP info>
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<b$ ou $b<a$.
</WRAP>

**~~#~~** 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$

<WRAP info>
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$.
</WRAP>

**~~#~~** 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?

<WRAP info>
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.
</WRAP>

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

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

**~~#.#~~** Escolha $m \in \zeta$ e $n$ o sucessor de $m$.

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

**~~#.#~~** Conclua que $Q$ não é definível em primeira ordem.

**~~#~~** 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.

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

<WRAP info>
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))$.
</WRAP>

**~~#~~** 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.
Topologia e conjuntos em exercícios

Ferramentas do usuário

Ferramentas do site

Ferramentas da página
