The Mathematics of Logic
11 de Abril de 2010 ⋅ Lógica

Lógica matematizada

Rui Daniel Cunha
The Mathematics of Logic: A Guide to Completeness Theorems and Their Applications, de Richard Kaye
Cambridge: Cambridge University Press, 2007, 216 pp.
Comprar

Richard Kaye é o autor deste exigente manual avançado de lógica moderna, apresentado do ponto de vista algébrico. A sua complexidade torna-o, paradoxalmente, um manual extremamente interessante para o leitor já experiente no material canónico da maioria dos livros introdutórios de lógica. Isto deve-se tanto ao facto de Kaye avançar decididamente para a exposição de resultados metalógicos, que normalmente não fazem parte do material canónico das introduções à lógica, quanto ao facto de Kaye optar pela apresentação do material em lógica algébrica, abordagem que também não é comum na maior parte dos manuais. Recorde-se, porém, que uma das primeiras apresentações em língua portuguesa da perspectiva algébrica do cálculo proposicional se deve ao Professor Francisco Miraglia, da Universidade de São Paulo, no seu livro Cálculo Proposicional: Uma Interação da Álgebra e da Lógica (CLE, Unicamp, 1987).

No Prefácio, Kaye expõe sumariamente a sua concepção da lógica:

“A característica principal da lógica é que deve ser acerca do raciocínio ou da dedução, deve tentar fornecer regras para as inferências válidas. Se estas regras forem definidas de forma suficientemente precisa (e devem sê-lo), tornam-se regras para a manipulação de séries de símbolos numa página. O passo seguinte é adicionar significado a estas séries de símbolos e tentar apresentar uma justificação matemática para as regras de inferência. Tipicamente, apresenta-se dois teoremas distintos: o primeiro é o “Teorema da Consistência”, que diz que nenhuma dedução incorrecta pode ser feita a partir das regras de inferência; o segundo é o “Teorema da Completude”, que diz que todas as deduções correctas que podem ser expressas no sistema podem de facto ser feitas utilizando uma combinação das regras de inferência fornecidas” (p. VIII).

É deste modo que Kaye justifica o seu objectivo principal: a compreensão do conteúdo matemático do teorema da completude da lógica de primeira ordem, cuja demonstração original, publicada em 1930, se deve ao maior lógico do século XX, Kurt Gödel. Para o leitor principiante, convém não confundir este teorema da completude da lógica de primeira ordem com o teorema da incompletude da aritmética formal, também de Gödel e publicado em 1931, e que é o seu resultado mais famoso: a existência de proposições verdadeiras mas indemonstráveis no sistema formal da aritmética — o chamado primeiro teorema da incompletude — e a impossibilidade de demonstrar a consistência da aritmética formal com os próprios meios desse sistema formal — o chamado segundo teorema da incompletude.

A partir do Teorema da Completude, e especificamente da sua demonstração, Kaye encontra técnicas matemáticas relevantes para a construção de novas estruturas matemáticas:

“Assim, a lógica não é apenas acerca de conectivas como “e” e “ou”, apesar de os sistemas principais, incluindo a lógica proposicional e a lógica de primeira ordem, terem símbolos para estas conectivas. O poder da técnica lógica para o matemático surge do modo como o sistema formal de dedução pode ajudar a organizar um conjunto complexo de condições que podem ser exigidas numa construção ou demonstração matemática. O Teorema da Completude torna-se uma forma muito geral e poderosa de construir estruturas matemáticas interessantes. Um exemplo típico é a aplicação da lógica de primeira ordem à construção de sistemas numéricos com infinitesimais, que podem ser utilizados rigorosamente para apresentar o cálculo real. É a chamada análise não canónica de Abraham Robinson, e é apresentada no último capítulo deste livro” (p. IX).

