Topologia e conjuntos em exercícios

1. $R$ é uma relação $n$-ária sobre $A$ se $R \subset A^n$
2. $f$ é uma função $n$-ária sobre $A$ se $f : A^n \to A$

Símbolos lógicos:

1. Variáveis (usualmente escreveremos $x,y,z,\ldots$ ou $x_1,\ldots,x_n,\ldots$ como símbolo de variável)
2. Símbolo de igualdade: $=$
3. Operadores conectivos: $\neg, \wedge, \vee, \rightarrow$
4. Operadores quantificadores: $\exists, \forall$
5. Parêntesis e vírgula: (, ), ,

Símbolos não lógicos:

1. Relações
2. Funções
3. Constantes

A coleção $L$ de todos os símbolos (lógicos e não lógicos) é chamada de vocabulário (ou linguagem).

Em geral iremos chamar os símbolos de relação de $L$ de $L$-relação, os símbolos de função de $L$ de $L$-função etc.

Fixado um vocabulário $L$, temos:

Uma $L$-expressão nada mais é do que uma concatenação finita de símbolos de $L$.

Um $L$-termo é um elemento do menor conjunto $T$, onde $T$ é um conjunto de $L$-expressões que contém todas as $L$-variáveis, as $L$-constantes e, se $t_1,\ldots,t_n$ são $L$-termos e $f$ é uma $L$-função $n$-ária, então $f(t_1,\ldots,t_n)$ também é um elemento de $T$.

Uma $L$-fórmula atômica é um elemento do conjunto $A$, onde $A$ é o conjunto formado pelas $L$-expressões da seguinte forma:

1. $s = t$, onde $s,t$ são $L$-termos
2. $R(t_1,\ldots,t_n)$, onde $t_1,\ldots,t_n$ são $L$-termos e $R$ é uma $L$-relação $n$-ária

Dados $\phi,\psi \in A$, uma $L$-fórmula é um elemento do menor conjunto $F$ que contém as seguintes $L$-expressões:

1. $\neg \phi$
2. $\phi \vee \psi$
3. $\phi \wedge \psi$
4. $\phi \rightarrow \psi$
5. $\exists x \phi$, onde $x$ é uma $L$-variável
6. $\forall x \phi$, onde $x$ é uma $L$-variável

Usualmente as $L$-fórmulas com variáveis livres $x_1,\ldots,x_n$ serão denotadas por $\phi(x_1,\ldots,x_n)$

Uma variável que aparece em uma fórmula atômica é chamada de variável livre.

Se $x$ é uma variável livre em uma $L$-fórmula $\phi$, então ela deixa de ser nas fórmulas $\forall x \phi$ e $\exists x \phi$. Neste caso dizemos que $x$ é uma variável ligada.

Uma $L$-fórmula $\phi$ que não possui variáveis livres é chamada de $L$-sentença.

Um $L$-modelo $\mathcal{M}$ é um par $\langle M, \cdot^{\mathcal{M}} \rangle$, onde $M$ é um conjunto não vazio, que chamamos de universo, e $\cdot^{\mathcal{M}}$ é uma função cujo domínio é formado pelos símbolos não lógicos de $L$ de forma que:

1. Se $R$ é um símbolo de relação $n$-ária de $L$, então $R^{\mathcal{M}} \subset M^n$ é uma relação de $M$
2. Se $f$ é um símbolo de função $n$-ária de $L$, então $f^{\mathcal{M}} : M^n \to M$ é uma função em $M$
3. Se $c$ é um símbolo de constante de $L$, então $c^{\mathcal{M}} \in M$

Aqui, se $x$ é um símbolo não lógico de $L$, então $x^{\mathcal{M}}$ representa $\cdot^{\mathcal{M}}(x)$ e dizemos que $x^{\mathcal{M}}$ é a interpretação de $x$ em $M$.

Uma valoração nada mais é do que uma função que atribui a cada variável de $L$ um elemento de $M$.

Fixada uma valoração $\alpha$, então para cada termo $t$ de $L$ nós podemos atribuir um elemento de $M$, que denotaremos por $t^{\mathcal{M}}[\alpha]$, da seguinte forma:

1. Se $t$ é uma variável, então $t^{\mathcal{M}}[\alpha] = \alpha(t)$
2. Se $t$ é uma constante, então $t^{\mathcal{M}}[\alpha] = t^{\mathcal{M}}$
3. Se $t$ é da forma $f(t_1,\ldots,t_n)$, então $t^{\mathcal{M}}[\alpha] = f^{\mathcal{M}}(t_1^{\mathcal{M}}[\alpha],\ldots,t_n^{\mathcal{M}}[\alpha])$

Dada uma $L$-fórmula $\phi$, dizemos que $\phi$ é satisfeita por $\alpha$ em $\mathcal{M}$, denotado $\mathcal{M} \models \phi[\alpha]$, se:

1. $\phi$ é da forma $s = t$ e vale $s^{\mathcal{M}}[\alpha] = t^{\mathcal{M}}[\alpha]$
2. $\phi$ é da forma $R(t_1,\ldots,t_n)$ e vale $R^{\mathcal{M}}(t_1^{\mathcal{M}}[\alpha],\ldots,t_n^{\mathcal{M}}[\alpha])$
3. $\phi$ é da forma $\neg \psi$ e vale $\mathcal{M} \not\models \psi^{\mathcal{M}}[\alpha]$
4. $\phi$ é da forma $\phi_1 \wedge \phi_2$ e valem $\mathcal{M} \models \phi_1^{\mathcal{M}}[\alpha]$ e $\mathcal{M} \models \phi_2^{\mathcal{M}}[\alpha]$
5. $\phi$ é da forma $\phi_1 \vee \phi_2$ e vale $\mathcal{M} \models \phi_1^{\mathcal{M}}[\alpha]$ ou vale $\mathcal{M} \models \phi_2^{\mathcal{M}}[\alpha]$ (pode valer os dois)
6. $\phi$ é da forma $\exists x \psi$ e existe $a \in M$ tal que $\mathcal{M} \models \psi^{\mathcal{M}}[\alpha_a^x]$

Aqui $\alpha_a^x$ é a função que vale o mesmo de $\alpha$ para todo símbolo, mas $\alpha_a^x(x) = a$.

No caso em que $\mathcal{M} \models \phi[\alpha]$ para todo $\alpha$, dizemos que $\mathcal{M}$ satisfaz $\phi$ e denotamos simplesmente por $\mathcal{M} \models \phi$

Se $x_1,\ldots,x_n$ são as únicas variáveis livres de $\phi$, denotamos por $\mathcal{M} \models \phi[a_1,\ldots,a_n]$ a afirmação $\mathcal{M} \models \phi[\alpha]$, onde $\alpha(x_i) = a_i$.