===== Modelos de Conjuntos =====

==== Imersões ====

<WRAP info>
Uma {{entry>Imersão}} de $\mathcal{M}$ em $ \mathcal{N} $ é um isomorfismo entre $ \mathcal{M} $ e um submodelo $ \mathcal{A} \subseteq \mathcal{N} $.\\
	
Se $ \mathcal{A} \prec \mathcal{N} $, chamamos a imersão de {{entry>imersão elementar}}.
</WRAP>




**~~#~~** Sejam $ \mathcal{M} $ e $ \mathcal{N} $ $ L $-modelos e $ h:M \to N $, são equivalentes: <wrap help>[[solucao:imersao1|Solução]]</wrap>
   - h é uma imersão (elementar).
   -  Para toda fórmula atômica $ \varphi $ (para toda $ \varphi $) e toda valoração $ \alpha $ em $ M $, $ \mathcal{M} \models \varphi[\alpha] \iff \mathcal{N} \models \varphi[h \circ \alpha] $.




<WRAP info>
Seja $ \kappa $ ordinal limite, $ L $ uma linguagem. Seja $ \mathcal{F} = \{ \mathcal{M}_{\xi} = (M_{\xi}, \cdot^{\mathcal{M_\xi}}) : \xi \in \kappa \} $ uma família de $ L $-modelos.
   - $ \mathcal{F} $ é uma {{entry>Cadeia}} ({{entry>Cadeia Elementar}}) se $ \xi < \gamma \implies $ $ \mathcal{M}_{\xi} \subseteq \mathcal{M}_{\gamma}(\mathcal{M}_{\xi} \prec \mathcal{M}_{\gamma}) $.
   - Seja $ M = \bigcup_{\xi \in \kappa} M_{\xi} $. Vamos definir $ \bigcup \mathcal{F} \doteq (M,\cdot^{\mathcal{M}}) $.
   - Tome $ f^{\mathcal{M}} \doteq \bigcup_{\xi \in \kappa} f^{\mathcal{M}_{\xi}} $.
   - Seja $ R^{\mathcal{M}} \doteq \bigcup_{\xi \in \kappa} R^{\mathcal{M}_{\xi}} $.
   - Seja $ c^{\mathcal{M}} = c^{\mathcal{M}_{0}} $.
</WRAP>





**~~#~~** Seja $\mathcal{F}$ cadeia (cadeia elementar) de $L$-modelos:

**~~#.#~~** Mostre que está bem definida $f^\mathcal{M}$

**~~#.#~~** Para qualquer que seja $ \xi \in \kappa $, dada a cadeia (elementar) acima e $ \mathcal{M} = \bigcup \mathcal{F} $, $ \mathcal{M}_{\xi} \subseteq \mathcal{M} $ ($ \mathcal{M}_{\xi} \prec \mathcal{M} $).






==== Modelos para conjuntos ====

Vamos assumir a linguagem $ L = \{\neg,\land,\to, \exists,=,\in, x_{0},...\} $ com apenas um símbolo relacional não lógico, $ \in $, e variáveis.\\

Para evitar ambiguidade quando necessário, para diferenciar entre a linguagem do modelo e a meta-linguagem do universo em que estamos trabalhando, usemos $ \overset{\text{meta}}{=} $ e $ \overset{\text{meta}}{\in} $.\\





<WRAP info>
   - Dizemos que $ \mathcal{M} = (M,\cdot^{\mathcal{M}}) $ é um $ L $-modelo **forma padrão** se, $ \mathcal{M} \models t \in s [\alpha] \iff \alpha(t) \overset{\text{meta}}{\in} \alpha(s) $.
   - $ \exists x \in t \phi $ abreviação para $ \exists x \,\, x \in t \land \phi $.
   - $\forall x \in t \phi $ abreviação para $ \forall x (x \in t \to \phi) $.
   - Chamamos $ \Delta_{0} $ a menor coleção de fórmulas que contém as atômicas, fechado por conectivos tal que $ \phi $ está em $ \Delta_{0} $ e $ t $ é termo,  então $ \exists x \in t \phi $, $  \forall x \in t \phi $ estão em $ \Delta_{0} $.
   - $ \mathcal{M} = (M,\cdot^{\mathcal{M}}) $ é transitivo se $ M $ é transitivo. ($ x \in M $ então $ x \subset M $)
