Questão 6. (Princípio da Indução Forte). Seja
um número natural, e seja
uma propriedade. Suponha que, para cada
, tenhamos a seguinte implicação: se
é verdadeira para todos os naturais
, então
também é verdadeira. Conclua que
é verdadeira para todos os números naturais
.
Passo 1
O enunciado nos dá as seguintes informações e pede uma conclusão:
- Há um número natural inicial
. - Para cada
com vale a implicação: - A pergunta é: concluir que
é verdadeira para todos os números naturais .
Passo 2
Vou explicar o conceito que aparece aqui (sem usar jargões complicados): a hipótese do enunciado diz que, ao provar
para um certo
, está-se autorizado a assumir que
já vale para todos os naturais menores que
(mas maiores ou iguais a
). Isso é a forma chamada de “indução forte” ou “indução completa”. Antes de provar, duas ideias úteis:
- Verdade vacuamente: se eu digo “para todos
com , a propriedade vale” e não existe nenhum nessa faixa (o que ocorre quando ), então essa afirmação universal é considerada verdadeira automaticamente — diz-se que é verdadeira de forma vacuosa. - Princípio do mínimo contraexemplo (princípio do bom ordenamento): um subconjunto não vazio de naturais tem um menor elemento. Vou usar essa ideia para chegar a uma contradição caso exista algum
em que falhe.
Passo 3
Prova por contradição com mínimo contraexemplo. Suponha, para obter contradição, que nem todos os
satisfazem
. Defina o conjunto dos contraexemplos:
Pela suposição,
é não vazio.
Passo 4
Pelo princípio do bom ordenamento, como
é um subconjunto não vazio dos naturais, existe um menor elemento em
; chame-o de
. Logo:
e por minimalidade, para todo
com
tem-se
, isto é,
é verdadeira.
Passo 5
Agora examine a hipótese do enunciado aplicada ao
. A hipótese exige exatamente: se
é verdadeira para todos os
, então
é verdadeira. Mas, pelo passo anterior, sabemos que
é verdadeira para todos esses
. Portanto, pela hipótese do enunciado, segue que
é verdadeira.
Passo 6
Obtivemos uma contradição:
significa que
é falsa, enquanto a aplicação da hipótese dá que
é verdadeira. A única hipótese que levou a essa contradição foi supor que
era não vazio. Logo
deve ser o conjunto vazio.
Passo 7
Se
é vazio, não existe nenhum
em que
seja falsa. Portanto
é verdadeira para todos os naturais
. (Observação pedagógica: em particular, no caso
a condição antecedente é vacuamente verdadeira, então já garante
; a partir daí pode-se continuar usando a hipótese para todos os
.)