O que é a lógica matemática

O que a lógica estuda

Todo conhecimento que não se obtém por observação direta se obtém raciocinando: de certas afirmações que se aceitam passa-se a outra que decorre delas. Em geometria, quem sabe que os ângulos de um triângulo somam dois retos conclui que nenhum triângulo tem dois ângulos obtusos; em medicina, quem sabe que certa doença produz febre, e que a pessoa examinada não a tem, descarta essa doença. A lógica é a disciplina que estuda quando essa passagem é legítima, e a lógica matemática é a que a estuda com os métodos da matemática: definindo com exatidão seus objetos, que são linguagens, fórmulas e deduções, e demonstrando teoremas sobre eles.

Para enunciar com precisão o que ela estuda, convém fixar primeiro o vocabulário. Uma proposição é uma sentença declarativa da qual faz sentido dizer que é verdadeira ou que é falsa: “$7$ é um número primo” é uma proposição verdadeira; “todo número par é maior que $5$”, uma proposição falsa. Não são proposições, em contrapartida, as perguntas (“que horas são?”), as ordens (“feche a porta”) nem as expressões com variáveis livres, como “$x$ é par”, cujo valor depende do que $x$ designe.

Um argumento é uma lista de proposições, as premissas, junto com outra proposição, a conclusão, que se apresenta como consequência delas. As premissas podem ser quaisquer proposições: verdadeiras, falsas, conhecidas ou meras suposições; a única coisa que as distingue é o lugar que ocupam no argumento. Escreveremos os argumentos com as premissas em linhas sucessivas e a conclusão precedida de “portanto”:

A lógica não é uma teoria da verdade

Se isso é assim, a lógica não tem por ofício averiguar se as premissas de um argumento são verdadeiras. Se $28$ é múltiplo de $4$, decide-o a aritmética; se uma pessoa tem febre, o termômetro; se uma batalha ocorreu em certo ano, a história. Tampouco lhe cabe definir o que é a verdade, questão que pertence à filosofia. A lógica admite que as proposições têm um valor de verdade, seja ele qual for, e estuda como esses valores se relacionam entre si: em particular, quando a verdade de umas proposições obriga à verdade de outra. Dito de outro modo, a lógica não é uma teoria da verdade, mas uma teoria da transmissão da verdade.

Ora, o que transmite a verdade não depende do tema do argumento, mas de sua estrutura. Compare-se o argumento anterior com este outro: “se um animal é um mamífero, respira ar; a baleia é um mamífero; portanto, a baleia respira ar”. Ambos têm a mesma forma: “se algo é $A$, é $B$; $c$ é $A$; portanto, $c$ é $B$”. A forma de um argumento é o que resta ao substituir seus termos não lógicos (números, animais, propriedades) por letras, conservando as palavras lógicas: “não”, “e”, “ou”, “se… então”, “todo”, “algum”. Cada argumento que se obtém de uma forma ao dar conteúdo a suas letras é uma instância dela.

Uma forma é válida quando nenhuma de suas instâncias tem todas as premissas verdadeiras e a conclusão falsa; um argumento é válido quando sua forma o é. Uma instância com premissas verdadeiras e conclusão falsa chama-se contraexemplo da forma: donde uma forma é inválida exatamente quando tem um contraexemplo.

Nas demonstrações desta aula usaremos uma taquigrafia do português: $V(A)$ abrevia “$A$ é verdadeira” e $F(A)$, “$A$ é falsa”; $\neg$ abrevia “não”, $\wedge$ abrevia “e”, $\vee$ abrevia “ou”, $\Rightarrow$ abrevia “se… então” e $\Leftrightarrow$ abrevia “se e somente se”; $\forall$ lê-se “para todo” e $\exists$, “existe”. Esses signos são aqui meras abreviaturas de palavras da metalinguagem, e as setas duplas ficam reservadas em todo o curso para esse uso. Na aula seguinte aparecerão os signos de um só traço, $\rightarrow$ e $\leftrightarrow$, junto com $\neg$, $\wedge$ e $\vee$, como abreviaturas de uma linguagem formal, com um sentido que o curso fixará com exatidão; a diferença de traço entre as setas lembrará em que nível se fala.

