Prova por contradição

Prova por contradição (ou redução ao absurdo, do latim reductio ad absurdum) é um método de prova matemática indireta, não-construtiva. Este tipo de prova é feito assumindo-se como verdade o contrário do que queremos provar e então chegando-se a uma contradição.

A prova por contradição é muito usada em teoremas de existência. Neste caso, é usada para provar a existência de um elemento com determinada característica, sem no entanto mostrar tal elemento. Por esta razão, alguns matemáticos a evitam quando possível, preferindo métodos de prova construtivos. O argumento de diagonalização de Cantor para demonstrar a não-enumerabilidade dos números reais normalmente é provado por contradição, embora possa ser pensado como uma prova construtiva ^[1].

Exemplo

Prove que existem infinitos números primos.

Prova: Suponha por absurdo, que existem n (uma quantidade finita) números primos, denotados por p₁, p₂, ..., p_n. Considere o número x = p₁p₂...p_n + 1. O número x não é divisível por nenhum dos números p₁, p₂, ..., p_n (o resto da divisão é sempre 1). Logo, existe um primo diferente de p₁, p₂ ... p_n que divide x. Isto contradiz a nossa hipótese inicial de que existem apenas n números primos. Então nossa hipótese inicial está errada e portanto existem infinitos números primos.