</WRAP>



Note que estas são fórmulas onde todos os quantificadores estão ligados à uma variável que aparece relacionada por $ \in $ dentro da fórmula e que os termos são variáveis, visto que não existem funções e constantes na linguagem.\\




=== Absolutividade ===





<WRAP info>
   - Dizemos que $ \phi $ é {{entry>Absoluta Entre Modelos}} $ \mathcal{M} = (M,\cdot^{\mathcal{M}}) $ e $ \mathcal{N} = (N,\cdot^{\mathcal{N}}) $ se, e somente se, para toda valoração $ \alpha $  em $ M \cap N $ temos que $ \mathcal{M} \models \phi[\alpha] \iff \mathcal{N} \models \phi[\alpha] $.\\
   - $ \phi $ é {{entry>Absoluta}} se, e somente se, $ \phi $ é absoluta entre quaisquer modelos $ \mathcal{M} $ e $ \mathcal{N} $ transitivos.
</WRAP>





**~~#~~** Vamos definir, por abreviação, a fórmula $ x \sim y $ por:
\[
\forall z (( (z \in x )\to (z \in y)) \land ((z \in y) \to (z \in x)))
\]
**~~#.#~~** $ \mathcal{M} \doteq (M = \{a,\{a\},\{a,b\}\},\cdot^{\mathcal{M}}) $ e $ \mathcal{N} \doteq (N = \{a,b,\{a\},\{a,b\}\},\cdot^{\mathcal{N}}) $ são $L$-modelos na forma padrão.
   - Considere $ \alpha $ valoração com $ \alpha(x) = \{a\} $ e $ \alpha(y) = \{a,b\} $. Mostre que $ \mathcal{M} \models x \sim y [\alpha] $ mas $ \mathcal{N} $ não satisfaz a mesma proposição.
   - Conclua que $ x \sim y $ não é absoluta entre $ \mathcal{M} $ e $\mathcal{N} $.
   - Note que $ \mathcal{M} $ não sabe da existência de $ b $, e que apesar de $ \mathcal{M} \models x \sim y [\alpha] $, $ \alpha(x) \overset{\text{meta}}{\neq} \alpha (y) $.

**~~#.#~~** Considere agora um $L$-modelo $ \mathcal{M}$ qualquer:
   - Mostre que $ \mathcal{M} \models x \sim y [\alpha] \iff $ $ \alpha(x)\cap M = \alpha(y)\cap M $.
   - Seja $ \mathcal{M} $ transitivo, mostre que $ \mathcal{M} \models (x \sim y) \iff \mathcal{M} \models (x = y) $.
   - Conclua que $ \mathcal{M} $ é transitivo, então $ \mathcal{M} \models \text{ extensionalidade} $.





**~~#~~** Seja $\mathcal{M}$ um $L$-modelo e sejam $\phi,\psi$ $L$-fórmulas, podemos demontrar que:

**~~#.#~~** $ \mathcal{M} \models \phi \lor \psi \iff \mathcal{M} \models \neg((\neg \phi)\land(\neg \psi)) $ e que $ \mathcal{M} \models \forall x \phi \iff \mathcal{M} \models \neg(\exists x (\neg \phi)) $. Pode-se demonstrar, analogamente, resultados parecidos para outros conectivos, definindo-os em termos de $\{ \neg,\land,\exists \}$.

**~~#.#~~** Mostre que dada $ \phi $ existe fórmula $\psi$ construída usando-se apenas construções recursivas sob $\{ \neg,\land,\exists \} $ tal que $ \mathcal{M} \models \psi \leftrightarrow \phi $ usando indução sob a complexidade de $ \phi $.

**~~#.#~~** Conclua que, ao fazer indução sob a complexidade de fórmulas, basta provar recorrendo sob as construções usando $\{ \neg,\land,\exists \} $.






**~~#~~** Usando o 'atalho' fornecido pela questão anterior, vamos mostrar que seja $ \phi $ em $ \Delta_{0} $ e $ \mathcal{M},\mathcal{N} $ $ L $-modelos transitivos, então $ \phi $ é absoluta entre eles. \\

**~~#.#~~** Começando das atômicas, $ \psi $ do tipo $ t = s $ são na verdade do tipo $ x = y $ igualdade de variáveis. O outro caso é $ x \in y $. Em ambos, temos que as atômicas são absolutas entre os modelos.<wrap help>[[solucao:valeAtomicas|Solução]]</wrap>\\