A proposição diz o que a validade garante; convém ver com igual clareza o que ela não garante. Das oito combinações possíveis entre a validade do argumento, a verdade de todas as suas premissas e a verdade da sua conclusão, apenas uma fica excluída, a do argumento válido com premissas verdadeiras e conclusão falsa; as demais ocorrem todas.

Disso decorre a regra prática que a aula exercitará: para mostrar que um argumento é inválido não basta apontar que alguma premissa ou a conclusão é falsa, e para mostrar que é válido não basta que tudo nele seja verdadeiro; o primeiro exige exibir um contraexemplo de sua forma, e o segundo, um raciocínio que valha para todas as instâncias.

Linguagem natural e linguagem formal

A definição de validade repousa sobre duas operações: reconhecer a forma de um argumento e decidir se uma proposição é verdadeira ou falsa. Ambas supõem que cada sentença tem uma só leitura. A linguagem natural, o português, o chinês ou o árabe, que os seres humanos aprendem sem instrução formal e usam para se comunicar, não cumpre essa condição: sua flexibilidade, que a torna apta para a poesia, a conversa e a nuance, torna-a também ambígua.

• Ambiguidade lexical: uma palavra tem vários significados. “Sentei no banco” pode referir-se a um assento ou a uma instituição financeira.
• Ambiguidade sintática: uma sentença admite várias estruturas. “O dobro de três mais quatro” pode ser $2 \cdot 3 + 4 = 10$ ou $2 \cdot (3 + 4) = 14$.
• Ambiguidade de escopo: não se sabe a que parte da sentença uma palavra lógica afeta. “Todos os alunos não passaram” pode significar que nenhum passou ou que nem todos passaram.
• Conectivos imprecisos: o “ou” umas vezes admite que ambas as alternativas se cumpram (“exige-se diploma ou experiência”) e outras o exclui (“café ou chá”); o “se… então” umas vezes expressa causa, outras uma regra, outras uma mera sucessão.

À ambiguidade soma-se um traço mais profundo: a linguagem natural pode falar de si mesma. Contém as palavras “sentença”, “verdadeiro” e “definir”, e com elas pode formar sentenças que se referem a si mesmas, como “esta sentença tem cinco palavras”. Essa autorreferência é, em geral, inofensiva; mas, como se verá, combinada com a noção de verdade produz sentenças que não podem ser nem verdadeiras nem falsas.

Uma linguagem formal é projetada para eliminar ambas as fontes de dificuldade. Fixa-se um alfabeto, uma coleção de símbolos, e algumas regras de formação que dizem, sem deixar margem a interpretação, que sequências de símbolos são expressões bem formadas; o significado de cada expressão fixa-se depois mediante definições igualmente precisas. Assim, perguntar se uma sequência de símbolos pertence à linguagem é uma questão que se resolve mecanicamente, verificando regras, e cada expressão se lê de uma só maneira. A linguagem deste curso, que a aula sobre a linguagem da lógica proposicional constrói, tem um alfabeto de apenas dois símbolos, o círculo $\sigO$ e o disco $\sigI$, e uma única regra de formação.

O preço é a flexibilidade: uma linguagem formal não serve para conversar, e cada linguagem formal expressa apenas o que suas regras permitem. Não é verdade, porém, que se sacrifique todo o poder expressivo: as linguagens formais da lógica de primeira ordem bastam para escrever quase toda a matemática. O que se sacrifica é a ambiguidade e a autorreferência descontrolada; o que se ganha é a possibilidade de demonstrar teoremas sobre a própria linguagem.

Linguagem-objeto e metalinguagem

