Ferramentas do usuário
Modelos
Esta lista tem como objetivo apresentar como formalizar a ideia de como dizer que uma certa estrutura satisfaz determinados axiomas. Para isso, vamos formalizar como podemos escrever tais axiomas. A primeira parte da lista cuida justamente disso: como os axiomas podem ser escritos de uma maneira formal. Atente que, de começo, as fórmulas não tem qualquer significado - são apenas sequências de símbolos. O que fazemos de início é simplesmente dizer quais sequências estão bem formadas e quais não (as bem formadas têm chance de serem úteis mais tarde).
Comecemos com algumas terminologias. Fixado um conjunto $A$:
- $R$ é uma relação $n$-ária sobre $A$ se $R \subset A^n$
- $f$ é uma função $n$-ária sobre $A$ se $f : A^n \to A$
1 Dê um exemplo de uma relação $2$-ária (também chamada de binária) e de uma função sobre $\mathbb{N}$.
Agora mostremos quais símbolos poderemos usar ao escrevermos fórmulas:
Símbolos lógicos:
- Variáveis (usualmente escreveremos $x,y,z,\ldots$ ou $x_1,\ldots,x_n,\ldots$ como símbolo de variável)
- Símbolo de igualdade: $=$
- Operadores conectivos: $\neg, \wedge, \vee, \rightarrow$
- Operadores quantificadores: $\exists, \forall$
- Parêntesis e vírgula: (, ), ,
Símbolos não lógicos:
- Relações
- Funções
- 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$.
2 Vamos exibir quem é $T$:
- Seja $T_0$ o conjunto com todas as variáveis e constantes do vocabulário $L$.
- Dado $n \in \omega$, seja $T_{n+1} = T_n \cup \{f(t_1,\ldots,t_m) : f \text{ é uma função $m$-ária de $L$ e } t_1,\ldots,t_m \in T_n\}$
- Defina $T = \bigcup_{n \in \omega} T_n$
3 Mostre que $T$ é o menor conjunto que contém as variáveis do vocabulário $L$ e é fechado por $L$-funções. Ou seja:
- $T_0 \subset T$
- Se $f$ é uma $L$-função $n$-ária e $t_1,\ldots,t_n \in T$, então $f(t_1,\ldots,t_n) \in T$
- Se $T'$ é um outro conjunto de expressões com as propriedades 1 e 2, então $T \subset T'$
Uma $L$-fórmula atômica é um elemento do conjunto $A$, onde $A$ é o conjunto formado pelas $L$-expressões da seguinte forma:
- $s = t$, onde $s,t$ são $L$-termos
- $R(t_1,\ldots,t_n)$, onde $t_1,\ldots,t_n$ são $L$-termos e $R$ é uma $L$-relação $n$-ária
Uma $L$-fórmula é um elemento do menor conjunto $F$ que contém todas as $L$-fórmulas atômicas e que, se $\phi$ e $\psi$ pertencem a $F$, então as seguintes também pertencem a $F$: :
- $\neg \phi$
- $\phi \vee \psi$
- $\phi \wedge \psi$
- $\phi \rightarrow \psi$
- $\exists x \phi$, onde $x$ é uma $L$-variável
- $\forall x \phi$, onde $x$ é uma $L$-variável
4 Exiba quem é o conjunto $F$ e mostre que tal conjunto é de fato o menor, como feito no caso dos $L$-termos.
Toda ocorrência de uma variável em uma fórmula atômica é chamada de livre.
Se $x$ ocorre livre em uma $L$-fórmula $\phi$, então essas ocorrências o deixam de ser nas fórmulas $\forall x \phi$ e $\exists x \phi$. Neste caso dizemos que a ocorrência de $x$ é ligada.
Uma $L$-fórmula $\phi$ que não possui variáveis ocorrendo livres é chamada de $L$-sentença.
5 Dê exemplos de fórmulas com variáveis ocorrendo livres, ligadas e de sentenças. Solução
Finalmente podemos começar a dar algum sentido às afirmações da linguagem. A primeira parte é como “interpretar” os símbolos. Essa interpretação, intuitivamente, se dá na seguinte maneira: fixamos um conjunto (que será o nosso universo), para cada símbolo constante associamos um elemento do nosso universo, para cada símbolo de função, associamos uma função sobre o universo etc. É o que informalmente fazemos quando apresentamos, por exemplo, um espaço vetorial: dizemos qual é o conjunto dos vetores (universo), quem é o elemento neutro (constante), quem é a soma etc.
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:
- 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$
- 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$
- 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$.
6 Suponha que os símbolos não lógicos de $L$ sejam $+,-$ e $0$, onde $+$ é uma função binária, $-$ é uma função unária e $0$ é uma constante. Dê exemplos de $L$-modelos.
As fórmulas que vão ser mais interessantes para nós são as que não têm variáveis ocorrendo livremente. Essas são as que a gente vai querer ter uma noção de fato de satisfação ou não. Mas, pela própria forma de como as fórmulas são definidas, não conseguimos dar uma definição diretamente só para as fórmulas sem ocorrências livres. Então precisamos dar alguma noção de satisfação para as ocorrências livres. Essa é a motivação para a próxima definição.
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:
- Se $t$ é uma variável, então $t^{\mathcal{M}}[\alpha] = \alpha(t)$
- Se $t$ é uma constante, então $t^{\mathcal{M}}[\alpha] = t^{\mathcal{M}}$
- 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:
- $\phi$ é da forma $s = t$ e vale $s^{\mathcal{M}}[\alpha] = t^{\mathcal{M}}[\alpha]$
- $\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])$
- $\phi$ é da forma $\neg \psi$ e vale $\mathcal{M} \not\models \psi^{\mathcal{M}}[\alpha]$
- $\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]$
- $\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)
- $\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$.
7 Sejam $+_L, \cdot_L, 0_L, 1_L, \leq_L$ os símbolos não lógicos de $L$. Considere as seguintes fórmulas:
- $\exists x (x \cdot_L x = 1_L +_L 1_L)$
- $\forall x, \neg(x = 0_L), \exists y \ (x \cdot_L y = 1_L)$
- $\forall x, \forall y \ (\neg(x = y) \wedge x \leq_Ly)) \ \exists z \ ((x \leq_L z) \wedge (z \leq_L y) \wedge \neg(x = z) \wedge \neg(y = z))$
- $\exists x \ (x \cdot_L x +_L 1 = 0_L)$
Para cada fórmula, dê exemplos de $L$-modelos em que tais fórmulas valem e exemplos onde não valem.
8 Considere $+_L, \cdot_L, 1_L$ como os símbolos não lógicos da linguagem $L$ e $\langle \mathbb{N}, \cdot^{\mathbb{N}} \rangle$ um $L$-modelo, onde $\cdot_L$ é interpretado com a multiplicação usual em $\mathbb{N}$, $+_L$ como a soma usual e $1_L = 1$. Escolha valorações em $\mathbb{N}$ de forma que a seguinte fórmula seja válida:
$\forall x \forall y \ ((x \cdot_L y = z) \wedge \neg(z = 1_L) \implies ((x = z) \wedge (y = 1_L)) \vee ((x = 1_L) \wedge (y = z)))$ Solução
9 Seja $X$ a coleção de todas as $L$-fórmulas cuja única variável livre é $x$. Seja $g$ uma função que associa cada elemento de $X$ a um elemento de $M$. Então não existe uma fórmula $\psi(x,y)$ de forma que, para toda $L$-fórmula $\phi(x)$ em $X$ e para todo $a \in M$ vale: $\mathcal{M} \models \phi[a]$ se, e somente se, $\mathcal{M} \models \psi[g(\phi),a]$ Dica
Ferramentas da página
