Demonstre o Princípio da Indução usando o Princípio da Boa Ordem.
Passo 1
Estamos em teoria dos números (ou lógica matemática) e queremos provar o Princípio da Indução em
:
“Se
; é verdadeira e, para todo
,
, então
.”
Para isso, vamos usar o Princípio da Boa Ordem que diz:
“Qualquer subconjunto não vazio de
possui um menor elemento.”
Passo 2
Suponha, por contradição, que a conclusão da indução falha. Defina o conjunto
Se a indução não valesse para algum natural, então
seria não vazio.
Passo 3
Pelo Princípio da Boa Ordem,
tem um menor elemento; seja
.
Como , temos
.
Mas é verdadeira, logo
.
Então , o que implica
e
.
Como
Mas
Então
Passo 4
Pelo minimalidade de
, para todo
vale
. Em particular, vale
.
Pela hipótese de indução “ para todo
”, aplicando em
obtemos
.
Isso contraria a definição de (onde
seria falsa).
Pela hipótese de indução “
Isso contraria a definição de
Logo, a hipótese de que
é não vazio é absurda. Portanto
é vazio e, consequentemente,
.
Resposta
O Princípio da Indução decorre do Princípio da Boa Ordem, pois a suposição de existência de um contraexemplo leva a uma contradição pelo menor elemento de
.