Teorema da compacidade

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

O Teorema da Compacidade assegura que um conjunto 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 de também é satisfazível. Ou seja, se , então, qualquer que seja , com , tem-se que ; reciprocamente, se, qualquer que seja , tem-se que , então .

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 um conjunto de fórmulas e que todo subconjunto finito de é satisfazível. Seja uma lista, sem repetições, das fórmulas atômicas que ocorrem em , seguida das fórmulas atômicas que ocorrem em (e não em ), e assim por diante.

Uma vez que cada subconjuto finito de é satisfazível, para cada n existe uma valoração tal que . Então, cada em é válido para todas estas valorações finitas. Assumimos que é definido somente nas fórmulas atômicas que ocorrem em . Para cada , os valores de verdade que atribui para formam uma sequência finita de 0's e 1's. Então é 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 na qual cada prefixo de será também um prefixo de infitas sentenças de .

Lema: Seja um conjunto infinito de strings binárias finitas. Existe uma string binária infinita tal que qualquer prefixo de é também prefixo de uma quantidade infinita de em
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 de strings de tamanho finito como estas. Queremos construir uma string infinta de 0's e 1's tal que cada prefixo de é também prefixo de uma quantidade infinita de strings em
Nós construiremos passo a passo da esquerda para a direita. Ao n-ésimo passo, não só saberemos qual será o n-ésimo dígito de como também excluiremos strings indesejáveis de .
Para determinarmos qual deverá ser o primeiro dígito de , olhamos para os primeiros dígitos de todas as strings em (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 será 1 e excluiremos de 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 será 0.
Este mesmo procedimento pode ser repetido até obtermos n dígitos de . Neste n-ésimo passo, também teremos excluído de todas as strings que não começam com estes n dígitos, ficando apenas com um subconjunto , também infinito, de . Para obter o (n+1)-ésimo, podemos repetir o mesmo procedimento: Uma vez que é 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 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 infinita na qual os primeiros n dígitos de são iguais aos primeiros n dígitos de uma quanitade infinita de strings em , finalizando a demonstração de nosso lema.

Por fim, definimos uma valoração sobre todas as 's como se segue: Seja o n-ésimo dígito de . Devemos demonstrar agora que toda fórmula em vale em , o que segue do fato que vale em todas as finitas valorações em . Seja tal que não contém nenuhuma fórmula atômica após , então existe um em tal que e as primeiras entradas de são as mesmas de , donde segue que

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