Para estudar uma linguagem é preciso falar dela, e para falar dela é necessária outra linguagem. A linguagem-objeto é a linguagem que se estuda; a metalinguagem é a linguagem em que ela é estudada. Numa gramática latina escrita em português, o latim é a linguagem-objeto e o português a metalinguagem. Neste curso, a linguagem-objeto será a linguagem formal de círculos e discos, e a metalinguagem será o português, enriquecido com signos matemáticos e com letras gregas, $\varphi$, $\psi$, que designarão fórmulas quaisquer da linguagem-objeto sem pertencer a ela.

A distinção é central por uma razão precisa: as afirmações que o curso demonstrará sobre a linguagem formal (que toda fórmula se lê de uma só maneira, que tudo o que é dedutível é verdadeiro) não são fórmulas da linguagem formal, mas sentenças da metalinguagem. Por isso se chamarão metateoremas, para distingui-las dos teoremas que o sistema dedutivo produz dentro da linguagem-objeto.

Uma forma elementar da distinção é a que separa o uso de uma expressão de sua menção. Em “Roma é uma cidade” usa-se a palavra para falar da cidade; em “‘Roma’ tem quatro letras” menciona-se a palavra, e as aspas o indicam: a sentença fala da palavra, não da cidade. Confundir ambas as coisas produz enunciados absurdos, como “Roma tem quatro letras”, ou argumentos falaciosos, como “Roma é uma cidade; ‘Roma’ é uma palavra de quatro letras; portanto, uma cidade é uma palavra de quatro letras”.

Os paradoxos da linguagem

Uma contradição é uma afirmação junto com sua negação, como $V(A) \wedge \neg V(A)$. Um paradoxo é um raciocínio que, partindo de hipóteses que parecem aceitáveis e avançando por passos que parecem válidos, chega a uma contradição. Pela proposição sobre o que a validade garante, se os passos são de fato válidos, alguma hipótese é falsa: resolver um paradoxo consiste em encontrar qual. Convém não confundir o paradoxo com a ambiguidade, que é apenas a multiplicidade de leituras, nem com o meramente surpreendente.

O mentiroso

O paradoxo mais antigo desse gênero é atribuído a Eubulides de Mileto, no século IV antes da nossa era. Em sua forma precisa não fala de mentir, que supõe a intenção de enganar, mas de falsidade: seja $m$ a sentença “a sentença $m$ é falsa”. Para obter a contradição bastam duas hipóteses, que convém escrever explicitamente.

• Bivalência (B): toda proposição é verdadeira ou falsa, e não ambas as coisas; ser falsa equivale a não ser verdadeira.
• Esquema da verdade (T): uma sentença é verdadeira se e somente se o que ela diz é o caso. Por exemplo, “a neve é branca” é verdadeira se e somente se a neve é branca.

O teorema não diz que a lógica seja contraditória, mas que as duas hipóteses não podem sustentar-se ao mesmo tempo para uma linguagem que contém a sentença $m$. Há, portanto, três saídas: abandonar a bivalência e admitir sentenças sem valor de verdade; restringir o esquema da verdade; ou impedir que a linguagem forme a sentença $m$. A terceira é a de Alfred Tarski, em 1933: o predicado “é verdadeira” de uma linguagem não pertence a essa linguagem, mas à sua metalinguagem. Numa linguagem assim, $m$ não é uma sentença bem formada, e o paradoxo não pode ser enunciado.

O paradoxo de Berry

Publicado por Bertrand Russell em 1906, que o atribuiu a George Berry, bibliotecário de Oxford, esse paradoxo não usa a palavra “verdadeiro”, mas a palavra “definir”. Diz-se que uma frase do português define um número natural quando o descreve de modo que se possa identificá-lo sem ambiguidade: “o menor número primo maior que dez” define o $11$. Consideremos a frase “o menor natural que não pode ser definido com menos de vinte palavras”, que deve ser lida tal como está escrita, e chamemos $b$ o número que ela pretende definir. Os números naturais, neste curso, são $1, 2, 3, \ldots$

