Em
, prove o princípio de indução (A3) é uma consequência do princípio da boa ordenação.
Passo 1
Beleza, a gente vai provar que o princípio da indução matemática (A3) pode ser obtido a partir do princípio da boa ordenação, tudo isso dentro dos números naturais
. Vamos precisar entender o que cada um desses princípios diz e como eles estão relacionados para fazer a prova.
Passo 2
Primeiro, vamos relembrar o que é o princípio da boa ordenação. Esse princípio afirma que todo conjunto não vazio de números naturais tem um menor elemento. Em outras palavras, se você pegar qualquer grupo de números naturais que não esteja vazio, vai sempre ter um número que é o menor entre eles.
Passo 3
Agora, vamos recordar o que é o princípio da indução matemática. Ele diz que, para provar que uma propriedade
é verdadeira para todo número natural
, precisamos:
- Mostrar que
é verdadeira (base da indução). - Mostrar que, se
é verdadeira, então também é verdadeira (passo indutivo).
Se conseguirmos essas duas coisas, então
é verdadeira para todo
.
Passo 4
Vamos supor que o princípio da indução não seja uma consequência do princípio da boa ordenaç��o. Ou seja, existe alguma propriedade
que satisfaz a base da indução (
é verdadeira) e o passo indutivo (se
é verdadeira, então
é verdadeira), mas
não é verdadeira para todo
.
Passo 5
Se essa hipótese for verdadeira, então o conjunto dos números naturais para os quais
é falsa não é vazio (já que existe pelo menos um número onde
não vale). Pelo princípio da boa ordenação, esse conjunto tem um menor elemento. Vamos chamar esse menor elemento de
.
Passo 6
Como
é o menor número onde
é falsa, todo número menor que
deve satisfazer
, ou seja,
é verdadeira para todo
.
Passo 7
Agora, considerando o passo indutivo, se
é verdadeira para todo
, então em particular,
é verdadeira. De acordo com o passo indutivo, isso implica que
também deve ser verdadeira.
Passo 8
Mas isso é uma contradição, porque assumimos que
é o menor número onde
é falsa. Portanto, nossa hipótese inicial está errada.
Passo 9
Assim, não pode existir nenhum número natural para o qual
seja falsa, ou seja,
deve ser verdadeira para todo
. Portanto, o princípio da indução matemática é uma consequência do princípio da boa ordenação.
Resposta
Com isso, provamos que o princípio da indução matemática pode ser derivado a partir do princípio da boa ordenação nos números naturais.
Exercícios relacionados
Sejam
fixados em
e
números não negativos tais que
. Considere os números
definidos por
Mostre que
Identifique a curva definida pela função vetorial
;
Seja
onde
e
tem
e
elementos respectivamente, mostre que
tem
elementos. Deduza daqui que
.