Demonstração por absurdo

A demonstração por absurdo é uma técnica de demonstração muito popular. Se queremos demonstrar que uma proposição vale, negamos essa proposição, supomos que a sua negação é verdadeira e tentamos chegar a alguma contradição. O objetivo é demonstrar que a hipótese que escolhemos leva a algum absurdo.

Exemplo trivial

Tomemos a afirmação “não existe o menor número racional positivo”. Demonstramos essa afirmação por absurdo negando-a primeiro: “existe o menor número racional positivo”, e vamos chamar esse número de q. Se q é o menor número racional positivo, então não somos capazes de encontrar um número racional positivo menor — porque, nesse caso, o número q não seria o menor.

Vamos usar isso na busca da contradição. Se, apesar disso, encontrarmos um número menor que q, que podemos escolher livremente, então chegamos a uma contradição e a proposição negada não vale. Se escolhermos como o menor número, por exemplo, 0,1, vemos que o número 0,01 é menor. Depois, 0,001 é ainda menor, 0,0001 é de novo menor e assim por diante. Basta dividir o número q por dez e obtemos um número menor. Na verdade, basta dividi-lo por qualquer número maior que um, por exemplo, por dois — a metade do número q certamente será menor que o número q inteiro.

Ou seja, o número q/2 certamente é menor que q e, ao mesmo tempo, é um número racional positivo. Com isso chegamos a uma contradição com a afirmação negada; logo, a afirmação negada não vale e, portanto, vale a afirmação original, não negada.

Números interessantes

Uma demonstração clássica e engraçada que ilustra o princípio do absurdo é o exemplo a seguir. Suponhamos que existam números naturais que são, de algum modo, interessantes. Por exemplo, o número 2 é interessante, porque vale que 2 · 2 = 2 + 2, uma propriedade bastante atípica. O número 42 é interessante, porque é a resposta para tudo. E assim por diante. A pergunta é: existem infinitos números interessantes?

Suponhamos o contrário, isto é, que existam apenas finitos números interessantes e que alguns números são desinteressantes. Reunimos esses números naturais desinteressantes no conjunto dos números desinteressantes. Agora escolhemos o menor número desinteressante. Peraí, o menor número desinteressante? Isso soa bem interessante, não? :-)

Com isso chegamos a uma contradição, porque o menor número desinteressante é, na verdade, bem interessante; logo, não pode existir o menor número desinteressante e, por conseguinte, o conjunto dos números desinteressantes precisa ser necessariamente vazio.

É claro que isso é um absurdo, não definimos direito o que é um número interessante, mas o procedimento de demonstração em si está correto.

Demonstração de que os números primos são infinitos

Neste exemplo, vamos mostrar um procedimento semelhante ao do capítulo anterior, mas desta vez já será correto em todos os aspectos.

Número primo é um número que é divisível por apenas dois números diferentes — ele mesmo e o um. Observe que a definição não é satisfeita pelo um e é satisfeita pelo dois.

A decomposição em fatores primos, ou fatoração, é a decomposição de um número natural, exceto o um, em um produto de números primos. É uma propriedade bastante interessante dos números naturais. Pegue qualquer número natural (exceto o um) e vale que ele pode ser decomposto em um produto de vários (inclusive iguais) números primos. Exemplos:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

A afirmação sobre a decomposição em fatores primos se chama teorema fundamental da aritmética. Entre outras coisas, ela nos diz que essa decomposição é única, isto é, não encontraremos duas decomposições diferentes em fatores primos de um mesmo número natural. Além disso, somente os números primos têm a decomposição em fatores primos formada por um único número — eles mesmos. Ou seja, a decomposição do sete em fatores primos seria o número sete. Vamos usar esses fatos na construção da demonstração da afirmação seguinte.

Agora vamos demonstrar a afirmação “há infinitos números primos”. Novamente, negamos a afirmação: “há uma quantidade finita de números primos”. Suponhamos que a sequência de números

$$a_1,a_2,a_3,\dots ,a_n$$

represente todos os números primos existentes. Se nessa sequência estão todos os números primos, então certamente vale que já não seremos capazes de encontrar um número que seja primo e, ao mesmo tempo, não esteja nessa sequência. Todos os números primos estão na sequência; fora da sequência não pode aparecer nenhum número primo.

Se queremos chegar a uma contradição, precisamos então montar algum número primo que não esteja nessa sequência. Para isso, vamos usar o número q. Montamos esse número multiplicando todos os números primos da sequência e somando um:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Agora precisamos mostrar que esse número ou é primo, ou de algum modo gera um número primo. Sabemos que q é um número natural e que todo número natural pode ser expresso como um produto de números primos. No entanto, nenhum número primo a_i divide q sem resto, sempre sobra um na divisão. Se tentássemos dividir o número q, por exemplo, pelo número primo a₂, o resultado seria este:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

Primeiro, dividimos a fração em duas. Na primeira fração, simplificamos a₂ e sobra um produto de números primos, que é simplesmente algum outro número inteiro sem importância. Na segunda fração, não há o que simplificar; essa fração será sempre um número não inteiro (porque o denominador não pode ser um, o um não é número primo). Na soma, então, obtemos um número que não é inteiro, ou seja, o número primo a₂ não divide o número q.

Com isso, demonstramos que nenhum dos números primos da sequência a_n divide o número q. (Observação: mostramos isso apenas para a₂, mas é fácil generalizar, se trocarmos a₂ por um a_i genérico.) Mas, como todo número natural pode ser decomposto em um produto de números primos, devem existir outros números primos, que não estão na sequência a_n, mas que são a fatoração do número q. Ao mesmo tempo, o próprio número q pode muito bem ser primo, e a decomposição em fatores primos incluirá apenas o número q. Então, mais uma vez, o último raciocínio:

1. Todo número natural pode ser expresso como algum produto de números primos.
2. Pela hipótese, a sequência a_n contém todos os números primos existentes.
3. Ajustamos a primeira afirmação: todo número natural pode ser expresso como produto de termos escolhidos da sequência a_n, porque ela contém todos os números primos.
4. Demonstramos que nenhum número da sequência a_n divide o número q.
5. Com isso surgiu uma contradição com a hipótese → se precisamos ser capazes de decompor todo número natural em um produto de números primos e a sequência a_n não contém nenhum número que divida q, então devem existir outros números primos que dividem q e são a decomposição em fatores primos do número q.

Com isso chegamos a uma contradição. A decomposição em fatores primos do número q inclui números primos que não estão contidos na sequência que supusemos conter todos os números primos. Logo, não vale a afirmação negada, vale a afirmação original, não negada. Há infinitos números primos.