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
tem um menor elemento. - O que queremos mostrar: o Princípio de Indução vale. Formalmente, queremos provar que para qualquer subconjunto
, se -
, e - para todo
, ,
então.
-
Observações importantes extraídas do enunciado (essas são as informações que vamos usar):
- Está implícito que
contém . - A hipótese de indução consiste em uma condição de base (
) e uma condição de fechamento/sucessão ( ). - O objetivo é provar que não existe nenhum natural fora de
.
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
formaríamos o conjunto dos contraexemplos
, que por hipótese seria não vazio. Pelo Princípio da Boa Ordem,
teria um menor elemento
. Mostraríamos que isso leva a uma contradição, porque nem
(pois
) nem
pode ser um contraexemplo — o caso
falha porque todos menores que
estariam em
(pela minimalidade) e, em particular,
, então pela hipótese de fechamento obteríamos
, contradizendo
. Essa contradição força
a ser vazio, logo
.
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
. Defina
Pela suposição de contradição,
é não vazio. Pelo Princípio da Boa Ordem,
tem um menor elemento; chame-o de
. Ou seja,
Passo 4
Analisar o caso
e mostrar que não pode ocorrer.
Mas sabemos que
pela hipótese 1 da indução. Logo
. Portanto
. Concluímos que
Passo 5
Usar a minimalidade de
para obter que
.
Como
,
é um natural. Se
é o menor elemento de
, então todo natural menor que
não pertence a
; em outras palavras, para todo
vale
, isto é,
. Em particular, com
obtemos
Aqui é crucial entender por que isso vale: se
estivesse em
então seria um elemento de
menor que
, contradizendo que
é o menor elemento de
. Portanto
deve estar em
.
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
pertence a
então seu sucessor
também pertence a
. Aplicando isso ao caso
(que acabamos de ver que está em
), obtemos
Mas isso contradiz a definição de
como elemento de
. Portanto nossa suposição de que
é 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
(isto é,
não vazio) levou a uma contradição, a única possibilidade é que
seja vazio. Logo
Isso mostra exatamente o Princípio de Indução: sob as hipóteses de base e de fechamento por sucessor,
contém todos os naturais.
Resposta
O Princípio de Indução vale: qualquer
com
e tal que
satisfaz
.