Topologia e conjuntos em exercícios

===== Álgebras de Boole e valoração de fórmulas =====

<WRAP tip>
Antes de fazer esta lista, é melhor você fazer a lista de [[lista:algebraboole|Álgebras de Boole]].
</WRAP>

No decorrer de toda esta lista vamos supor fixada uma álgebra de Boole \((\mathcal{A},+,\cdot,-)\). Denotaremos o valor booleano de uma fórmula \(\varphi\) por \([\![\varphi]\!]\).

<WRAP info>
Um conjunto \(x\) é um {{entry>nome}} se \(x\) é uma função cujo domínio é um conjunto de nomes e cuja imagem está contida em \( \mathcal{A} \). 
</WRAP>

Na verdade precisamos definir os nomes recursivamente. Usaremos uma construção análoga a dos \(V_{\alpha}\), da seguinte forma: \[V^{\mathcal{A}}_0 = \emptyset\]
\[ V^{\mathcal{A}}_{\alpha} = \{x  \, | \, x \text{ é função, Im}(x) \subset \mathcal{A} \text{ e } \exists \xi < \alpha \, (\text{dom}(x) \subset V^{\mathcal{A}}_{\xi})\} \text{ para todo ordinal } \alpha\] 
\[V^{\mathcal{A}} = \{x \, | \, \exists \alpha \, (x \in V^{\mathcal{A}}_{\alpha})\} \]

Então \(V^{\mathcal{A}}\) é a classe de todos os nomes.\\


**~~#~~** Determine o conjunto \( V^{\mathcal{A}}_1\). "Entenda" qual é o conjunto \( V^{\mathcal{A}}_2\).

**~~#~~** Se \(\xi < \alpha\), então \( V^{\mathcal{A}}_{\xi} \subset V^{\mathcal{A}}_{\alpha}\).

Queremos definir valores na álgebra de Boole para fórmulas. Interpretando \(1\) como sendo verdadeiro e \(0\) como falso, vamos definir de tal forma que os axiomas de ZFC tenham valor \(1\) e garantindo que se uma fórmula tem valor \(1\) e ela implica alguma outra fórmula, então esta última também tenha valor \(1\). Para isso vamos substituir as variáveis por nomes, começando com as fórmulas atômicas para depois aumentarmos a complexidade.

<WRAP info>
Sejam \( x, y \) nomes. Então
 \[ [\![ x \in y ]\!] = \sup_{t \in \text{dom} (y)} [\![ x = t ]\!] y (t) \]
 \[ [\![ x \subset y ]\!] = \inf_{t \in \text{dom} (x)} (x (t) \Rightarrow [\![ t \in y ]\!] ) \]
 \[ [\![ x = y ]\!] = [\![ x \subset y ]\!] [\![ y \subset x ]\!] \] 
</WRAP>

Pode parecer que a definição acima não funciona, pois são interdependentes, porém novamente estamos definindo estas valorações recursivamente. Para isso usamos a seguinte relação bem fundada sobre as dupla de nomes:
\[ \langle x,y \rangle < \langle u,v \rangle \text{ se, e só se, } (x \in \text{dom}(u) \text{ e } y=v) \text { ou } (x = u \text{ e } y \in \text{dom}(v))\]
Se ainda não fizer sentido, os exercícios abaixo podem ajudar:

**~~#~~** Demonstre o resultado para o caso \(x = \emptyset\) e \(y = \emptyset\). <wrap tip>[[dica:InfSupVazio|Dica]]</wrap>

**~~#~~** Dado \(a \in \mathcal{A}\), demonstre o resultado para o caso \(x = \emptyset\) e \(y = \langle \emptyset, a \rangle \) e para o caso \(x = \langle \emptyset, a \rangle \) e \(y = \emptyset \).

**~~#~~** Dados \(a,b \in \mathcal{A}\), demonstre o resultado para o caso \(x = \langle \emptyset, a \rangle \) e \(y = \langle \emptyset, b \rangle \) e para o caso \(x = \langle \emptyset, b \rangle \) e \(y = \langle \emptyset, a \rangle \).

Uma relação bem fundada sobre \(A\) é uma relação onde qualquer \(X \subset A\) possui elemento minimal. Na verdade, para essa recursão funcionar precisamos também que a relação seja //set-like//. Os detalhes estão no livro do Kunen, na seção \(I.9\) (só a definição de relação bem fundada que está separada, na página 31). 

**~~#~~** Seja \(x\) um nome, então \( [\![ x = x ]\!] = 1 \). 

