A equivalência dos Princípios de Indução e da Boa Ordenação.
Prove que a primeira forma do PIM é equivalente ao PBO.
Prove que a primeira forma do PIM é equivalente ao PBO.
Passo 1
O enunciado pede para mostrar que a primeira forma do Princípio da Indução Matemática (PIM) é equivalente ao Princípio da Boa Ordenação (PBO). Vamos precisar das definições: PIM diz que se uma propriedade
vale para
e sempre que vale para
vale para
, então
vale para todo
. PBO diz que todo subconjunto não vazio de
tem elemento mínimo. Vamos provar duas implicações: PIM
PBO e PBO
PIM.
Passo 2
Prova de PIM
PBO: suponha PIM. Seja
não vazio. Queremos mostrar que
tem menor elemento. Se não,
não tem mínimo. Defina a propriedade
: “todo
não pertence a
”.
Checamos a base: como não tem mínimo,
, logo
é verdadeira. Agora, passo indutivo: suponha
verdadeira, ou seja,
para todo
. Se
, então
seria o menor elemento (pois nenhum
está em
), contradizendo a hipótese de que
não tem mínimo. Logo
e
vale.
Checamos a base: como
Passo 3
Pela PIM,
vale para todo
, isto é, nenhum
pertence a
. Assim
é vazio, contradizendo que
era não vazio. Portanto
sempre tem mínimo: PBO vale.
Passo 4
Prova de PBO
PIM: suponha PBO. Seja
tal que
vale e
para todo
. Queremos
para todo
. Considere
. Se
é vazio, pronto. Se
é não vazio, então por PBO existe mínimo
. Mas
(pois
é verdadeira), então
e
implica
. Pela hipótese indutiva
valeria, contradizendo
. Logo
não pode ser não vazio.
Passo 5
Como mostramos ambas as implicações, concluímos que PIM e PBO são equivalentes.
Resposta
O Princípio da Indução Matemática na sua forma usual é logicamente equivalente ao Princípio da Boa Ordenação de
.