Questão 6. (Princípio da Indução Forte). Seja m_{0} um número natural, e seja P(m) uma propriedade. Suponha que, para cada m \geq m_{0}, tenhamos a seguinte implicação: se P\left(m^{\prime}\right) é verdadeira para todos os naturais m_{0} \leq m^{\prime}<m, então P(m) também é verdadeira. Conclua que P(m) é verdadeira para todos os números naturais m \geq m_{0}.

Passo 1

O enunciado nos dá as seguintes informações e pede uma conclusão:
  • Há um número natural inicial m_{0}.
  • Para cada m com m\ge m_{0} vale a implicação: \text{se }P(m')\text{ é verdadeira para todos os naturais }m_{0}\le m'<m,\text{ então }P(m)\text{ é verdadeira.}éãé
  • A pergunta é: concluir que P(m) é verdadeira para todos os números naturais m\ge m_{0}.

Passo 2

Vou explicar o conceito que aparece aqui (sem usar jargões complicados): a hipótese do enunciado diz que, ao provar P(m) para um certo m, está-se autorizado a assumir que P(m') já vale para todos os naturais menores que m (mas maiores ou iguais a m_{0}). 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 m' com m_{0}\le m'<m, a propriedade P(m') vale” e não existe nenhum m' nessa faixa (o que ocorre quando m=m_{0}), 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 m\ge m_{0} em que P(m) falhe.

Passo 3

Prova por contradição com mínimo contraexemplo. Suponha, para obter contradição, que nem todos os m\ge m_{0} satisfazem P(m). Defina o conjunto dos contraexemplos:
S=\{m\in\mathbb{N} \mid m\ge m_{0}\text{ e }P(m)\text{ é falsa}\}.é
Pela suposição, S é não vazio.

Passo 4

Pelo princípio do bom ordenamento, como S é um subconjunto não vazio dos naturais, existe um menor elemento em S; chame-o de m_{1}. Logo:
m_{1}\in S,\qquad m_{1}\ge m_{0},
e por minimalidade, para todo m' com m_{0}\le m'<m_{1} tem-se m'\notin S, isto é, P(m') é verdadeira.

Passo 5

Agora examine a hipótese do enunciado aplicada ao m=m_{1}. A hipótese exige exatamente: se P(m') é verdadeira para todos os m_{0}\le m'<m_{1}, então P(m_{1}) é verdadeira. Mas, pelo passo anterior, sabemos que P(m') é verdadeira para todos esses m'. Portanto, pela hipótese do enunciado, segue que P(m_{1}) é verdadeira.

Passo 6

Obtivemos uma contradição: m_{1}\in S significa que P(m_{1}) é falsa, enquanto a aplicação da hipótese dá que P(m_{1}) é verdadeira. A única hipótese que levou a essa contradição foi supor que S era não vazio. Logo S deve ser o conjunto vazio.

Passo 7

Se S é vazio, não existe nenhum m\ge m_{0} em que P(m) seja falsa. Portanto P(m) é verdadeira para todos os naturais m\ge m_{0}. (Observação pedagógica: em particular, no caso m=m_{0} a condição antecedente é vacuamente verdadeira, então já garante P(m_{0}); a partir daí pode-se continuar usando a hipótese para todos os m>m_{0}.)

Resposta

P(m) é verdadeira para todos os números naturais m\ge m_{0}.

Exercícios relacionados