A exposição corrente, que se limita a observar que a frase tem menos de vinte palavras, omite metade do argumento: que o número $b$ existe, o que exige a finitude do vocabulário e a escolha do primeiro que falta. A hipótese que falha é a segunda: “definir” não é uma relação precisa do português, porque a frase que define $b$ usa a própria palavra “definir”, e seu sentido depende de quais frases contam como definições. Numa linguagem formal $L$ pode-se precisar o que significa “definível em $L$”, mas essa noção só se expressa na metalinguagem; a frase que define $b$ não pertence a $L$, e a contradição desaparece: $b$ não é definível em $L$ com poucos símbolos, embora o seja na metalinguagem.

O barbeiro e o conjunto de Russell

O paradoxo do barbeiro costuma ser contado assim: numa aldeia há um barbeiro, homem da aldeia, que barbeia todos os homens da aldeia que não se barbeiam a si mesmos, e somente a eles. O barbeiro barbeia a si mesmo? As palavras “e somente a eles” são essenciais: um barbeiro que barbeasse todos os que não se barbeiam a si mesmos, sem a restrição, poderia barbear também a si mesmo sem contradição alguma. O paradoxo é um caso particular de um lema geral, de forma diagonal, que convém demonstrar uma única vez.

A conclusão do barbeiro é inofensiva: ninguém havia afirmado que tal barbeiro existisse. O mesmo não ocorre com sua versão na teoria dos conjuntos. Em 1902, Russell escreveu a Gottlob Frege que seu sistema, que pretendia fundar a aritmética na lógica, admitia o seguinte princípio de compreensão: para toda propriedade há um conjunto cujos elementos são exatamente os objetos que a têm. Aplicado à propriedade de não pertencer a si mesmo, o princípio afirma que existe o conjunto

Diferentemente do barbeiro, aqui a existência de $Z$ não era uma suposição de um relato, mas um princípio da teoria. O paradoxo de Russell não se resolve declarando que $Z$ não existe, mas reformando a teoria: a teoria axiomática dos conjuntos de Zermelo, de 1908, só permite formar, com uma propriedade, subconjuntos de um conjunto já dado, e com essa restrição a contradição não se deduz.

O que não é um paradoxo

Chamou-se às vezes “paradoxo do conjunto vazio” à observação de que o conjunto vazio existe embora não tenha elementos, como se um objeto existente devesse ser feito de objetos existentes. Não há nisso contradição alguma: um conjunto não é feito de seus elementos como um muro de seus tijolos, mas fica determinado por eles, e a coleção dos elementos de um conjunto pode não ter nenhum, assim como uma caixa vazia continua sendo uma caixa. Que um fato surpreenda não o torna paradoxal; o paradoxo exige deduzir uma contradição, e aqui não se deduz nenhuma.

Como uma linguagem formal os trata

Do exposto decorre que uma linguagem formal não evita os paradoxos por arte de mágica, mas de duas maneiras precisas. A primeira é que ela pode carecer dos recursos que os produzem. A linguagem da lógica proposicional, que este curso constrói, não tem sentenças que se refiram a si mesmas nem um predicado de verdade: nela não se pode escrever a sentença do mentiroso, e sua semântica atribui a cada fórmula, em cada atribuição de valores às variáveis, um único valor de verdade. A segunda é que, em linguagens mais ricas, o paradoxo se converte em teorema: o raciocínio do mentiroso, feito com rigor, demonstra que a verdade de uma linguagem suficientemente expressiva não é definível nessa mesma linguagem (Tarski); o do barbeiro e de Russell demonstra que certas coleções não são conjuntos; e argumentos aparentados com o de Berry estão no coração dos teoremas de incompletude de Kurt Gödel, de 1931. Assim, o que na linguagem natural é uma perplexidade, numa linguagem formal é informação.

Os quatro pilares da lógica matemática

A lógica matemática nasceu no fim do século XIX e no começo do XX, com Frege, Peano, Russell e David Hilbert, como resposta a uma pergunta precisa: sobre que fundamentos repousa a matemática e se esses fundamentos estão livres de contradição. Hoje ela é dividida em quatro grandes ramos, que se entrelaçam constantemente.

