Lógica e Matemática
O Óbvio que Induz o Não Óbvio
Carlos César de Araújo

Matemática para Gregos & Troianos

Introdução

Neste artigo enunciaremos um resultado sobre o conjunto © 2002-2006, Matemática para Gregos & Troianos - Carlos César dos números naturais que pode ser considerado bastante “óbvio”, mas (relativamente) pouco conhecido. Em seguida, passaremos o enunciado para a linguagem simbólica da Lógica e faremos algumas manipulações simples com quantificadores e conectivos (discutidas em outros artigos desta Seção), gradualmente transformando o enunciado original num outro equivalente. A surpresa é que, no final, obtemos um fato totalmente “diferente” que, embora mais familiar, é normalmente considerado muito menos óbvio.

Um Fato Óbvio

Um conjunto de números naturais pode não possui um maior elemento, mas tem sempre um menor, um primeiro. Não há como duvidar disso. É um fato que se pode aceitar como óbvio. Não importa se preferimos começar © 2002-2006, Matemática para Gregos & Troianos - Carlos César com © 2002-2006, Matemática para Gregos & Troianos - Carlos César ou © 2002-2006, Matemática para Gregos & Troianos - Carlos César: qualquer © 2002-2006, Matemática para Gregos & Troianos - Carlos César deve “começar” em algum número, que é o seu elemento mínimo — o menor de todos.

Observe que ao falarmos em “qualquer © 2002-2006, Matemática para Gregos & Troianos - Carlos César”, incluímos o caso © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Afinal, © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Todavia, o conjunto vazio é a única exceção à regra — o que também não deixa de ser óbvio, uma vez que © 2002-2006, Matemática para Gregos & Troianos - Carlos César não possui elemento algum (donde muito menos um menor). Assim, devemos consertar nossa afirmação e dizer: se © 2002-2006, Matemática para Gregos & Troianos - Carlos César e © 2002-2006, Matemática para Gregos & Troianos - Carlos César, então © 2002-2006, Matemática para Gregos & Troianos - Carlos César possui um menor elemento.

Tradução para a o Simbolismo Lógico

Uma formulação mais completa deve mencionar o quantificador “qualquer” que atua sobre © 2002-2006, Matemática para Gregos & Troianos - Carlos César, o que pode ser feito assim:

Expressão (1)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Por exportação, isto é o mesmo que

Expressão (2)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Agora, a sentença “© 2002-2006, Matemática para Gregos & Troianos - Carlos César possui um menor elemento” se decompõe na seguinte:

Expressão (3)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

(veja o artigo Teoria da Ordem na seção Conceitos Fundamentais), que por sua vez é equivalente a

Expressão (4)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

obtida da anterior por contraposição da implicação.  Substituindo a expressão (4) na expressão (2), ficamos com a seguinte asserção:

Expressão (5)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Tomando a contrapositiva da segunda implicação dessa sentença, o enunciado (1) torna-se

Expressão (6)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Dualidade Booleana

As fórmulas “© 2002-2006, Matemática para Gregos & Troianos - Carlos César” e “© 2002-2006, Matemática para Gregos & Troianos - Carlos César” na sentença (6) nos levam a considerar o seu dual booleano. Conforme vimos em outro artigo desta Seção, uma instância da dualidade booleana — que é de largo emprego — provém do fato de toda afirmação da forma (aqui particularizada a © 2002-2006, Matemática para Gregos & Troianos - Carlos César)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

ser equivalente a

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

obtida da primeira substituindo (cada ocorrência de) © 2002-2006, Matemática para Gregos & Troianos - Carlos César por © 2002-2006, Matemática para Gregos & Troianos - Carlos César, que é o complementar de © 2002-2006, Matemática para Gregos & Troianos - Carlos César em relação a © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Por simplicidade, escrevamos

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Desse modo, o dual booleano da sentença (6) é

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

que é o mesmo que

Expressão (7)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

O Passo Final

Por fim, eliminamos o sinal © 2002-2006, Matemática para Gregos & Troianos - Carlos César aplicando as regras de negação e a forma normal disjuntiva da implicação:

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Levando a última expressão na sentença (7), ficamos com o seguinte:

Expressão (8)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Um Fato Popular

Todas as manipulações que fizemos acima, da sentença (1) à sentença (8), alteram a estrutura sintática das sentenças, mas não sua semântica. Por outras palavras — embora não pareça —, a sentença (8) traduz exatamente o mesmo estado de coisas que o fato óbvio com o qual começamos. Agora, paremos para examinar nossa sentença final. Ela nos diz o seguinte:

