Teorema da compacidade

O Teorema da Compacidade assegura que um conjunto ${\displaystyle \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 ${\displaystyle \Gamma _{0}\,\!}$ de ${\displaystyle \Gamma \,\!}$ também é satisfazível. Ou seja, se ${\displaystyle \Gamma \vdash \alpha }$, então, qualquer que seja ${\displaystyle \Gamma _{0}=\{\alpha _{1}{,...,}\alpha _{n}\}}$, com ${\displaystyle \Gamma _{0}\subseteq \Gamma }$, tem-se que ${\displaystyle \Gamma _{0}\vdash \alpha }$; reciprocamente, se, qualquer que seja ${\displaystyle \Gamma _{0}\subseteq \Gamma }$, tem-se que ${\displaystyle \Gamma _{0}\vdash \alpha }$, então ${\displaystyle \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 ${\displaystyle {\mathcal {F}}=\{F_{1},F_{2},F_{3},...\}}$ um conjunto de fórmulas e que todo subconjunto finito de ${\displaystyle {\mathcal {F}}}$ é satisfazível. Seja ${\displaystyle A_{1},A_{2},A_{3},...\,\!}$ uma lista, sem repetições, das fórmulas atômicas que ocorrem em ${\displaystyle F_{1}\,\!}$, seguida das fórmulas atômicas que ocorrem em ${\displaystyle F_{2}\,\!}$ (e não em ${\displaystyle F_{1}\,\!}$), e assim por diante.

Uma vez que cada subconjuto finito de ${\displaystyle {\mathcal {F}}}$ é satisfazível, para cada n existe uma valoração ${\displaystyle {\mathcal {A}}_{n}}$ tal que ${\displaystyle {\mathcal {A}}_{n}\models \land _{i=1}^{n}F_{n}}$. Então, cada ${\displaystyle F_{i}\,\!}$ em ${\displaystyle {\mathcal {F}}}$ é válido para todas estas valorações finitas. Assumimos que ${\displaystyle {\mathcal {A}}_{n}}$ é definido somente nas fórmulas atômicas que ocorrem em ${\displaystyle F_{1},F_{2},F_{3},...\,\!}$. Para cada ${\displaystyle n\,\!}$, os valores de verdade que ${\displaystyle {\mathcal {A}}_{n}}$ atribui para ${\displaystyle A_{1},A_{2},A_{3},...\,\!}$ formam uma sequência finita de 0's e 1's. Então ${\displaystyle 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 ${\displaystyle {\bar {\omega }}\,\!}$ na qual cada prefixo de ${\displaystyle {\bar {\omega }}\,\!}$ será também um prefixo de infitas sentenças de ${\displaystyle X\,\!}$.

Lema: Seja ${\displaystyle X\,\!}$ um conjunto infinito de strings binárias finitas. Existe uma string binária ${\displaystyle {\bar {\omega }}\,\!}$ infinita tal que qualquer prefixo de ${\displaystyle {\bar {\omega }}\,\!}$ é também prefixo de uma quantidade infinita de ${\displaystyle {\bar {x}}\,\!}$ em ${\displaystyle 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 ${\displaystyle X\,\!}$ de strings de tamanho finito como estas. Queremos construir uma string infinta ${\displaystyle {\bar {\omega }}\,\!}$ de 0's e 1's tal que cada prefixo de ${\displaystyle {\bar {\omega }}\,\!}$ é também prefixo de uma quantidade infinita de strings em ${\displaystyle X\,\!}$

Nós construiremos ${\displaystyle {\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 ${\displaystyle {\bar {\omega }}\,\!}$ como também excluiremos strings indesejáveis de ${\displaystyle X\,\!}$.

Para determinarmos qual deverá ser o primeiro dígito de ${\displaystyle {\bar {\omega }}\,\!}$, olhamos para os primeiros dígitos de todas as strings em ${\displaystyle 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 ${\displaystyle {\bar {\omega }}\,\!}$ será 1 e excluiremos de ${\displaystyle 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 ${\displaystyle {\bar {\omega }}\,\!}$ será 0.

Este mesmo procedimento pode ser repetido até obtermos n dígitos de ${\displaystyle {\bar {\omega }}\,\!}$. Neste n-ésimo passo, também teremos excluído de ${\displaystyle X\,\!}$ todas as strings que não começam com estes n dígitos, ficando apenas com um subconjunto ${\displaystyle X'\,\!}$, também infinito, de ${\displaystyle X\,\!}$. Para obter o (n+1)-ésimo, podemos repetir o mesmo procedimento: Uma vez que ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle {\bar {\omega }}\,\!}$ infinita na qual os primeiros n dígitos de ${\displaystyle {\bar {\omega }}\,\!}$ são iguais aos primeiros n dígitos de uma quanitade infinita de strings em ${\displaystyle X\,\!}$, finalizando a demonstração de nosso lema.

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

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

• Portal da matemática