Ferramentas do usuário
Teorema da Compacidade
Esta lista é um roteiro para provar um resultado bastante importante em lógica de primeira ordem, o Teorema da Compacidade:
Todo conjunto finitamente modelável de fórmulas é modelável
Dizemos que um conjunto $\Sigma$ de sentenças é modelável se existe $\mathcal{M}$ modelo tal que $\mathcal{M} \models \Sigma$.
Um conjunto $\Sigma$ de sentenças será finitamente modelável se todo subconjunto finito de $\Sigma$ for modelável
Um conjunto (finitamente) modelável será maximal se, adicionando outra sentença qualquer sentença, o conjunto deixa de ser
1 Todo conjunto finitamente modelável pode ser estendido a um conjunto finitamente modelável máximal. Dica
2 Seja $\Sigma$ finitamente modelável maximal. Para todo $\Delta$ conjunto de sentenças e $\varphi, \psi$ sentenças, mostre que:
2.1 $\Delta$ finito, $\Delta \models \varphi, \, \Delta \subset \Sigma \Rightarrow \varphi \in \Sigma$ (note que $\varphi \in \Sigma$ e $\Sigma \models \varphi$ são equivalentes)
2.2 $\varphi \land \psi \in \Sigma \Leftrightarrow \varphi, \, \psi \in \Sigma$
2.3 $\neg \varphi \in \Sigma \Leftrightarrow \varphi \notin \Sigma$
3 Todo conjunto finitamente modelável $\Sigma$ sobre um vocabulário $\mathcal{L}$ pode ser estendido a um conjunto finitamente modelável $\Sigma '$ sobre um vocabulário $\mathcal{L}'$ expansão simples de $\mathcal{L}$ com a seguinte propriedade: $$ (\exists x \varphi(x)) \in \Sigma \Rightarrow \exists \mathbf{c} \in \mathcal{L}' \, \varphi(\mathbf{c}) \in \Sigma '$$
4 Chamamos a propriedade descrita no exercício acima de Propriedade Henkin. Mostre que, dado um vocabulário $\mathcal{L}$, existe uma expansão simples $\mathcal{L}'$ de $\mathcal{L}$ tal que todo conjunto finitamente modelável de sentenças em $\mathcal{L}$ pode ser estendido a um conjunto finitamente modelável maximal Henkin em $\mathcal{L}'$
5 Seja $\Sigma$ um conjunto finitamente modelável maximal Henkin. Defina uma relação de equivalência nos termos livres de variáveis de $\mathcal{L}'$ a seguir: $$s \sim t :\equiv (s=t) \in \Sigma$$ $$\vert t \vert := \{ s \, : \, s \sim t \}$$
5.1 Prove que de fato $\sim$ é uma relação de equivalência
5.2 Construa um modelo $\mathcal{A}$ de modo que $t^{\mathcal{A}}=\vert t \vert$. Mostre que $f^{\mathcal{A}}(\vert t_1 \vert,\ldots,\vert t_n \vert) = \vert f(t_1,\ldots,t_n) \vert$
5.3 Use indução sobre sentenças para mostrar que, sendo $\varphi$ uma sentença, $\mathcal{A} \models \varphi \Leftrightarrow \varphi \in \Sigma$
5.4 Conclua que todo conjunto finitamente modelável Henkin é modelável e, portanto, segue o Teorema da Compacidade.
Ferramentas da página
