Ferramentas do usuário
Essa é uma revisão anterior do documento!
Modelos
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 de todos os símbolos (lógicos e não lógicos) é chamada de vocabulário (ou linguagem).
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 variáveis do vocabulário $L$ e tal que, se $t_1,\ldots,t_n$ são 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 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$
Mostre que de fato $T$ é o menor conjunto descrito na definição acima, ou seja, se $T'$ é um outro conjunto que contém as variáveis de $L$ e tal que, se $t_1,\ldots,t_n \in T'$ e $f$ é uma função $n$-ária, então $f(t_1,\ldots,t_n) \in T'$, temos $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 as seguintes $L$-expressões:
- $\neg \phi; \phi \wedge \psi; \phi \rightarrow \psi$, onde $\phi,\psi \in A$
- $\exists x \phi$ e $\forall x \phi$, onde $x$ é uma $L$-variável e $\phi \in A$.
3 Exiba quem é o conjunto $F$ e mostre que tal conjunto é de fato o menor, como feito no caso dos $L$-termos.
Ferramentas da página
