Lógica e Matemática
Uma Aplicação da Indução
Carlos César de Araújo

Matemática para Gregos & Troianos

Introdução

Como se sabe, o Princípio da Indução Matemática (em sua versão clássica) fornece um método para provar sentenças do tipo

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (1)

onde © 2002-2007, Matemática para Gregos & Troianos - Carlos César é uma propriedade aplicável a números naturais e © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Em sua forma fraca, mais simples, a técnica repousa sobre o fato de (1) ser logicamente equivalente a

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (2)

(A equivalência entre (1) e (2) pode ser proposta como uma definição, aceita como um axioma ou derivada como um teorema. Veja o artigo Indução desta seção.)

Também é amplamente sabido que o método acima se aplica a objetos diferentes dos números naturais, contanto que possuam alguma característica mensurável por esses números. Então, pode-se tentar provas indutivas em © 2002-2007, Matemática para Gregos & Troianos - Carlos César usando essa “medida”. Exemplificando, a fim de provarmos que todo polígono satisfaz uma certa propriedade, podemos fazê-lo por “indução no número de lados” da seguinte maneira: (i) verificamos a propriedade para polígonos de três lados; (ii) mostramos que se a propriedade valer para polígonos de © 2002-2007, Matemática para Gregos & Troianos - Carlos César lados, continuará válida para polígonos de © 2002-2007, Matemática para Gregos & Troianos - Carlos César lados.

O exemplo dos polígonos nos permite conceber facilmente o caso geral: dada uma função © 2002-2007, Matemática para Gregos & Troianos - Carlos César, trata-se de provar afirmações da forma

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

por “indução em © 2002-2007, Matemática para Gregos & Troianos - Carlos César”. Isto é menos óbvio quando © 2002-2007, Matemática para Gregos & Troianos - Carlos César não ocorre em © 2002-2007, Matemática para Gregos & Troianos - Carlos César. (Um exemplo em que © 2002-2007, Matemática para Gregos & Troianos - Carlos César ocorre em © 2002-2007, Matemática para Gregos & Troianos - Carlos César é: “[Num domínio de integridade] todo polinômio de grau © 2002-2007, Matemática para Gregos & Troianos - Carlos César [© 2002-2007, Matemática para Gregos & Troianos - Carlos César] possui no máximo © 2002-2007, Matemática para Gregos & Troianos - Carlos César zeros.”)

Surpreendentemente, não é fácil encontrar um enunciado geral desse método nos compêndios. Por exemplo, não encontramos uma formalização em textos como [2] e [4], escritos por lógicos eminentes num período em que [1] ditava os padrões de rigor na Matemática. Uma exceção recente é [3] (Cap. 1, p.39), mas o autor deixa a demonstração como exercício, numa forma não imediatamente reconhecível. Seja como for, neste artigo preenchemos essas lacunas registrando o procedimento e, principalmente, justificando-o de maneira simples e direta.

Enunciado do Procedimento

A técnica de indução à qual nos referimos envolve os seguintes componentes:

• um conjunto © 2002-2007, Matemática para Gregos & Troianos - Carlos César;

• uma função © 2002-2007, Matemática para Gregos & Troianos - Carlos César.

• um © 2002-2007, Matemática para Gregos & Troianos - Carlos César tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César.

Por exemplo, se © 2002-2007, Matemática para Gregos & Troianos - Carlos César é o conjunto dos polígonos, então © 2002-2007, Matemática para Gregos & Troianos - Carlos César pode ser o número de lados. Nesse caso, © 2002-2007, Matemática para Gregos & Troianos - Carlos César, já que todo polígono tem no mínimo três lados.

Voltando ao caso geral, suponha que se queira provar

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (3)

“por indução” em © 2002-2007, Matemática para Gregos & Troianos - Carlos César. O plano consiste em dois passos:

Passo 1. Prove que se um © 2002-2007, Matemática para Gregos & Troianos - Carlos César qualquer é tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César, então © 2002-2007, Matemática para Gregos & Troianos - Carlos César;

Passo 2. Tome um © 2002-2007, Matemática para Gregos & Troianos - Carlos César “arbitrário” e admita a seguinte hipótese de indução: se um © 2002-2007, Matemática para Gregos & Troianos - Carlos César é tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César, então © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Deduza que se um © 2002-2007, Matemática para Gregos & Troianos - Carlos César é tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César, então © 2002-2007, Matemática para Gregos & Troianos - Carlos César.

