Assumindo o Princípio da Boa Ordem, mostre que vale o Princípio de Indução.

Passo 1

Vou deixar claro o que o enunciado pede e o que está sendo assumido (não vou resolver nada ainda).
  • O que se assume: o Princípio da Boa Ordem — isto é, toda parte não vazia de \mathbb{N} tem um menor elemento.
  • O que queremos mostrar: o Princípio de Indução vale. Formalmente, queremos provar que para qualquer subconjunto S\subseteq\mathbb{N}, se
    1. 0\in S, e
    2. para todo n\in\mathbb{N}, n\in S \Rightarrow n+1\in S,
      então S=\mathbb{N}.
Observações importantes extraídas do enunciado (essas são as informações que vamos usar):
  • Está implícito que \mathbb{N} contém 0.
  • A hipótese de indução consiste em uma condição de base ( 0\in S) e uma condição de fechamento/sucessão ( n\in S \Rightarrow n+1\in S).
  • O objetivo é provar que não existe nenhum natural fora de S.

Passo 2

Estratégia geral (sem calcular nada ainda): usar prova por contradição combinada com o Princípio da Boa Ordem.
Explicando a ideia em palavras simples: supondo que as hipóteses da indução sejam verdadeiras, se existisse algum natural que não estivesse em S formaríamos o conjunto dos contraexemplos T=\mathbb{N}\setminus S, que por hipótese seria não vazio. Pelo Princípio da Boa Ordem, T teria um menor elemento m. Mostraríamos que isso leva a uma contradição, porque nem m=0 (pois 0\in S) nem m>0 pode ser um contraexemplo — o caso m>0 falha porque todos menores que m estariam em S (pela minimalidade) e, em particular, m-1\in S, então pela hipótese de fechamento obteríamos m\in S, contradizendo m\in T. Essa contradição força T a ser vazio, logo S=\mathbb{N}.
Antes de aplicar, vou explicar os instrumentos usados:
  • Prova por contradição: assume-se a negação do que se quer provar e mostra-se que isso leva a uma contradição lógica; então a afirmação original é verdadeira.
  • Técnica do menor contraexemplo: bastante usada com o Princípio da Boa Ordem; consiste em pegar o menor elemento que violaria a propriedade e usar sua minimalidade para obter uma contradição.

Passo 3

Começo a prova formal usando a ideia explicada.
Suponha, para contradizer o que queremos provar, que existe algum natural fora de S. Defina
T=\mathbb{N}\setminus S = \{n\in\mathbb{N} \mid n\notin S\}.
Pela suposição de contradição, T é não vazio. Pelo Princípio da Boa Ordem, T tem um menor elemento; chame-o de m. Ou seja,
m\in T \qquad\text{e}\qquad \text{para todo }k\in T,\\ k\ge m.

Passo 4

Analisar o caso m=0 e mostrar que não pode ocorrer.
Mas sabemos que 0\in S pela hipótese 1 da indução. Logo 0\notin T. Portanto m\neq 0. Concluímos que
m\ge 1.

Passo 5

Usar a minimalidade de m para obter que m-1\in S.
Como m\ge 1, m-1 é um natural. Se m é o menor elemento de T, então todo natural menor que m não pertence a T; em outras palavras, para todo k<m vale k\notin T, isto é, k\in S. Em particular, com k=m-1 obtemos
m-1\in S.
Aqui é crucial entender por que isso vale: se m-1 estivesse em T então seria um elemento de T menor que m, contradizendo que m é o menor elemento de T. Portanto m-1 deve estar em S.

Passo 6

Aplicar a hipótese de fechamento (passo de indução) para obter contradição.
Pela hipótese 2 da indução, sempre que um natural n pertence a S então seu sucessor n+1 também pertence a S. Aplicando isso ao caso n=m-1 (que acabamos de ver que está em S), obtemos
(m-1)+1 = m \in S.
Mas isso contradiz a definição de m como elemento de T=\mathbb{N}\setminus S. Portanto nossa suposição de que T é não vazio leva a uma contradição.

Passo 7

Concluir a prova e interpretar o resultado.
Como a suposição de que existe algum natural fora de S (isto é, T não vazio) levou a uma contradição, a única possibilidade é que T seja vazio. Logo
T=\varnothing \qquad\Rightarrow\qquad \mathbb{N}\setminus S=\varnothing \qquad\Rightarrow\qquad S=\mathbb{N}.
Isso mostra exatamente o Princípio de Indução: sob as hipóteses de base e de fechamento por sucessor, S contém todos os naturais.

Resposta

O Princípio de Indução vale: qualquer S\subseteq\mathbb{N} com 0\in S e tal que n\in S\Rightarrow n+1\in S satisfaz S=\mathbb{N}.

Exercícios relacionados