===== Ultraprodutos =====

<WRAP info>
Seja $X$ um conjunto. Dizemos que uma família não vazia $\mathcal F$ de subconjuntos de $X$ é um {{entry>filtro}} sobre $X$ se
  - $\emptyset \notin \mathcal F$;
  - se $A, B \in \mathcal F$ então $A \cap B \in \mathcal F$;
  - se $A \in \mathcal F$ e $A \subset B$, então $B \in \mathcal F$.
Um ultrafiltro nada mais é que um filtro maximal, isto é, se $\mathcal{F}$ é um ultrafiltro sobre $X$, então $\mathcal F$ é um filtro com a propriedade de que, se $A \subset X$, então ou $A \in \mathcal F$ ou $X \setminus A \in \mathcal F$.

Intuitivamente, um ultrafiltro separa subconjuntos "grandes" de "pequenos". Pode ser útil enxergar a definição de ultrafiltro da seguinte forma. Um ultrafiltro é uma coleção de subconjuntos grandes, em que:
  - O conjunto vazio não é grande;
  - A interseção de dois subconjuntos grandes ainda é grande;
  - Se algum subconjunto grand está contido em outro, então este também é grande;
  - Todos os subconjuntos são, exclusivamente, ou grandes ou pequenos.
Veja que as três primeiras são a definição de filtro e a quarta é a condição adicional para ser ultrafiltro.

</WRAP>

**~~#~~** Dos exemplos abaixo, diga se $\mathcal F$ é filtro e se é ultrafiltro sobre $X$.

**~~#.#~~** $X = \mathbb N$ e $A \in \mathcal F \Leftrightarrow \exists n \in \mathbb N \ A = \{ x \in \mathbb N : x>n \}$.

**~~#.#~~** $X = \mathbb N$ e $A \in \mathcal F \Leftrightarrow \exists n \in \mathbb N \ A \supset \{ x \in \mathbb N : x>n \}$.

**~~#.#~~** $X$ é infinito e $\mathcal F$ é a coleção dos subconjuntos cujo complementar é finito.

**~~#.#~~** $a \in X$ e $\mathcal F = \{ A \subset X : a \in A \}$

**~~#~~** Mostre que todo filtro pode ser estendido a um ultrafiltro. Isto é, dado um conjunto $X$ e um filtro $\mathcal F$ sobre $X$, existe um ultrafiltro $\mathcal U$ sobre $X$ de modo que $\mathcal F \subset \mathcal U$.

**~~#~~** Seja $F$ um subconjunto de $\mathcal P (X)$ com a propriedade de que, se $A, B \in F$, então $A \cap B \in F$. Além disso, suponha que $\emptyset \not\in F$. Mostre que $F$ pode ser estendido a um filtro. <wrap tip> [[dica:ultra1|Dica]]</wrap>

<WRAP info>
Seja $L$ um vocabulário e $I$ um conjunto não vazio. Para cada $i \in I$, considere $M_i$ um modelo para $L$. Seja $\mathcal U$ um ultrafiltro sobre $I$. Definimos o ultraproduto dos $M_i$ por $\mathcal{U}$, e denotamos $\prod\limits_{i \in I} \mathcal{M}_i / \mathcal{U}$ ou simplesmente $M^\ast$, como segue:
  - O universo de $M^\ast$ é o produto $\prod\limits_{i \in I} M_i$ quocientado pela relação de equivalência $\sim$: Sejam $a = (a_i)_{i \in I}$ e $b = (b_i)_{i \in I} $, então $a \sim b \Leftrightarrow \{ i \in I : a_i = b_i \} \in \mathcal U$;
  - $\mathbf{c}^{\mathcal M ^\ast} = \vert ( \mathbf{c}^{\mathcal M _i})_{i \in I}) \vert$, em que as barras indicam a classe de equivalência;
  - $\mathbf{f}^{\mathcal M ^\ast} ( \vert m^1 \vert , \vert m^2 \vert, ... , \vert m^k \vert ) = \vert t \vert \Leftrightarrow \{i \in I : \mathbf{f}^{\mathcal{M}_i}(m^1_i,m^2_i,...,m^k_i) = t_i \} \in \mathcal{U}$;
  - $\mathbf{r}^{\mathcal{M}^\ast}(\vert m^1 \vert , ... , \vert m^k \vert) \Leftrightarrow \{ i \in I : \mathbf{r}^{M_i}(m^1_i,...,m^k_i) \} \in \mathcal{U}$.
</WRAP>

**~~#~~** Mostre que a interpretação dos símbolos de constante, função e relação está bem definida. Isto é, que independe da escolha do representante da classe.

**~~#~~** Sejam $\varphi = \varphi (a)$ e $\psi = \psi (a)$ fórmulas atômicas. Da definição, temos que $\mathcal M ^\ast \models \varphi \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \varphi \} \in \mathcal{U}$ e $\mathcal M ^\ast \models \psi \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \psi \} \in \mathcal{U}$. Mostre que:

**~~#.#~~** $\mathcal M ^\ast \models \neg\varphi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \neg\varphi (m_i) \} \in \mathcal{U}$;

**~~#.#~~** $\mathcal M ^\ast \models \varphi \lor \psi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \varphi \lor \psi (m_i)\} \in \mathcal{U}$;

**~~#.#~~** $\mathcal M ^\ast \models \varphi \land \psi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \varphi \land \psi (m_i)\} \in \mathcal{U}$

**~~#~~** Considere, agora, $\sigma = \exists x \ \varphi$.

**~~#.#~~** Mostre que $\mathcal M ^\ast \models \sigma \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \sigma \} \in \mathcal{U}$. <wrap tip>[[dica:ultra2 | Dica]]</wrap>

**~~#.#~~** Suponha, agora, que $\varphi = \varphi (a,b)$ e $\sigma (a) = \exists x \varphi (a,x)$. Mostre que $\mathcal M ^\ast \models \sigma (m) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \sigma (m) \} \in \mathcal{U}$.

**~~#~~** Use os exercícios anteriores e indução sobre fórmulas para escrever uma prova para o //Teorema de Łoś//: Dado $\mathcal{M}^\ast$ um ultraproduto e $\varphi$ uma sentença, então $\mathcal{M}^\ast \models \varphi \Leftrightarrow \{i \in I : \mathcal{M}_i \models \varphi \} \in \mathcal{U}$.

Na verdade, do que foi feito, podemos provar algo mais forte: Dado $\mathcal{M}^\ast$ um ultraproduto e $\varphi(a^1,...,a^k)$ uma fórmula, então $\mathcal{M}^\ast \models \varphi (|m^1|,...,|m^k|) \Leftrightarrow \{i \in I : \mathcal{M}_i \models \varphi(m^1_i,...,m^k_i) \} \in \mathcal{U}$. 

**~~#~~** Seja $T$ uma teoria. Suponha que todo subconjunto finito de $T$ admite modelo. Indicando por $\{ T_i \}_{i \in I}$ a coleção das subteorias finitas de $T$ e $\mathcal{M}_i$ um modelo para $T_i$, encontre um ultrafiltro $\mathcal{U}$ de modo que $\prod\limits_{i \in I} \mathcal{M}_i / \mathcal{U} \models T$. Use a <wrap tip>[[dica:ultra3 | Dica]]</wrap>.

**~~#~~** Conclua o //Teorema da Compacidade//: Uma teoria admite modelo se, e somente se, todo subconjunto finito dessa teoria admite modelo.