Ferramentas do usuário
Álgebras de Boole e valoração de fórmulas
Antes de fazer esta lista, é melhor você fazer a lista de Álgebras de Boole.
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]\!]\).
Um conjunto \(x\) é um nome se \(x\) é uma função cujo domínio é um conjunto de nomes e cuja imagem está contida em \( \mathcal{A} \).
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.
1 Determine o conjunto \( V^{\mathcal{A}}_1\). “Entenda” qual é o conjunto \( V^{\mathcal{A}}_2\).
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.
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 ]\!] \]
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:
3 Demonstre o resultado para o caso \(x = \emptyset\) e \(y = \emptyset\). Dica
4 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 \).
5 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).
6 Seja \(x\) um nome, então \( [\![ x = x ]\!] = 1 \).
7 Sejam \(x, y\) e \(z\) nomes, então: Dica
- \([\![ 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 ]\!]\)
8 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.
9 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 ]\!]\). Dica
Além disso, vários nomes podem representar um mesmo conjunto.
10 Seja \( x = \{\langle \emptyset, 1 \rangle\}\) e \( y = \{\langle \emptyset, a \rangle, \langle \langle \emptyset, 0 \rangle, -a \rangle \} \). Calcule \([\![ x=y ]\!]\).
11 Encontre uma classe de nomes em que todos os seus elementos representam o mesmo conjunto. Dica
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) ]\!]\]
12 Sejam \(\varphi\) e \(\psi\) fórmulas, então \([\![ \varphi \rightarrow \psi ]\!] = 1\) se, e só se, \( [\![ \varphi ]\!] \leq [\![ \psi ]\!]\).
13 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\).
14 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\).
Ferramentas da página
