Prova por exaustão

Prova por exaustão, também conhecido como prova por casos, indução perfeita ou método de força bruta, é um método de prova matemática em que a afirmação a ser provada é dividida em um número finito de casos e cada caso é checado para verificar se a afirmação é correta. Esse é um método de prova direta. A prova por exaustão é composta por duas etapas:

1. A prova de que os casos são exaustivos; isto é, que cada parte da afirmação a ser provada corresponde com as condições de (pelo menos) um dos casos.
2. A prova de cada um dos casos.

Exemplo

Para provar que um número inteiro que é um cubo perfeito é um múltiplo de nove, ou é um a mais que um múltiplo de nove, ou o um a menos que um múltiplo de nove.

Prova: Cada número cúbico é o cubo de um número inteiro n. Cada número inteiro é ou um múltiplo de 3, ou 1 a mais ou 1 a menos que um múltiplo de 3. Então esses 3 casos são exaustivos:

• Caso 1: Se n = 3p, então n³ = 27p³, que é um múltiplo de 9.
• Caso 2: Se n = 3p+1, então n³ = 27p³ + 27p² + 9p + 1, que é um 1 a mais que um múltiplo de 9. Por exemplo, se n = 4, então n³ = 64 = 9x7 + 1.
• Caso 3: Se n = 3p - 1, então n³ = n³ = 27p³ − 27p² + 9p − 1, que é 1 a menos que um múltiplo de 9. Por exemplo, se n=5, então n³ = 125 = 9x14 -1.∎

Número de casos

Não há um limite máximo para o número de casos permitidos na prova por exaustāo. Ás vezes há apenas dois ou três casos. Ás vezes há milhares ou até milhões de casos. Por exemplo, solucionando o final de um jogo de xadrez pode involver considerar um grande número de possíveis posições na árvore de decisão do problema.

A primeira prova do teorema das quatro cores foi uma prova por exaustão com 1,936 casos. Essa prova foi controversia porque a maioria dos casos foram verificados por um programa de computador, e não a mão. A menor prova conhecida do teorema das quatro cores ainda tem 600 casos.

Matemáticos preferem evitar provas com um grande número de casos, pois é um método pouco elegante, e a probabilidade de erro aumenta com o número de casos. Uma prova com um grande número de casos dá a impressão de que o teorema é verdadeiro apenas por coincidência, e não por um princípio ou conexão. Outros tipos de prova, como a prova por indução, são consideradas mais elegantes. No entanto, há importantes teoremas para quais nenhum outro método de prova foi encontrado, como

• A prova de que não há um plano projetivo finito de ordem 10.
• A classificação de grupos simples finitos.
• A conjetura de Kepler.