**~~#~~** Sejam \(x, y\) e \(z\) nomes, então: <wrap tip>[[dica:InducaoNosNomes|Dica]]</wrap>
  - \([\![ x = y ]\!] [\![ y = z]\!]  \leq [\![ x = z ]\!]\)
  - \([\![ x \in y ]\!] [\![ x = z ]\!] \leq [\![ z \in y ]\!]\)
  - \([\![ x \in y ]\!] [\![ y = z ]\!] \leq [\![ x \in z ]\!]\)

**~~#~~** Sejam \(x,y\) nomes. Se \( x \in \text{dom}(y)\) então \( y(x) \leq [\![ x \in y ]\!]\).

Ou seja, \(x(y)\) "mede a chance" de \(y\) pertencer a \(x\). Porém como estamos lidando com nomes, podemos ter uma desigualdade estrita.

**~~#~~** Seja \(a \in \mathcal{A}\) com \(a \neq 0,1\). Considere o nome \( x = \{\langle \emptyset,a \rangle,\langle \langle \emptyset,0 \rangle,-a \rangle\}\). Calcule \(x(\emptyset) \) e \([\![ \emptyset \in x ]\!]\). <wrap tip>[[dica:InfSupVazio|Dica]]</wrap>

Além disso, vários nomes podem representar um mesmo conjunto.

**~~#~~** Seja \( x = \{\langle \emptyset, 1 \rangle\}\) e \( y = \{\langle \emptyset, a \rangle, \langle \langle \emptyset, 0 \rangle, -a \rangle \} \). Calcule \([\![ x=y ]\!]\).

**~~#~~** Encontre uma classe de nomes em que todos os seus elementos representam o mesmo conjunto. <wrap tip>[[dica:NomesVazio|Dica]]</wrap>

<WRAP info>
Dada uma fórmula \(\varphi(x_1,\dots,x_n)\) onde \( x_1,\dots,x_n\) indicam suas variáveis livres, e dados nomes \(\tau_1,\dots,\tau_n\), definimos \([\![ \varphi (\tau_1,\dots,\tau_n) ]\!]\) por recursão sobre a complexidade de \(\varphi\).
  - Se \(\varphi\) é atômica, usamos a definição anterior.
  - Se \( \varphi(x_1,\dots,x_n)\) é da forma \( \neg \psi(x_1,\dots,x_n)\), então \[[\![ \varphi(\tau_1,\dots,\tau_n) ]\!] = -[\![ \psi(\tau_1,\dots,\tau_n) ]\!]\]
  - Se \( \varphi(x_1,\dots,x_n)\) é da forma \(\psi(x_1,\dots,x_n) \wedge \psi'(x_1,\dots,x_n)\), então \[ [\![ \varphi(\tau_1,\dots,\tau_n) ]\!] = [\![ \psi(\tau_1,\dots,\tau_n) ]\!][\![ \psi'(\tau_1,\dots,\tau_n) ]\!]\]
  - Se \( \varphi(x_1,\dots,x_n)\) é da forma \(\psi(x_1,\dots,x_n) \vee \psi'(x_1,\dots,x_n)\), então \[ [\![ \varphi(\tau_1,\dots,\tau_n) ]\!] = [\![ \psi(\tau_1,\dots,\tau_n) ]\!]+[\![ \psi'(\tau_1,\dots,\tau_n) ]\!]\]
  - Se \( \varphi(x_1,\dots,x_n)\) é da forma \(\exists y \,\psi(y,x_1,\dots,x_n)\), então \[ [\![ \varphi(\tau_1,\dots,\tau_n) ]\!] = \sup_{\sigma} [\![ \psi(\sigma, \tau_1,\dots,\tau_n) ]\!]\]
  - Se \( \varphi(x_1,\dots,x_n)\) é da forma \(\forall y \,\psi(y,x_1,\dots,x_n)\), então \[ [\![ \varphi(\tau_1,\dots,\tau_n) ]\!] = \inf_{\sigma} [\![ \psi(\sigma, \tau_1,\dots,\tau_n) ]\!]\]
</WRAP>

**~~#~~** Sejam \(\varphi\) e \(\psi\) fórmulas, então \([\![ \varphi \rightarrow \psi ]\!] = 1\) se, e só se, \( [\![ \varphi ]\!] \leq [\![ \psi ]\!]\).

**~~#~~** Se \(\varphi\) é o axioma da extensionalidade, isto é, 
\[ \forall x \, \forall y \, x=y \leftrightarrow (\forall z \, ( z \in x \rightarrow z \in y) \wedge (z \in y \rightarrow z \in x))\]
Então \([\![ \varphi ]\!]=1\).

**~~#~~** Se \(\varphi\) é o axioma do par, ou seja, 
\[ \forall x \, \forall y \, \exists z \, x \in z \wedge y \in z\]
Então \([\![ \varphi ]\!]=1\).
Topologia e conjuntos em exercícios

Ferramentas do usuário

Ferramentas do site

Ferramentas da página
