Ferramentas do usuário
Ultraprodutos
Seja $X$ um conjunto. Dizemos que uma família não vazia $\mathcal F$ de subconjuntos de $X$ é um 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.
1 Dos exemplos abaixo, diga se $\mathcal F$ é filtro e se é ultrafiltro sobre $X$.
1.1 $X = \mathbb N$ e $A \in \mathcal F \Leftrightarrow \exists n \in \mathbb N \ A = \{ x \in \mathbb N : x>n \}$.
1.2 $X = \mathbb N$ e $A \in \mathcal F \Leftrightarrow \exists n \in \mathbb N \ A \supset \{ x \in \mathbb N : x>n \}$.
1.3 $X$ é infinito e $\mathcal F$ é a coleção dos subconjuntos cujo complementar é finito.
1.4 $a \in X$ e $\mathcal F = \{ A \subset X : a \in A \}$
2 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$.
3 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. Dica
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, \ldots , \vert m^k \vert ) = \vert t \vert \Leftrightarrow \{i \in I : \mathbf{f}^{\mathcal{M}_i}(m^1_i,m^2_i,\ldots,m^k_i) = t_i \} \in \mathcal{U}$;
- $\mathbf{r}^{\mathcal{M}^\ast}(\vert m^1 \vert , \ldots , \vert m^k \vert) \Leftrightarrow \{ i \in I : \mathbf{r}^{M_i}(m^1_i,\ldots,m^k_i) \} \in \mathcal{U}$.
4 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.
5 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:
5.1 $\mathcal M ^\ast \models \neg\varphi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \neg\varphi (m_i) \} \in \mathcal{U}$;
5.2 $\mathcal M ^\ast \models \varphi \lor \psi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \varphi \lor \psi (m_i)\} \in \mathcal{U}$;
5.3 $\mathcal M ^\ast \models \varphi \land \psi (|m|) \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \varphi \land \psi (m_i)\} \in \mathcal{U}$
6 Considere, agora, $\sigma = \exists x \ \varphi$.
6.1 Mostre que $\mathcal M ^\ast \models \sigma \Leftrightarrow \{ i \in I : \mathcal{M}_i \models \sigma \} \in \mathcal{U}$. Dica
6.2 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}$.
7 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,\ldots,a^k)$ uma fórmula, então $\mathcal{M}^\ast \models \varphi (|m^1|,\ldots,|m^k|) \Leftrightarrow \{i \in I : \mathcal{M}_i \models \varphi(m^1_i,\ldots,m^k_i) \} \in \mathcal{U}$.
8 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 Dica.
9 Conclua o Teorema da Compacidade: Uma teoria admite modelo se, e somente se, todo subconjunto finito dessa teoria admite modelo.
Ferramentas da página