**~~#.#~~** Mostre sob recursão em $ \neg $ e $ \land $.<wrap help>[[solucao:conjuntionAndNegationStep|Solução]]</wrap>\\

**~~#.#~~** Seja $ \phi $ absoluta entre os modelos, mostre que ainda o é a fórmula $ \exists x \in t \phi $.<wrap help>[[solucao:boundExistenceStep|Solução]]</wrap>\\










**~~#~~** Mostre que existem fórmulas em $ \Delta_{0} $ equivalentes às (abreviações):
   - $ x = \emptyset $.
   - $ x \subset y $.
   - $ x=y $.
   - $ x = \{y,z\} $.
   - $ x = (y,z) $.
   - $ x $ é ordinal.
   - $ x = y \times z $.
   - $ x = \omega $.
   - $ x = dom(y) $.






**obs.:** note que se encontrarmos um modelo transitivo para uma fórmula $\Delta_0$, temos que qualquer modelo transitivo satisfaz tal fórmula.\\





<WRAP info>
Define-se por recursão sobre os ordinais o rank de um conjunto como:
   - Seja $ rank(\emptyset) = \emptyset $
   - $ rank(X) \doteq \sup\{rank(y) + 1 : y \in X \} $.
Define-se também a hierarquia de von Neumann como:	
   - $ V_{0} = \emptyset $
   - $ V_{\alpha+1} \doteq \mathcal{P}(V_{\alpha}) $  para $ \alpha $ sucessor.
   - $ V_{\alpha} = \bigcup_{\gamma\in \alpha}V_{\gamma} $ pra $ \alpha $ limite.\\
</WRAP>


**~~#~~** Determine o rank de $\emptyset$, $\{\emptyset\}$, $\{\emptyset, \{\emptyset\}\}$, $\omega$ e $\omega \cup \{\omega\}$. 

**~~#~~** De fato, tem-se que:
   - $ V_{\alpha} $ transitivo.
   - $ V_{\alpha} \subset V_{\beta} $ se $ \alpha \leq \beta $.
   - $ X \subset V_{\alpha} $ e $ \alpha < \beta $ então $ X \in V_{\beta} $.
   - $ X \in V_{\alpha} $ então $ X \subset V_{\beta} $ para algum $ \beta < \alpha $.
   - $ X $ é um conjunto, $ rank(X) = \alpha $ $ \iff $ $( X \subset V_{\alpha} $ e $ \beta < \alpha \implies X \not \subset V_{\beta}) $.





**~~#~~** Considere $ \mathcal{M} = (V_{\omega + \omega},\cdot^{\mathcal{M}}) $ modelo na forma padrão. Queremos mostrar, ao menos parcialmente, que $ \mathcal{M} \models ZFC\backslash\{\text{substituição}\} $.

**~~#.#~~** Mostremos que $ \mathcal{M} \models ZFC \backslash \{\text{substituição}\} $.
   - Note que $ V_{\omega + \omega} $ é transitivo, logo, em particular ele modela extensionalidade. De fato, qualquer $ \Delta_0 $ para a qual existe modelo transitivo é satisfeita por $ \mathcal{M} $.
   - Prove que $ \mathcal{M} \models \{\text{união}\}$.<wrap help>[[solucao:OmegaOmegaUniao|Solução]]</wrap>
   - Prove que $ \mathcal{M} \models \{\text{partes}\}$.<wrap help>[[solucao:OmegaOmegaPartes|Solução]]</wrap>
   - Mostre para os outros axiomas.

**~~#.#~~** Prove que $ \mathcal{M} \models \neg\text{substituição} $.<wrap help>[[solucao:OmegaOmegaNaoSubst|Solução]]</wrap>

**~~#.#~~** Note que isso demonstra que o axioma da substituição é independente do restante de $ZFC$, assumindo que $ZFC$ é consistente.




**~~#~~** Mostre que $ V_\omega \models ZFC \backslash \{\text{infinito}\} $.

**~~#~~** Este é um roteiro para mostrar que todo conjunto admite um fecho transitivo. Seja $X$ um conjunto.

**~~#.#~~** Defina $T_0 = X$ e $T_{n + 1} = \bigcup T_n$ para cada $n \in \omega$. Considere $tr(X) = \bigcup_{n \in \omega} T_n$. Note que $tr(X)$ é um conjunto tal que $X \subset tr(X)$.