• Teoria da prova: estuda as demonstrações formais como objetos matemáticos, isto é, como sequências finitas de fórmulas que seguem regras explícitas; pergunta o que pode ser demonstrado num sistema, se um sistema é consistente e como umas demonstrações se transformam em outras. A unidade de dedução deste curso é um primeiro contato com ela.
• Teoria dos modelos: estuda a relação entre uma linguagem formal e as estruturas que a interpretam, seus modelos; pergunta que estruturas satisfazem um conjunto de fórmulas e que propriedades das estruturas podem ser expressas numa linguagem dada. A unidade de semântica, com suas atribuições de valores de verdade, é sua versão mais elementar.
• Teoria dos conjuntos: estuda os conjuntos com axiomas precisos, como a de Zermelo e Fraenkel, na qual pode ser escrita quase toda a matemática; nasceu, em boa parte, da necessidade de evitar o paradoxo de Russell.
• Teoria da computabilidade: estuda que problemas podem ser resolvidos mediante um procedimento mecânico e quais não. A lógica proposicional é decidível, como o curso verá: existe um procedimento que decide num número finito de passos se uma fórmula é válida; a lógica de predicados, em contrapartida, não o é.

Nenhum pilar se estuda em profundidade sem tocar os demais: a completude, resultado central deste curso, é ao mesmo tempo um teorema da teoria da prova e da teoria dos modelos, e a decidibilidade que dela se obtém pertence à computabilidade.

O mapa do curso

O curso percorre, para a linguagem mais simples da lógica, a proposicional, o caminho completo de uma teoria lógica, em quatro unidades.

1. Linguagem: a sintaxe. Constrói-se a linguagem-objeto com seu alfabeto de dois símbolos e sua regra de formação, demonstra-se que cada fórmula se lê de uma só maneira, aprende-se a demonstrar por indução e traduzem-se para a linguagem formal enunciados e argumentos da linguagem natural, apontando o que a tradução conserva e o que perde.
2. Dedução: fixa-se um sistema de axiomas e de regras de inferência, e define-se o que significa que uma fórmula $\varphi$ se deduza de um conjunto de fórmulas $\Gamma$, o que se escreve $\Gamma \vdash \varphi$. É a face sintática da validade: manipular símbolos segundo regras, sem atender a seu significado.
3. Semântica: atribui-se a cada fórmula um valor de verdade em cada atribuição, e define-se o que significa que $\varphi$ seja consequência de $\Gamma$, o que se escreve $\Gamma \models \varphi$: toda atribuição que torna verdadeiras as fórmulas de $\Gamma$ torna verdadeira $\varphi$. É a face semântica da validade, a definição desta aula tornada precisa.
4. Metateoria: demonstra-se que ambas as faces coincidem. A correção diz que tudo o que é dedutível é consequência, e a completude, que toda consequência é dedutível. Estudam-se depois a compacidade e um método mecânico, a resolução, para decidir se um conjunto de fórmulas pode ser satisfeito.

Se isso é assim, o curso é o primeiro exemplo completo de uma teoria matemática cujo objeto é o próprio raciocínio; e todas as suas afirmações sobre a linguagem formal serão, como se viu nesta aula, sentenças da metalinguagem demonstradas com o rigor da matemática.

Problemas resolvidos

Os problemas seguintes exercitam, em dificuldade crescente, as distinções da aula: refutar um argumento cujas sentenças são todas verdadeiras, separar as leituras de um enunciado ambíguo, classificar expressões da linguagem-objeto e da metalinguagem, e analisar dois raciocínios de aparência paradoxal para decidir se o são.

Problemas propostos

Os dois primeiros problemas exercitam a validade e a ambiguidade; o terceiro, o uso e a menção; os dois últimos pedem analisar um paradoxo novo e aplicar o lema diagonal fora da linguística. Cada um tem uma pista, que convém abrir apenas depois de tê-lo tentado.