Prova de exaustão - Proof by exhaustion

Prova por exaustão , também conhecida como prova por casos , prova por análise de caso , indução completa ou o método da força bruta , é um método de prova matemática em que o enunciado a ser provado é dividido em um número finito de casos ou conjuntos de casos equivalentes , e onde cada tipo de caso é verificado para ver se a proposição em questão é válida. Este é um método de prova direta . Uma prova por exaustão normalmente contém dois estágios:

  1. Uma prova de que o conjunto de casos é exaustivo; ou seja, que cada instância da declaração a ser provada atende às condições de (pelo menos) um dos casos.
  2. Uma prova de cada um dos casos.

A prevalência de computadores digitais aumentou muito a conveniência de usar o método de exaustão (por exemplo, a primeira prova assistida por computador do teorema das quatro cores em 1976), embora tais abordagens também possam ser contestadas com base na elegância matemática . Os sistemas especialistas podem ser usados ​​para chegar a respostas a muitas das perguntas que lhes são feitas. Em teoria, o método da prova por exaustão pode ser utilizado sempre que o número de casos for finito. No entanto, como a maioria dos conjuntos matemáticos são infinitos, esse método raramente é usado para derivar resultados matemáticos gerais.

No isomorfismo de Curry-Howard , a prova por exaustão e a análise de caso estão relacionadas ao casamento de padrões no estilo ML .

Exemplo

A prova por exaustão pode ser usada para provar que se um inteiro for um cubo perfeito , então ele deve ser um múltiplo de 9, 1 mais que um múltiplo de 9 ou 1 menos que um múltiplo de 9.

Prova :
cada cubo perfeito é o cubo de algum inteiro n , onde n é um múltiplo de 3, 1 mais do que um múltiplo de 3 ou 1 menos que um múltiplo de 3. Portanto, esses três casos são exaustivos:

  • Caso 1: se n = 3 p , então n 3 = 27 p 3 , que é um múltiplo de 9.
  • Caso 2: Se n = 3 p  + 1, então n 3 = 27 p 3  + 27 p 2  + 9 p  + 1, que é 1 mais do que um múltiplo de 9. Por exemplo, se n  = 4, então n 3 = 64 = 9 × 7 + 1.
  • Caso 3: Se n = 3 p  - 1, então n 3 = 27 p 3  - 27 p 2  + 9 p  - 1, que é 1 menor que um múltiplo de 9. Por exemplo, se n = 5 então n 3 = 125 = 9 × 14 - 1. QED

Elegância

Os matemáticos preferem evitar as provas por exaustão com grande número de casos, que são vistos como deselegantes . Uma ilustração de como essas provas podem ser deselegantes é observar as seguintes provas de que todos os Jogos Olímpicos de Verão modernos são realizados em anos divisíveis por 4:

Prova : os primeiros Jogos Olímpicos de Verão modernos foram realizados em 1896 e, a partir de então, a cada 4 anos (negligenciando exceções, como quando os jogos não foram realizados devido à Primeira Guerra Mundial e à Segunda Guerra Mundial, juntamente com os Jogos Olímpicos de Tóquio de 2020 sendo adiados para 2021 devido a a pandemia COVID-19 ). Como 1896 = 474 × 4 é divisível por 4, as próximas Olimpíadas seriam no ano 474 × 4 + 4 = (474 ​​+ 1) × 4, que também é divisível por quatro, e assim por diante (esta é uma prova por indução matemática ) Portanto, a afirmação está provada.

A afirmação também pode ser comprovada pela exaustão listando todos os anos em que foram realizadas as Olimpíadas de verão e verificando se cada um deles pode ser dividido por quatro. Com 28 Jogos Olímpicos de Verão no total em 2016, esta é uma prova de exaustão com 28 casos.

Além de menos elegante, a prova por exaustão também exigirá uma caixa extra a cada vez que uma nova Olimpíada for realizada. Isso deve ser contrastado com a prova por indução matemática, que prova a afirmação indefinidamente no futuro.

Número de casos

Não há limite máximo para o número de casos permitidos em uma prova por exaustão. Às vezes, existem apenas dois ou três casos. Às vezes, pode haver milhares ou até milhões. Por exemplo, resolver rigorosamente um quebra-cabeça de final de jogo de xadrez pode envolver a consideração de um grande número de posições possíveis na árvore do jogo desse problema.

A primeira prova do teorema das quatro cores foi uma prova por exaustão com 1834 casos. Essa prova foi polêmica porque a maioria dos casos foi verificada por um programa de computador, não manualmente. A prova mais curta conhecida do teorema das quatro cores hoje ainda tem mais de 600 casos.

Em geral, a probabilidade de um erro em toda a prova aumenta com o número de casos. Uma prova com um grande número de casos deixa a impressão de que o teorema só é verdadeiro por coincidência, e não por causa de algum princípio ou conexão subjacente. Outros tipos de provas - como prova por indução ( indução matemática ) - são considerados mais elegantes . No entanto, existem alguns teoremas importantes para os quais nenhum outro método de prova foi encontrado, como

Veja também

Notas