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:
  1. Mostrar que é verdadeira (base da indução).
  2. 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
Construa uma função sobrejetiva tal que para cada a pre-imagem seja um conjunto enumerável.
Identifique a curva definida pela função vetorial
;
Seja onde e tem e elementos respectivamente, mostre que tem elementos. Deduza daqui que .