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 de primeira ordem é satisfazível se, e somente se, todo subconjunto finito $\Gamma _{0}\,\!$ de $\Gamma \,\!$ também é satisfazível. Ou seja, se $\Gamma \vdash \alpha$, então, qualquer que seja $\Gamma _{0}=\{\alpha _{1}{,...,}\alpha _{n}\}$, com $\Gamma _{0}\subseteq \Gamma$, tem-se que $\Gamma _{0}\vdash \alpha$; reciprocamente, se, qualquer que seja $\Gamma _{0}\subseteq \Gamma$, tem-se que $\Gamma _{0}\vdash \alpha$, então $\Gamma \vdash \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 ${\mathcal {F}}=\{F_{1},F_{2},F_{3},...\}$ um conjunto de fórmulas e que todo subconjunto finito de ${\mathcal {F}}$ é 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 ${\mathcal {F}}$ é satisfazí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 a 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)
• en:Ruy de Queiroz