Ao centrar o seu manual na questão da completude da lógica de primeira ordem, Kaye, ainda que implicitamente, toma partido no conhecido problema da determinação das fronteiras da lógica, isto é, no problema de saber que teorias se deve considerar que pertencem ao âmbito da lógica, e que teorias se deve considerar que não pertencem ao seu âmbito. Em particular, o problema é distinguir a lógica da matemática, ou seja, de determinar que critérios possibilitam traçar uma linha divisória entre teorias lógicas e teorias não lógicas, isto é, matemáticas.

A completude é efectivamente um desses critérios de demarcação entre lógica e matemática, e é, aliás, o critério também defendido pelos professores William e Martha Kneale, na obra O Desenvolvimento da Lógica, publicada entre nós pela Fundação Gulbenkian. Assim, segundo este critério, pertencem ao âmbito da lógica as teorias que sejam completas, como é nomeadamente o caso do cálculo proposicional e do cálculo de predicados de primeira ordem. Teorias completas são aquelas teorias em que, para qualquer fórmula bem formada a da teoria T, ou a é demonstrável em T, ou a sua negação, não-a, é demonstrável em T. Pelo contrário, as teorias que sejam incompletas, como é nomeadamente o caso da teoria de conjuntos ou da aritmética formal, já são teorias que não podem ser exaustivamente caracterizadas estabelecendo regras de inferência, pelo que estão fora do âmbito da lógica — são teorias matemáticas. Teorias incompletas são aquelas teorias em que não ocorre que, para qualquer fórmula bem formada a da teoria T, ou a é demonstrável em T, ou a sua negação, não-a, é demonstrável em T.

A decidibilidade, por exemplo, seria um critério alternativo da demarcação entre lógica e matemática mais estrito do que a completude: seriam parte da lógica apenas aquelas teorias que fossem decidíveis, como é nomeadamente o caso do cálculo proposicional. Teorias decidíveis são aquelas teorias para as quais existe um processo construtivo (isto é, executável num número finito de passos), para determinar, para qualquer fórmula bem formada a da teoria T, se existe uma demonstração de a em T. Pelo contrário, estariam fora do âmbito da lógica teorias indecidíveis, como é nomeadamente o caso, além da teoria de conjuntos e da aritmética formal, do próprio cálculo de predicados de primeira ordem, visto que embora existam processos de decisão para uma série de casos especiais da teoria da quantificação, não existe um processo geral de decisão para todo o cálculo de predicados de primeira ordem. Teorias indecidíveis são teorias para as quais não existe um processo construtivo para determinar, para qualquer fórmula bem formada a da teoria T, se existe uma demonstração de a em T.

Para Frege, claro, o problema não se colocava, visto Frege defender a inexistência de uma demarcação entre a lógica e a matemática. Segundo a sua tese logicista, a matemática é parte da lógica. Por exemplo, as noções da aritmética poderiam ser definidas em termos das noções requeridas para a lógica em geral, e as leis da aritmética poderiam ser derivadas dos princípios requeridos para a lógica em geral. Que o programa logicista não é exequível, pelo menos na sua formulação original, sabemo-lo graças a Bertrand Russell, que descobriu uma contradição no sistema de Frege (o chamado “paradoxo de Russell”).

Tentemos enumerar sinteticamente, e de modo não técnico, o material básico de cada capítulo, para se compreender a estrutura da obra.

Kaye dedica o Cap. 1 ao lema de König, depois de apresentar os conceitos prévios de árvore, árvore binária e árvore infinita. O lema de König assevera então que qualquer árvore binária infinita (com infinitos nós) tem pelo menos um ramo infinito. Este resultado é significativo, visto que Kaye explica assim tal papel central do lema de König:

“O teorema central deste livro, o teorema da completude para a lógica de primeira ordem, não só tem o mesmo “sabor” do Lema de König como é de facto uma generalização poderosa dele” (p. 6).

Aqui, ao contrário do que sucede noutros capítulos da obra, o formalismo matemático não é particularmente difícil, mesmo para um leitor não matemático.