Antes de mostrarmos como (3) é conseqüência desses passos, lembramos que o sucesso dessa estratégia não pode ser garantido de maneira absoluta, pois depende da propriedade © 2002-2007, Matemática para Gregos & Troianos - Carlos César e de uma escolha acertada da função © 2002-2007, Matemática para Gregos & Troianos - Carlos César. O Passo 2 envolve a transição mais difícil: nos casos em que é possível passar de © 2002-2007, Matemática para Gregos & Troianos - Carlos César para © 2002-2007, Matemática para Gregos & Troianos - Carlos César, a função © 2002-2007, Matemática para Gregos & Troianos - Carlos César sempre reflete alguma característica estrutural dos elementos de © 2002-2007, Matemática para Gregos & Troianos - Carlos César que pode ser especificada recursivamente a partir de uma definição indutiva de © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Isso conduz naturalmente ao exame da indução estrutural, assunto de outro artigo desta seção.

Demonstração

Vejamos como os passos (1) e (2) implicam (3). Cremos que a conexão ficará mais transparente se usarmos livremente a linguagem dos conjuntos. Em particular, usaremos a notação © 2002-2007, Matemática para Gregos & Troianos - Carlos César para a imagem inversa de © 2002-2007, Matemática para Gregos & Troianos - Carlos César por © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Um momento de reflexão mostra que a afirmação a ser provada no Passo 1 é

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (4)

onde, por comodidade, cometemos o abuso de empregar a mesma letra (© 2002-2007, Matemática para Gregos & Troianos - Carlos César) para denotar uma propriedade e o conjunto correspondente. Fica claro, então, que o Passo 2 consiste em provar

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (5)

(É intuitivamente óbvio que o Passo 2 equivale à derivação desta sentença, mas isto pode ser rigorosamente estabelecido por meio do Teorema da Dedução do Cálculo de Predicados.)

Justificaremos o procedimento se mostrarmos que (4) e (5) acarretam (3) na forma

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

Suponha que (4) e (5) foram provados. Então temos um caso de (2), com © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Segue-se do Princípio da Indução que

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

Mas esta sentença é equivalente a

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (6)

(Veja o artigo A União é o Supremo.) Ora, por hipótese, © 2002-2007, Matemática para Gregos & Troianos - Carlos César, condição que é equivalente a

© 2002-2007, Matemática para Gregos & Troianos - Carlos César (7)

Resulta  de (6) e (7) que © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Era o que devíamos provar.

Em suma, podemos dizer que uma prova de (3) por “indução em © 2002-2007, Matemática para Gregos & Troianos - Carlos César” corresponde a provar © 2002-2007, Matemática para Gregos & Troianos - Carlos César por “indução em © 2002-2007, Matemática para Gregos & Troianos - Carlos César”.

Exercícios

Exercício 1. Outra maneira de provar (3) por indução é a seguinte. Dado © 2002-2007, Matemática para Gregos & Troianos - Carlos César, suponha que do fato de valer © 2002-2007, Matemática para Gregos & Troianos - Carlos César para todo © 2002-2007, Matemática para Gregos & Troianos - Carlos César tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César, se possa concluir que vale © 2002-2007, Matemática para Gregos & Troianos - Carlos César para todo © 2002-2007, Matemática para Gregos & Troianos - Carlos César tal que © 2002-2007, Matemática para Gregos & Troianos - Carlos César. Justifique este procedimento usando o Segundo Princípio da Indução.

Exercício 2. Em nossa apresentação, há alguma restrição sobre © 2002-2007, Matemática para Gregos & Troianos - Carlos César que permita concluir algo sobre sua cardinalidade? Por exemplo, podemos concluir que © 2002-2007, Matemática para Gregos & Troianos - Carlos César, isto é, que © 2002-2007, Matemática para Gregos & Troianos - Carlos César deve ser no máximo um conjunto infinito enumerável?

Referências

[1] Bourbaki, Nicholas. Elements of mathematics I, Theory of sets. Hermann, 1968.

[2] Feferman, Solomon. The Number Systems: Foundations of Algebra and Analysis. Reading, Mass.: Addison-Wesley Publishing Co., Inc., 1964.

[3] Mitchell, John C. Foundations for Programming Languages, MIT Press, 1996. (O capítulo 1 se encontra disponível em http://theory.stanford.edu/~jcm/books.html.)

[4] Rosser, J. Barkley. Logic for mathematicians, McGraw-Hill, New York, 1953.

Carlos César de Araújo, 20 de janeiro de 2007, 18:52:44