(1) Considere um conjunto © 2002-2006, Matemática para Gregos & Troianos - Carlos César de números naturais (ou seja, © 2002-2006, Matemática para Gregos & Troianos - Carlos César);
(2) Tome um número © 2002-2006, Matemática para Gregos & Troianos - Carlos César qualquer. (Isso prepara o terreno para o que virá no escopo do quantificador © 2002-2006, Matemática para Gregos & Troianos - Carlos César.);
(3) Suponha que do fato de todo predecessor estrito de © 2002-2006, Matemática para Gregos & Troianos - Carlos César pertencer a © 2002-2006, Matemática para Gregos & Troianos - Carlos César (isto é, © 2002-2006, Matemática para Gregos & Troianos - Carlos César), se possa concluir que © 2002-2006, Matemática para Gregos & Troianos - Carlos César também pertence a © 2002-2006, Matemática para Gregos & Troianos - Carlos César (© 2002-2006, Matemática para Gregos & Troianos - Carlos César).
(4) Então pode-se concluir que todo elemento de © 2002-2006, Matemática para Gregos & Troianos - Carlos César pertence a © 2002-2006, Matemática para Gregos & Troianos - Carlos César (ou seja, © 2002-2006, Matemática para Gregos & Troianos - Carlos César).

Em vez de conjuntos (de números naturais), podemos falar em propriedades. Nesses termos, a expressão (8) incorpora um método para demonstrar afirmações da forma © 2002-2006, Matemática para Gregos & Troianos - Carlos César, onde © 2002-2006, Matemática para Gregos & Troianos - Carlos César é uma propriedade sobre números naturais (isto é, © 2002-2006, Matemática para Gregos & Troianos - Carlos César). Logo, a fim de provarmos que © 2002-2006, Matemática para Gregos & Troianos - Carlos César é verdadeira para todo © 2002-2006, Matemática para Gregos & Troianos - Carlos César, seguimos os mesmos passos acima, começando com (2). Ou seja, assumimos como hipótese que © 2002-2006, Matemática para Gregos & Troianos - Carlos César e daí tentamos provar que vale © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Se tivermos sucesso em fazê-lo, sem nenhuma restrição sobre © 2002-2006, Matemática para Gregos & Troianos - Carlos César, então teremos conseguido provar que © 2002-2006, Matemática para Gregos & Troianos - Carlos César é sempre verdadeira em © 2002-2006, Matemática para Gregos & Troianos - Carlos César.

Esse método de prova é popularmente conhecido como Princípio da Indução Forte ou Segundo Princípio da Indução, para diferenciá-lo da indução matemática em sua forma mais corriqueira (a do “raciocínio de © 2002-2006, Matemática para Gregos & Troianos - Carlos César para © 2002-2006, Matemática para Gregos & Troianos - Carlos César”). A relação de “força” entre essa duas formas de indução finita é tema de outro artigo desta Seção.

Óbvio, mas não Anônimo

Tendo mantido o suspense até este ponto, podemos revelar agora que o fato óbvio do qual partimos também tem um nome na literatura: Princípio da Boa Ordenação. Na teoria da ordem, dizemos que o “conjunto” © 2002-2006, Matemática para Gregos & Troianos - Carlos César é bem ordenado. (Veja o artigo Teoria da Ordem, Parte 3 na Seção Conceitos Fundamentais.) Assim, o que mostramos em nossa transição da sentença (1) para a sentença (8) é que a condição de boa ordenação é equivalente a uma forma forte de indução.

Uma Prova Tortuosa

Nos textos “ortodoxos” de matemática, essa equivalência não é explicitamente declarada; a maioria dos autores deriva apenas uma parte da dupla implicação, a saber, que o Segundo Princípio da Indução decorre do Princípio da Boa Ordenação (reforçando nossa opinião de que o primeiro é tomado como menos óbvio) — e isso de maneira indireta, por redução ao absurdo. Resumidamente, o argumento é o seguinte. Assuma que © 2002-2006, Matemática para Gregos & Troianos - Carlos César é bem ordenado. Agora, tome © 2002-2006, Matemática para Gregos & Troianos - Carlos César e suponha (hipótese de indução) que © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Devemos provar que © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Por absurdo (sic), admita que © 2002-2006, Matemática para Gregos & Troianos - Carlos César, isto é, que © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Então © 2002-2006, Matemática para Gregos & Troianos - Carlos César possui um mínimo, digamos, © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Logo, © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Mas isso, com a hipótese de indução, nos dá © 2002-2006, Matemática para Gregos & Troianos - Carlos César. Aqui surge a contradição: © 2002-2006, Matemática para Gregos & Troianos - Carlos César.

Esse argumento é logicamente impecável, mas é tortuoso. Nossa argumentação, por outro lado, expõe a essência lógica dos enunciados de uma maneira “limpa” e direta, mostrando que o Segundo Princípio da Indução é essencialmente a seguinte variação (do dual booleano) da sentença (2):

Expressão (9)

© 2002-2006, Matemática para Gregos & Troianos - Carlos César

Além disso, talvez torne mais evidente que os passos se aplicam a qualquer conjunto © 2002-2006, Matemática para Gregos & Troianos - Carlos César munido com uma relação © 2002-2006, Matemática para Gregos & Troianos - Carlos César que se comporte como a relação menor ou igual a em © 2002-2006, Matemática para Gregos & Troianos - Carlos César. (Isso inclui partes do próprio © 2002-2006, Matemática para Gregos & Troianos - Carlos César!) Essa generalização é um fato tão poderoso quanto espantoso, sobre o qual falaremos em outra ocasião.


Carlos César de Araújo, 11 de dezembro de 2006, 23:16:07