No Cap. 2, Kaye introduz o conceito de “ordem” e chega, através do conceito de conjunto parcialmente ordenado (poset, no original inglês), ao lema de Zorn. O lema de Zorn diz-nos que qualquer poset tem um elemento maximal, desde que tenha a propriedade de Zorn, isto é, que cada subconjunto completamente ordenado dos seus membros tenha majorante, como explica Kaye na p. 15. De seguida, Kaye relaciona este lema de Zorn com o axioma da escolha (da teoria de conjuntos):

“Acontece que não apenas o axioma da escolha chega para provar o Lema de Zorn, mas também que a conversa é verdadeira: do Lema de Zorn pode demonstrar-se o Axioma da Escolha” (p. 16).

As demonstrações são então apresentadas (pp. 21-22). Conclui Kaye:

“A contribuição de Zorn parece ser a de fornecer um princípio útil e forte, que é equivalente a estes [o axioma da escolha e o princípio da boa ordem] e que pode ser facilmente utilizado em álgebra e noutros contextos, sem a terminologia problemática da teoria de conjuntos, que era na altura comum” (p. 22).

O Cap. 3 é dedicado ao conceito de “sistema formal”, procedendo Kaye à sua caracterização detalhada, bem como à exemplificação do mesmo:

“Os sistemas formais são tipos de jogos matemáticos com séries de símbolos e regras precisas. Imitam a ideia de uma “demonstração” ” (p. 24).

O estudo preciso de tais demonstrações, utilizando os símbolos e regras dos sistemas formais, dá origem a um dos ramos principais da lógica moderna, a teoria da demonstração:

“As derivações formais ou demonstrações são objectos matemáticos finitos, e como tal são objectos de uma teoria matemática. Isto deve-se ao facto de termos especificado exactamente que regras serão permitidas numa demonstração, e não termos deixado isso ao juízo subjectivo de outro ser humano. De facto, o ramo da lógica matemática chamado teoria da demonstração estuda as demonstrações como objectos matemáticos” (p. 26).

O capítulo quatro é dedicado às derivações com posets. Escreve Kaye:

“O ponto principal do capítulo é ilustrar os métodos nucleares da lógica, dos sistemas formais e da semântica” (p. 48).

Introduzem-se aqui numerosos exemplos de demonstrações formais, bem como a regra da reductio ad absurdum, para posteriores utilizações. A completar cada capítulo, e este não é excepção, surgem, assinaladas com asterisco, secções opcionais, com material ainda mais avançado e de maior complexidade conceptual, bem como, por vezes, de grande exigência no formalismo matemático.

No Cap. 5, Kaye expõe álgebras de Boole e introduz conceitos como o de “reticulado” (lattice):

“Conjuntos parcialmente ordenados e linearmente ordenados podem ser interessantes, mas não são verdadeiramente “lógica” no sentido usual da palavra: não representam enunciados lógicos nem são modelos de operações lógicas, como “não”, “e”, ou “ou”. Vamos agora investigar tipos especiais de posets chamados álgebras de Boole, cujos elementos podem ser utilizados para representar proposições lógicas” (p. 55).

O estudo da lógica do ponto de vista algébrico foi iniciado por George Boole, ainda antes do trabalho de Frege. Interessantemente, a secção final opcional deste capítulo (pp. 61-63) consiste na distinção que se pode estabelecer entre a álgebra de Boole moderna e a inicial, tal como George Boole a apresentou nos livros The Mathematical Analysis of Logic (1847) e An Investigation of the Laws of Thought (1854). Por exemplo, Boole nunca estipulou um conjunto completo de axiomas para a sua álgebra, nem utilizou símbolos para “e” e “ou”, mas antes as operações da multiplicação e da adição.