**~~#.#~~** Mostre que $tr(X)$ é transitivo.

**~~#.#~~** Seja $Y$ transitivo tal que $X \subset Y$. Mostre que $tr(X) \subset Y$.

<WRAP info>
   - Dado $ \kappa $ cardinal, dizemos que $ X $ é hereditariamente de cardinalidade $ < \kappa $ se $ |tr(x)| < \kappa $.
   - Denotemos por $ H(\kappa) = \{x : |tr(x)| < \kappa \} $ a coleção de todos os conjuntos hereditariamente de card. $ < \kappa $.
</WRAP>

**~~#~~** Esse é um roteiro para motivar a definição acima.

**~~#.#~~** Dê um exemplo de um conjunto finito mas cujo fecho transitivo não seja finito.

**~~#.#~~** Mostre que a coleção de todos os conjuntos unitários não forma um conjunto.


**~~#~~** $ H(\kappa) $ é transitivo.<wrap help>[[solucao:HkappaEhTrans|Solução]]</wrap>




**~~#~~** Seja $ x $ um conjunto tal que $ rank(x) = \alpha $, então $ \{rank(y) : y \in tr(x)\} = \alpha $.<wrap help>[[solucao:rankSet|Solução]]</wrap>





**~~#~~** Observe que, //a priori//, $H(\kappa)$ não é necessariamente um conjunto. Queremos demonstrar que este é o caso:

**~~#.#~~** Dado $ \kappa $ infinito, seja $ x \in H(\kappa) $ então $ |tr(x)| < \kappa $, note que $ \{rank(y) : y \in tr(x)\} = \alpha = rank(x) $ está 'enumerado' por itens de $ tr(x) $ e portanto temos que $ |rank(x)| \leq |tr(x)| < \kappa $ .

**~~#.#~~** Nesse caso, é possível mostrar que $ x \in V_\kappa $. Conclua que $ H(\kappa) $ é conjunto.




**~~#~~** Mostre que $ H(\omega) = V_\omega $.<wrap help>[[solucao:hOmegaehVomega|Solução]]</wrap>




**~~#~~** Seja $ \kappa  $ regular. Seja $ x \subset H(\kappa) $ tal que $ |x| < \kappa $, queremos mostrar que  $ x \in H(\kappa) $. Se $\kappa = \omega$, temos o resultado.

**~~#.#~~** Tome $\omega < \kappa $ regular e $ x $ como na hipótese, seja $|tr(x)| \geq \kappa$. Seja $ x_{0} = x $ tem $ |x_{0}| < \kappa $. Tome $ x_{n+1} = \bigcup x_{n} $, deve haver $ n $ o menor com $ |x_{n}| \geq \kappa $. Se $ |x_{n-1}| < \kappa$ e $ |\bigcup x_{n-1}| \geq \kappa $, note que encontramos $x_{n-1}\in tr(x)$ com $|tr(x_{n-1})| \geq \kappa $, mas havíamos assumido $x \subset H(\kappa)$.

**~~#.#~~** Seja $ |tr(x)| = |\bigcup_{n \in \omega}x_n| = \sup \{|x_{n}| : n \in \omega \}= \alpha \geq \kappa $, note que também $\alpha \leq \kappa $. Mas então $\alpha = \kappa$, mas daí $ cf(\kappa) = \omega $.



**~~#~~** Seja $ \phi $ uma fórmula do tipo função tal que $ a \in H(\kappa) $ então $ \phi(a) \in H(\kappa) $. Então dado $ A \in H(\kappa) $ temos que $ \{\phi(a) : a \in A\} \in H(\kappa) $.<wrap help>[[solucao:HmodelaSubst|Solução]]</wrap>



**obs.:** existe $ x \in H(\kappa) $, $ 2^{|x|} \geq \kappa $.\\



Fosse $ \kappa $ regular com $ \forall \alpha < \kappa \,\, 2^{\alpha} < \kappa $ ( que não $ \omega $). $ H(\kappa) = V_{\kappa} $ seria modelo para $ ZFC $.\\



Concluímos que $ \kappa $ não enum. regular então $ H(\kappa) $ é modelo para $ ZFC $ exceto pelo axioma das partes. Se é, $ \kappa $ é inacessível.