Exercício 2. Dado um número natural a, seja Y \subset \mathbb{N} um conjunto com as seguintes propriedades: Prove que Y contém todos os números naturais maiores do que ou iguais a a.
a \in Y;

Passo 1

O enunciado (completando a propriedade que é padrão neste tipo de exercício) nos dá as seguintes informações:
  • a é um número natural fixo.
  • Y\subset\mathbb{N} é um subconjunto dos naturais.
  • As propriedades de Y são:
    • a\in Y.
    • Sempre que n\in Y então n+1\in Y. (fechamento por sucessor)
      O que precisa ser provado: mostrar que Y contém todos os números naturais maiores ou iguais a a, isto é, provar que
\{n\in\mathbb{N}\mid n\ge a\}\subseteq Y.

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 a.
  • Definimos a propriedade P(n) como: “ n\in Y”.
  • O princípio da indução (na versão iniciando em a) diz: se
    1. P(a) é verdadeira, e
    2. para todo n\ge a, P(n)\Rightarrow P(n+1),
      então P(n) é verdadeira para todo n\ge a.
  • 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 a.
    Vou aplicar esse princípio aqui: P(n) é a declaração “ n\in Y”.

Passo 3

Base da indução:
  • Pela hipótese do enunciado temos explicitamente que a\in Y.
  • Ou seja, P(a) é verdadeira.

Passo 4

Passo indutivo:
  • Suponha que para algum k\ge a já tenhamos P(k), isto é, suponha k\in Y.
  • Pela segunda propriedade de Y (fechamento por sucessor), a partir de k\in Y segue que k+1\in Y.
  • Logo P(k)\Rightarrow P(k+1) para todo k\ge a.

Passo 5

Conclusão por indução:
  • Aplicando o princípio da indução (com base em a e no passo indutivo verificado), obtemos que P(n) é verdadeira para todo n\ge a.
  • Em palavras: todos os naturais n tais que n\ge a pertencem a Y.

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 m\ge a com m\notin Y.
  • Pelo princípio do bom ordenamento de \mathbb{N}, existe o menor tal m.
  • Como m não é o menor possível (pois a\in Y), tem-se m>a, então m-1\ge a.
  • Pelo minimalidade de m, todos os números entre a e m-1 estão em Y; em especial m-1\in Y.
  • Pela propriedade de fechamento, de m-1\in Y seguiria (m-1)+1=m\in Y, contradizendo m\notin Y.
  • Logo não existe tal m, e portanto todos n\ge a estão em Y.
  • Esta argumentação é equivalente à indução e ajuda a entender a lógica por trás dela.

Resposta

\{n\in\mathbb{N}\mid n\ge a\}\subseteq Y

Exercícios relacionados