No Cap. 6, intitulado “Lógica Proposicional”, o que se vai construir é então um sistema formal para demonstrações com álgebras de Boole, concluindo-se o capítulo com uma secção opcional onde Kaye apresenta o teorema da decidibilidade da lógica proposicional. A abordagem algébrica é uma opção constante de Kaye, e, a meu ver, torna o seu livro significativamente mais difícil para os leitores cuja formação de base não seja a matemática.

O Cap. 7, intitulado “Valorações” (Valorations), consiste na construção de uma semântica para o cálculo proposicional, com a introdução de tabelas de verdade, a partir do material de álgebra de Boole anteriormente apresentado. Como escreve Kaye:

“Utilizámos as álgebras de Boole para representar o material mais tradicional da “lógica proposicional” ” (pg. 90).

Podemos preferir a apresentação tradicional deste material à abordagem algébrica, sobretudo porque é intuitiva e mais didáctica. Kaye, porém, pensa diferentemente, com base na maior aplicabilidade matemática deste tipo de ponto de vista.

Segue-se o Cap. 8, um dos mais difíceis da obra, a meu ver, acerca de filtros e ideais, incluindo a apresentação de conceitos como o de “homoformismo”, que conclui com duas secções opcionais uma acerca do teorema de Tychonov (que envolve espaços topológicos) e outra acerca do teorema da representação de Stone, que estabelece um isomorfismo entre as álgebras de Boole e álgebras de conjuntos.

Finalmente, no Cap. 9 entra-se na lógica de primeira ordem, o tradicionalmente chamado cálculo de predicados. A sua importância é adequadamente assinalada por Kaye:

“A lógica proposicional é a lógica das afirmações que podem ser verdadeiras ou falsas, ou que tomam algum valor numa álgebra de Boole. A lógica da maior parte da argumentação matemática envolve mais do que isto: envolve objectos matemáticos de um ou outro domínio, tais como o conjunto dos números naturais, números reais, números complexos, etc. Se introduzirmos tais objectos no nosso sistema formal para demonstrações, obtemos aquilo que é conhecido como lógica de primeira ordem, ou lógica predicativa.

Tal como acontece com qualquer uma das nossas outras lógicas, a lógica de primeira ordem não seria tão interessante se fosse apenas um sistema para escrever e verificar mecanicamente demonstrações formais de um domínio particular do trabalho matemático. Mas, felizmente, pode ser interpretada numa classe bastante geral de estruturas matemáticas, e a teoria de tais estruturas é uma espécie de teoria algébrica generalizada, que se aplica igualmente bem a grupos, anéis, campos e muitas outras estruturas familiares, pelo que a lógica de primeira ordem pode ser aplicada a um domínio amplo de áreas da matemática” (p. 116).

Kaye trata então de apresentar o material predicativo, com as suas regras específicas e demonstrações dos principais resultados, seguindo-se uma secção opcional final acerca de lógicas de segunda ordem e superiores, em que a quantificação não se limita a elementos de um domínio (não vazio), mas também inclui predicados e classes.

O Cap. 10 é o capítulo nuclear do livro: aí se apresentam e demonstram os teoremas da completude e da compacidade da lógica de primeira ordem, através de um método que se deve ao lógico Leon Henkin (a “henkinização”). Em rigor, trata-se de metateoremas, visto que fazem parte da metalinguagem acerca da linguagem objecto, que no caso é uma lógica de primeira ordem.

Não se apresenta, contudo, o resultado negativo para a decidibilidade da lógica predicativa, cuja demonstração se deve a Alonzo Church, em 1936. A indecidibilidade do cálculo de predicados de primeira ordem é, aliás, um dos mais importantes resultados de outro ramo fundamental da lógica moderna, a teoria da computabilidade.

O Cap. 11 onze é dedicado a outro ramo essencial da lógica moderna — a teoria dos modelos. Com a teoria da demonstração e a teoria da computabilidade, estes são os três principais ramos da lógica moderna (admitindo que a teoria dos conjuntos não faz parte do universo da lógica e pondo de lado a lógica intuicionista, iniciada por Brouwer). É outro capítulo complexo e difícil, onde Kaye também aborda a cardinalidade de conjuntos infinitos e o contributo de Cantor, com a teoria dos números transfinitos, bem como o ideal subjacente ao programa de Hilbert:

“Era uma espécie de Santo Graal da lógica do início do século XX encontrar um sistema de demonstrações para toda a matemática, ou para grande parte dela, como por exemplo a teoria dos números ou a teoria dos conjuntos, que fosse completo para a sua própria linguagem. Tal sistema, em princípio, colocaria os matemáticos no desemprego, sendo substituídos por um computador a produzir os teoremas. Que este Graal é de facto inatingível foi mais tarde demonstrado por Gödel, em 1931. Contudo, durante a procura de tais teorias, algumas pessoas, tais como Tarski e Hilbert, encontraram sistemas interessantes de primeira ordem que eram completos para as suas (limitadas) linguagens” (p. 171).

Também o Cap. 12, o capítulo final, acerca da análise não canónica, é um capítulo sofisticado. Escreve Kaye:

“Os teoremas da completude e da compacidade para a lógica de primeira ordem são interessantes do ponto de vista dos fundamentos da matemática, que é aquilo para que originariamente se destinavam, mas também fornecem uma caixa de ferramentas lógicas poderosas, que pode ser aplicada a outras áreas da matemática. Uma das mais excitantes aplicações dos teoremas da completude e da compacidade é a descoberta de Robinson de que podem ser utilizados para conferir um sentido perfeitamente rigoroso à ideia de número infinitesimal e para utilizar infinitesimais para apresentar o material da análise tradicional, incluindo a continuidade e a diferenciabilidade. Robinson chamou ao seu método “análise não canónica” ” (p. 182).

A concluir o livro existe um índice remissivo de nomes e conceitos (pp. 200-204), bem como uma bibliografia básica (p. 199). Do índice de nomes, aliás, não consta sequer Aristóteles (o que talvez se afigure uma injustiça). Mas este é um manual de lógica moderna, e não uma história da lógica. E a lógica moderna já nada tem a ver com Aristóteles.

Trata-se, em resumo, de um manual avançado, complexo, e exigente, com imenso material lógico para o leitor explorar detidamente, escrito por um matemático e destinado a iniciar na lógica moderna, sob a perspectiva algébrica, quem é estudante de matemática. Também pode ser recomendado, apesar da sua dificuldade, a quem não é de matemática (estudantes de filosofia, designadamente), desde que se possua já um conhecimento muito bom de lógica moderna, como será o caso de estudantes de lógica da pós-graduação, por exemplo. Não é de todo, porém, um manual para iniciar principiantes não matemáticos na lógica, dada a sua dificuldade e exigência conceptual. Também não é, seguramente, para professores de filosofia do secundário — e, contudo, que bom seria que aqueles que ensinam a tal “lógica aristotélica” aos seus alunos compreendessem que nada estão a ensinar-lhes do que é verdadeiramente a lógica, como este manual de Kaye amplamente demonstra.

Há um site na Internet para acompanhar este manual de Richard Kaye, segundo é indicado no livro, em que contém material adicional, exercícios e sugestões de resposta aos exercícios.

Evitei deliberadamente nesta recensão a simbologia matemática: é agora a altura de o leitor interessado em lógica moderna, e já com bastante experiência nela, começar a pagar a dívida contraída, por assim dizer, trabalhando o livro de Kaye, porque o que permitiu justamente a emergência da lógica moderna, com Frege, foi a sua matematização — não há lógica verdadeira sem matematização. Há mais de um século que sabemos isto. Como escreveu Quine, “a lógica é uma disciplina antiga, e desde 1879 é uma grande disciplina”.

Rui Daniel Cunha
Gabinete de Filosofia da Educação
Faculdade de Letras da Universidade do Porto
Termos de utilização ⋅ Não reproduza sem citar a fonte