Teorema da compacidade

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Teorema da Compacidade assegura que um conjunto \Gamma \,\! qualquer formado por fórmulas bem-formadas de um cálculo de predicados primeira ordem é satisfazível se e somente se todo subconjunto finito \Gamma_0 \,\! de \Gamma \,\! também é satisfazí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.

Definição[editar | editar código-fonte]

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[editar | editar código-fonte]

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 à 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]