Teorema da compacidade

O Teorema da Compacidade assegura que um conjunto $\mathrm{\Gamma }$ qualquer formado por fórmulas bem formadas de um cálculo de predicados de primeira ordem é satisfazível se, e somente se, todo subconjunto finito ${\mathrm{\Gamma }}_0$ de $\mathrm{\Gamma }$ também é satisfazível. Ou seja, se $\mathrm{\Gamma }⊢\alpha$, então, qualquer que seja ${\mathrm{\Gamma }}_0=\{{\alpha }_1,...,{\alpha }_n\}$, com ${\mathrm{\Gamma }}_0\subseteq \mathrm{\Gamma }$, tem-se que ${\mathrm{\Gamma }}_0⊢\alpha$; reciprocamente, se, qualquer que seja ${\mathrm{\Gamma }}_0\subseteq \mathrm{\Gamma }$, tem-se que ${\mathrm{\Gamma }}_0⊢\alpha$, então $\mathrm{\Gamma }⊢\alpha$.

Este teorema denota uma importante propriedade para a lógica de predicados, pois garante que toda e qualquer fórmula é derivável (ou logicamente implicada, no caso semântico) a partir de um conjunto finito de premissas.

No caso proposicional, a propriedade da compacidade é consequência do Teorema de Tychonoff (que assegura que o produto de espaços compactos também é compacto) aplicado a espaços de Stone compactos, e daí segue o nome do teorema.

Definição

Seja Γ um conjunto de fórmulas da lógica proposicional. Γ é satisfazível se e somente se todo subconjunto finito de Γ é satisfazível. O teorema é válido mesmo que Γ seja infinito. Prova:

1. IDA Assuma que Γ seja satisfazível. Então existe uma valoração v que satisfaz Γ. Tome S como sendo um subconjunto qualquer de Γ. Tome v como valoração. Como v satisfaz ao conjunto todo (ou seja, satisfaz a Γ ), v satisfaz cada uma das partes. Logo v satisfaz S. Portanto, S é satisfazível.

2. VOLTA Assuma que todo subconjunto finito de Γ é satisfazível (nesse caso dizemos que Γ é FINITAMENTE SATISFAZÍVEL). Temos que provar que Γ é satisfazível, ou seja, que existe uma valoração v que satisfaz Γ.

Vamos aumentar Γ de forma consistente até quando esse processo chegue em um CONJUNTO MAXIMALMENTE CONSISTENTE, isto é, um conjunto ∆ tal que:

1. Para toda fórmula θ , θ ∈ ∆ ou ¬θ ∈ ∆ . 2. Para nenhuma fórmula δ , δ ∈ ∆ e ¬δ ∈ ∆ . Seja α0, α1, α2,... uma enumeração do conjunto de fórmulas PROP. Agora tome:

• ∆0 = Γ.
• ∆n+1 = {αn} U ∆n se {αn} é consistente com ∆n. caso contrário, ∆n+1 = Γ.

Faça ∆ = a união de todos os ∆i começando com i = 0.

Podemos afirmar que ∆ é FINITAMENTE SATISFAZÍVEL. A prova é por indução sobre n, mostrando que para todo n o ∆n é finitamente satisfazível.

Seja a seguinte valoração: v(x) = 1 se e somente se x ∈ ∆. Claramente v satisfaz a todas as fórmulas atômicas em ∆. Ou seja, precisamos provar que PARA TODA α ∈ PROP ^v(α) = 1 se e somente se α ∈ ∆.

Prova: por indução sobre a complexidade de α .

1. CASO BASE: α é atômica.

• Trivial, pois a própria definição de v atesta que v satisfaz α quando α é atômica e pertence a ∆.

2. CASOS INDUTIVOS: I) α é da forma ¬β. II) α é da forma (ρ∧θ). III) α é da forma (ρ∨θ ). IV) α é da forma (ρ→θ).

Demonstraremos apenas o caso da negação:

I) Hipótese Indutiva: ^v(β ) = 1 se e somente se β ∈ ∆ Tese: ^v(¬β ) = 1 se e somente se ¬β ∈ ∆

IDA: Se ^ v(¬β) = 1 então ¬β ∈ ∆ . Suponha que ¬β ∉ ∆. Como ∆ é maximalmente consistente então β ∈ ∆ .Logo, pela HI, ^v(β ) = 1. Daí, ^v(¬β ) = 0. Portanto, ^v(¬β ) ≠ 0.

VOLTA: Se ¬β ∈ ∆ , então ^ v(¬β ) = 1. Assuma que ¬β ∈ ∆. Como ∆ é maximalmente consistente, β ∉ ∆ . Da HI, ^ v(β ) = 0. Daí, ^ v(¬β ) = 1.

Demonstração

Suponha $ℱ=\{F_1,F_2,F_3,...\}$ um conjunto de fórmulas e que todo subconjunto finito de $ℱ$ é satisfazível. Seja $A_1,A_2,A_3,...$ uma lista, sem repetições, das fórmulas atômicas que ocorrem em $F_1$, seguida das fórmulas atômicas que ocorrem em $F_2$ (e não em $F_1$), e assim por diante.

