Caros, Corrigindo:
Afinal, a completude semântica > da lógica de predicados no caso finito é apenas um caso especial da > completude semântica para o caso geral (infinito), demonstrado por Gödel > na sua tese de doutorado. > Não. Segundo o teorema de Trakhtenbrot, não há sistema dedutivo cujos teoremas são exatamente as sentenças válidas (para uma linguagem canônica) em todas as estruturas finitas. Essa propriedade também é chamada de incompletude (semântica, como você diz). Claro que também temos, como corolário, que a validade em estruturas finitas não é recursiva (decidível). Se por incompletude sintática você quer dizer o mesmo que negação incompletude (não vale que uma entre A e ~A é teorema, para qualquer sentença A), então incompletude sintática também não é o mesmo que indecidibilidade. Há contraexemplos triviais: a lógica proposicional é decidível e não é negação completa, a lógica de primeira ordem com um símbolo de propriedade (unário) também é contraexemplo, a teoria dos domínios com no máximo k>1 elementos com igualdade apenas, etc. A demonstração do teorema de Trakhtenbrot é simples: Dada uma máquina de Turing m e uma entrada n, há uma sentença canônica A_mn que descreve a operação de m com entrada n na interpretação padrão. A sentença A_mn tem modelo finito se e somente se m para com a entrada n. De fato, por um lado, A_mn é satisfeita na subestrutura da interpretação padrão cujo domínio é o intervalo de operação de m com a entrada n. Por outro lado, é fácil ver que se m não para com a entrada n então A_mn só tem modelos infinitos. Segue-se do problema da parada que a satisfatibilidade em estruturas finitas não é recursiva. Como a satisfatibilidade em estruturas finitas é recursivamente enumerável (a satisfatibilidade em cada estrutura finita é recursiva), temos que a validade em estruturas finitas não é recursivamente enumerável. Portando, não há sistema dedutivo (recursivamente enumerável) que tenha como teoremas exatamente as sentenças válidas em todas as estruturas finitas. Fim. Referências: Alguns livros de lógica "undergraduate" contém os detalhes. Ebbinghaus, Flum e Thomas é um deles. Pessoalmente, gosto (mais) do Boolos, Burgess e Jeffrey, mas neste o teorema de Trakhtenbrot é enunciado em um exercício apenas. Abraço Rodrigo -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para [email protected]. Para postar neste grupo, envie um e-mail para [email protected]. Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/cddf00d9-0f65-4584-8463-10d7d5c814be%40dimap.ufrn.br.
