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.
n \in Y \Rightarrow n+1 \in Y.

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 a.
  • Há um subconjunto Y\subset\mathbb{N} tais que vale a condição n\in Y \Rightarrow n+1\in Y.
  • O objetivo é provar que Y contém todos os números naturais maiores ou iguais a a; isto é, mostrar que todo n\in\mathbb{N} com n\ge a pertence a Y.
(Observação: para que a conclusão faça sentido é preciso que o enunciado também forneça que a\in Y. Vou assumir que esse fato está presente no enunciado, pois sem um ponto inicial a\in Y a propriedade de sucessor sozinha não garante nenhum elemento em Y.)

Passo 2

Vamos organizar a prova de forma clara. Defino, para cada k\in\mathbb{N}, a proposição
P(k):\quad a+k\in Y.
A ideia é mostrar que P(k) é verdadeira para todo k\in\mathbb{N}. Como a+k ao variar k por todos os naturais produz exatamente todos os naturais \ge a, isso dará o resultado desejado. A técnica natural aqui é o princípio da indução matemática (prova por indução em k).

Passo 3

Base da indução (caso k=0). Precisamos provar P(0), isto é, provar que a+0\in Y. Como a+0=a e estamos assumindo que a\in Y, concluímos imediatamente que
P(0)\text{ é verdadeira, pois }a\in Y.é
Explicação didática: a base da indução garante o ponto de partida — mostramos que o primeiro elemento da sequência a,a+1,a+2,\dots está em Y.

Passo 4

Passo indutivo. Suponha que para algum k\ge 0 valha P(k), isto é, suponha como hipótese indutiva que
a+k\in Y.
Usando a propriedade dada do conjunto Y (se um número está em Y, então seu sucessor também está), aplicamos essa propriedade ao número n=a+k. Assim obtemos
(a+k)\in Y \Rightarrow (a+k)+1\in Y.
Como (a+k)+1 = a+(k+1), concluímos que
a+(k+1)\in Y,
ou seja, P(k+1) é verdadeira. Explicação passo a passo: a hipótese indutiva dá que um certo elemento da sequência está em Y; a regra de sucessor do enunciado nos permite então colocar o próximo elemento da sequência em Y.

Passo 5

Conclusão da indução. Pela base P(0) verdadeira e pelo passo indutivo que mostra P(k)\Rightarrow P(k+1), o princípio da indução matemática afirma que P(k) é verdadeira para todo k\in\mathbb{N}. Em outras palavras,
\text{para todo }k\in\mathbb{N}\text{ vale }a+k\in Y.

Passo 6

Tradução para a conclusão pedida. O conjunto \{a+k: k\in\mathbb{N}\} é precisamente o conjunto de todos os naturais maiores ou iguais a a, isto é,
\{a+k: k\in\mathbb{N}\}=\{n\in\mathbb{N}\mid n\ge a\}.
Como mostramos que todo a+k pertence a Y, segue imediatamente que
\{n\in\mathbb{N}\mid n\ge a\}\subset Y,
ou seja, Y contém todos os números naturais maiores ou iguais a 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 m\ge a com m\notin Y. Pelo bom ordenamento de \mathbb{N} existe então o menor tal m. Esse m não pode ser igual a a porque assumimos a\in Y; logo m>a e portanto m-1\ge a. Pela minimalidade de m segue m-1\in Y, e aplicando a propriedade de sucessor obtemos (m-1)+1=m\in Y, contradição. Assim não existe tal m e a conclusão segue. Esse argumento é equivalente à indução, só muda a abordagem mental.

Resposta

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

Exercícios relacionados