Uma vez que cada subconjuto finito de $ℱ$ é satisfazível, para cada n existe uma valoração ${𝒜}_n$ tal que ${𝒜}_n\models \underset{i=1}{\overset{n}{\wedge }}{F}_n$. Então, cada $F_i$ em $ℱ$ é válido para todas estas valorações finitas. Assumimos que ${𝒜}_n$ é definido somente nas fórmulas atômicas que ocorrem em $F_1,F_2,F_3,...$. Para cada $n$, os valores de verdade que ${𝒜}_n$ atribui para $A_1,A_2,A_3,...$ formam uma sequência finita de 0's e 1's. Então $X=\{{𝒜}_n|n=1,2,...\}$ é um conjunto infinito de sequências binárias finitas.

Neste ponto, utilizaremos o seguinte lema para mostar que existe uma sequência binária finita $\overline{\omega }$ na qual cada prefixo de $\overline{\omega }$ será também um prefixo de infitas sentenças de $X$.

Lema: Seja $X$ um conjunto infinito de strings binárias finitas. Existe uma string binária $\overline{\omega }$ infinita tal que qualquer prefixo de $\overline{\omega }$ é também prefixo de uma quantidade infinita de $\overline{x}$ em $X$

Demonstração: Uma string binária é uma sequência de 0's e 1's como 1001. As strings 1, 10, 101, 1011 são os prefixos de 1011. Temos um conjunto infinito $X$ de strings de tamanho finito como estas. Queremos construir uma string infinta $\overline{\omega }$ de 0's e 1's tal que cada prefixo de $\overline{\omega }$ é também prefixo de uma quantidade infinita de strings em $X$

Nós construiremos $\overline{\omega }$ passo a passo da esquerda para a direita. Ao n-ésimo passo, não só saberemos qual será o n-ésimo dígito de $\overline{\omega }$ como também excluiremos strings indesejáveis de $X$.

Para determinarmos qual deverá ser o primeiro dígito de $\overline{\omega }$, olhamos para os primeiros dígitos de todas as strings em $X$ (obviamente existe uma quantidade infinita de strings, assumeremos que se possa verificar todas). Se, ao verificar todas as strings, houver um número infinito de strings que começam com 1, então o primeiro dígito de $\overline{\omega }$ será 1 e excluiremos de $X$ todas as strings que começam com 0 (Note que ainda continuaremos com um conjunto infinito de strings). De outra forma, ser houver apenas um número finito de strings que começam com 1, então excluiremos estas e o primeiro dígito de $\overline{\omega }$ será 0.

Este mesmo procedimento pode ser repetido até obtermos n dígitos de $\overline{\omega }$. Neste n-ésimo passo, também teremos excluído de $X$ todas as strings que não começam com estes n dígitos, ficando apenas com um subconjunto $X^{\prime }$, também infinito, de $X$. Para obter o (n+1)-ésimo, podemos repetir o mesmo procedimento: Uma vez que $X^{\prime }$ é infinito, possuirá uma quantidade infinita de strings de comprimento n+1 ou maior, logo se houver uma quantidade infinita de strings cujo (n+1)-ésimo dígito é 1, então o (n+1)-ésimo dígito de $\overline{\omega }$ também o será. Caso contrário, será 0 (em ambos os casos, também se exclui as strings indesejadas). Este conjunto resultante ainda será infinito.

Desta forma, continuando o procedimento, teremos uma sequência $\overline{\omega }$ infinita na qual os primeiros n dígitos de $\overline{\omega }$ são iguais aos primeiros n dígitos de uma quanitade infinita de strings em $X$, finalizando a demonstração de nosso lema.

Por fim, definimos uma valoração $𝒜$ sobre todas as ${𝒜}_n$'s como se segue: Seja $𝒜(A_n)$ o n-ésimo dígito de $\overline{\omega }$. Devemos demonstrar agora que toda fórmula $F$ em $ℱ$ vale em $𝒜$, o que segue do fato que $F$ vale em todas as finitas valorações em $X$. Seja $m$ tal que $F$ não contém nenuhuma fórmula atômica após $A_m$, então existe um ${𝒜}_n$ em $X$ tal que ${𝒜}_n\models F$ e as primeiras $m$ entradas de ${𝒜}_n$ são as mesmas de $𝒜$, donde segue que $𝒜\models F$

Assim, temos que toda fórmula no conjunto $ℱ$ vale sob a valoração $𝒜$, o que conclui nossa demonstração.

Aplicações

O Teorema da Compacidade pode ser usado para estabelecer que toda ordenação parcial de um conjunto infinito (porém contável) pode ser estendida a uma ordenação total. Usa-se o fato de que toda ordenação parcial de um conjunto finito pode ser estendida a uma ordenação total; isto pode ser demonstrado por indução sobre o tamanho do conjunto.

Ver também

• Lógica proposicional
• Teorema de Tychonoff

Referências

• Predefinição:Link
• Hendman, Shawn. A First Course of Logic. An introduction to Model Theory, Proof Theory, Computability and Complexity. Oxford University Press. 2004. 1ª edição.
• Teorema da Compacidade (em inlgês)
• en:Ruy de Queiroz