Topologia e conjuntos em exercícios

===== Valor booleano de fórmulas =====

<WRAP tip>
É melhor você fazer essa [[lista:nomes|lista]] antes desta.
</WRAP>

**~~#~~** Dentro de uma álgebra de Boole, mostre que $\inf \emptyset = 1$ e $\sup \emptyset = 0$.

O objetivo desta lista é determinar o valor $[\![ \varphi ]\!]$ para uma fórmula $\varphi$ da teoria dos conjuntos. Pense nisso como um algoritmo que, fixada uma fórmula, temos como calcular tal valor. Esse procedimento será feito por indução na complexidade das fórmulas. Assim, começamos com as atômicas (as mais simples). Outra coisa a se notar é que as fórmulas aqui não falarão mais sobre conjuntos, mas sim sobre nomes para conjuntos.

<WRAP info>
Vamos usar a seguinte notação para $a, b \in B$: $a \Rightarrow b = -a + b$.
</WRAP>

<WRAP info>

Sejam $x, y$ nomes. Definimos:

  * $\displaystyle [\![ x \in y ]\!] = \sup_{t \in \text{dom}(y)}y(t)[\![ x = t ]\!]$
  * $\displaystyle [\![ x \subset y ]\!] = \inf_{t \in \text{dom}(x)} (x(t) \Rightarrow [\![ t \in y ]\!])$
  * $[\![ x = y ]\!] = [\![ x \subset y ]\!] [\![ y \subset x ]\!]$

</WRAP>

**~~#~~** Mostre que $[\![ \emptyset = \emptyset ]\!] = 1$.

**~~#~~** Considere o nome $x = \{(\emptyset, a)\}$ onde $a \in B$. Calcule $[\![ \emptyset \in x ]\!]$. 

**~~#~~** Seja $x$ um nome. Mostre que $[\![ x = x ]\!] = 1$. Atenção, neste resultado, você provavelmente vai querer usar o que chamamos de indução na complexidade do nome. Isto é, você mostra que vale $[\![ x = x ]\!] = 1$, supondo que vale $[\![ t = t ]\!] = 1$ para qualquer $t$ com rank menor que $x$.

**~~#~~** Sejam $x, y$ nomes, com $y \in $dom$(x)$. Mostre que $x(y) \leq [\![ y \in x ]\!]$. 

**~~#~~** Sejam $a, b, c$ nomes. Mostre as seguintes afirmações:
  * $[\![ a = b ]\!] [\![ b = c ]\!] \leq [\![ a = c ]\!]$
  * $[\![ a \in b ]\!] [\![ a = c ]\!] \leq [\![ c \in b ]\!]$
  * $[\![ a \in b ]\!] [\![ b = c ]\!] \leq [\![ a \in c ]\!]$
Dica: Mostre as três afirmações simultaneamente por indução em $a, b, c$. 

<WRAP info>
Dada uma fórmula $\varphi(x_1, ..., x_n)$ onde $x_1, ..., x_n$ são as variáveis livres de $\varphi$ e dados $\sigma_1, ..., \sigma_n$ nomes, definimos $[\![ \varphi(\sigma_1, ..., \sigma_n) ]\!]$ por indução na complexidade de $\varphi$ da seguinte forma:
  * Se $\varphi$ é da forma $x_1 = x_2$ ou $x_1 \in x_2$, procedemos como anteriormente.
  * Se $\varphi$ é da forma $\neg \psi(x_1, ..., x_n)$, então $[\![ \varphi(\sigma_1, ..., \sigma_n) ]\!] = - [\![ \psi(\sigma_1, ..., \sigma_n) ]\!]$. 
  * Se $\varphi$ é da forma $\psi_1(x_1, ..., x_n) \land \psi_2(x_1, ..., x_n)$, então $[\![ \varphi(\sigma_1, ..., \sigma_n) ]\!] = [\![ \psi_1(\sigma_1, ..., \sigma_n) ]\!] [\![ \psi_2(\sigma_1, ..., \sigma_n) ]\!]$. 
  * Se $\varphi$ é da forma $\exists y \psi(y, x_1, ..., x_n)$, então $\displaystyle [\![ \varphi(\sigma_1, ..., \sigma_n) ]\!] = \sup_{\tau}[\![ \psi(\tau, \sigma_1, ..., \sigma_n) ]\!]$
 
</WRAP>


**~~#~~** Calcule $[\![ \varphi \lor \psi ]\!]$ em termos de $[\![ \varphi ]\!]$ e $[\![ \psi ]\!]$.

**~~#~~** Calcule $[\![ \forall y \ \varphi(y) ]\!]$ em termos de $[\![ \varphi(\sigma) ]\!]$ para $\sigma$ nome.

**~~#~~** Calcule $[\![ \exists x \ \forall y \ y \notin x ]\!]$.

**~~#~~** Mostre que $[\![ \varphi ]\!] = 1$, onde $\varphi$ é o axioma da extensionalidade.

**~~#~~** Mostre que $[\![ \varphi ]\!] = 1$, onde $\varphi$ é o axioma do par.
Topologia e conjuntos em exercícios

Ferramentas do usuário

Ferramentas do site

Ferramentas da página
