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 nos dá as seguintes informações (estas são todas as informações relevantes que usaremos):
- Foi fixado um número natural
. - Há um subconjunto
tais que vale a condição - O objetivo é provar que
contém todos os números naturais maiores ou iguais a ; isto é, mostrar que todo com pertence a .
(Observação: para que a conclusão faça sentido é preciso que o enunciado também forneça que
. Vou assumir que esse fato está presente no enunciado, pois sem um ponto inicial
a propriedade de sucessor sozinha não garante nenhum elemento em
.)
Passo 2
Vamos organizar a prova de forma clara. Defino, para cada
, a proposição
A ideia é mostrar que
é verdadeira para todo
. Como
ao variar
por todos os naturais produz exatamente todos os naturais
, isso dará o resultado desejado. A técnica natural aqui é o princípio da indução matemática (prova por indução em
).
Passo 3
Base da indução (caso
). Precisamos provar
, isto é, provar que
. Como
e estamos assumindo que
, concluímos imediatamente que
Explicação didática: a base da indução garante o ponto de partida — mostramos que o primeiro elemento da sequência
está em
.
Passo 4
Passo indutivo. Suponha que para algum
valha
, isto é, suponha como hipótese indutiva que
Usando a propriedade dada do conjunto
(se um número está em
, então seu sucessor também está), aplicamos essa propriedade ao número
. Assim obtemos
Como
, concluímos que
ou seja,
é verdadeira. Explicação passo a passo: a hipótese indutiva dá que um certo elemento da sequência está em
; a regra de sucessor do enunciado nos permite então colocar o próximo elemento da sequência em
.
Passo 5
Conclusão da indução. Pela base
verdadeira e pelo passo indutivo que mostra
, o princípio da indução matemática afirma que
é verdadeira para todo
. Em outras palavras,
Passo 6
Tradução para a conclusão pedida. O conjunto
é precisamente o conjunto de todos os naturais maiores ou iguais a
, isto é,
Como mostramos que todo
pertence a
, segue imediatamente que
ou seja,
contém todos os números naturais maiores ou iguais a
.
Passo 7
Uma prova alternativa (curta) — princípio do mínimo contramodelo (opcional para reforçar a intuição): suponha, por contradição, que exista algum
com
. Pelo bom ordenamento de
existe então o menor tal
. Esse
não pode ser igual a
porque assumimos
; logo
e portanto
. Pela minimalidade de
segue
, e aplicando a propriedade de sucessor obtemos
, contradição. Assim não existe tal
e a conclusão segue. Esse argumento é equivalente à indução, só muda a abordagem mental.