Exercício 2. Dado um número natural
, seja
um conjunto com as seguintes propriedades: Prove que
contém todos os números naturais maiores do que ou iguais a
.
;
Passo 1
O enunciado (completando a propriedade que é padrão neste tipo de exercício) nos dá as seguintes informações:
-
é um número natural fixo. -
é um subconjunto dos naturais. - As propriedades de
são: -
. - Sempre que
então . (fechamento por sucessor)
O que precisa ser provado: mostrar quecontém todos os números naturais maiores ou iguais a , isto é, provar que
-
Passo 2
Ideia da técnica que vamos usar (explicação didática da indução):
- A prova por indução é uma forma sistemática de mostrar que uma propriedade vale para todos os naturais a partir de um ponto inicial
. - Definimos a propriedade
como: “ ”. - O princípio da indução (na versão iniciando em
) diz: se -
é verdadeira, e - para todo
, ,
entãoé verdadeira para todo .
-
- Intuição: a base dá o ponto de partida; o passo indutivo garante que, a partir de qualquer número em que a propriedade vale, o próximo também vale; repetindo, alcançamos todos os naturais a partir de
.
Vou aplicar esse princípio aqui:é a declaração “ ”.
Passo 3
Base da indução:
- Pela hipótese do enunciado temos explicitamente que
. - Ou seja,
é verdadeira.
Passo 4
Passo indutivo:
- Suponha que para algum
já tenhamos , isto é, suponha . - Pela segunda propriedade de
(fechamento por sucessor), a partir de segue que . - Logo
para todo .
Passo 5
Conclusão por indução:
- Aplicando o princípio da indução (com base em
e no passo indutivo verificado), obtemos que é verdadeira para todo . - Em palavras: todos os naturais
tais que pertencem a .
Passo 6
Observação alternativa (método do menor contraexemplo, útil para entender por que a indução funciona):
- Suponha, para obter contradição, que exista algum
com . - Pelo princípio do bom ordenamento de
, existe o menor tal . - Como
não é o menor possível (pois ), tem-se , então . - Pelo minimalidade de
, todos os números entre e estão em ; em especial . - Pela propriedade de fechamento, de
seguiria , contradizendo . - Logo não existe tal
, e portanto todos estão em . - Esta argumentação é equivalente à indução e ajuda a entender a lógica por trás dela.