Teorema da compacidade

O Teorema da Compacidade assegura que um conjunto $\Gamma \,\!$ qualquer formado por fórmulas bem-formadas de um cálculo de predicados primeira ordem é satisfatível se e somente se todo subconjunto finito $\Gamma_0 \,\!$ de $\Gamma \,\!$ também é satisfatível. Por exemplo:

Se $\Gamma \vdash \alpha$ então existe um subconjunto finito $\Gamma_0 = \{\alpha_1{,...,}\alpha_n\} \subseteq \Gamma$ tal que $\Gamma_0 \vdash \alpha$, onde $\Gamma \,\!$ é um uma instância do conjunto $\Sigma_0 \,\!$ acima citado.

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.

Demonstração

Suponha $\mathcal F = \{F_1, F_2, F_3, ... \}$ um conjunto de fórmulas e que todo subconjunto finito de $\mathcal F$ é satisfatí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 $\mathcal F$ é satisfatível, para cada n existe uma valoração $\mathcal A_n$ tal que $\mathcal A_n \models \land_{i=1}^{n} F_n$. Então, cada $F_i \,\!$ em $\mathcal F$ é válido para todas estas valorações finitas. Assumimos que $\mathcal A_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 $\mathcal A_n$ atribui para $A_1, A_2, A_3,... \,\!$ formam uma sequência finita de 0's e 1's. Então $X = \{ \mathcal A_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 $\bar\omega \,\!$ na qual cada prefixo de $\bar\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 $\bar\omega \,\!$ infinita tal que qualquer prefixo de $\bar\omega \,\!$ é também prefixo de uma quantidade infinita de $\bar{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 $\bar\omega \,\!$ de 0's e 1's tal que cada prefixo de $\bar\omega \,\!$ é também prefixo de uma quantidade infinita de strings em $X \,\!$

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

Para determinarmos qual deverá ser o primeiro dígito de $\bar\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 $\bar\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 $\bar\omega \,\!$ será 0.

Este mesmo procedimento pode ser repetido até obtermos n dígitos de $\bar\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' \,\!$, também infinito, de $X \,\!$. Para obter o (n+1)-ésimo, podemos repetir o mesmo procedimento: Uma vez que $X' \,\!$ é 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 $\bar\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 $\bar\omega \,\!$ infinita na qual os primeiros n dígitos de $\bar\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 $\mathcal A$ sobre todas as $\mathcal A_n$'s como se segue: Seja $\mathcal A(A_n)$ o n-ésimo dígito de $\bar\omega \,\!$. Devemos demonstrar agora que toda fórmula $F \,\!$ em $\mathcal F$ vale em $\mathcal A$, 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 $\mathcal A_n$ em $X \,\!$ tal que $\mathcal A_n \models F$ e as primeiras $m \,\!$ entradas de $\mathcal A_n$ são as mesmas de $\mathcal A$, donde segue que $\mathcal A \models F$

Assim, temos que toda fórmula no conjunto $\mathcal F$ vale sob a valoração $\mathcal A$, 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

• PlanetMath - proof of compactness theorem for first order logic
• 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)