Seja
uma sentença aberta sobre
, e seja
. Suponha que:
i.
é verdadeira, e
ii. qualquer que seja
, com
, sempre que
for verdadeira, segue-se que
é verdadeira.
Então,
é verdadeira para todo número natural
.
i.
ii. qualquer que seja
Então,
Passo 1
Beleza, o enunciado diz o seguinte: temos uma propriedade aberta
para
e um número fixo
. Sabemos duas coisas:
-
é verdadeira (caso base). - Para todo
, se é verdadeira então também é (passo indutivo).
Conteúdo: estamos mostrando o Princípio da Indução Matemática usando o Princípio da Boa Ordem de
. Vamos precisar entender bem a ideia de “menor elemento” em um conjunto não-vazio de naturais e usar isso pra montar uma contradição.
Passo 2
A ideia é provar por contradição. Suponha que não seja verdade que
valha para todo
. Então existe pelo menos um natural
tal que
é falsa. Definimos o conjunto dos “contraexemplos” assim:
Pelo Princípio da Boa Ordem, se
não é vazio, então ele tem um menor elemento; seja
. Agora olhe esses dois casos:
- Se
, aí já bate de frente com a hipótese do caso base, porque sabíamos que era verdadeira. Contradição. - Se
, então e, como é o menor contraexemplo, é verdadeira. Mas aí, pelo passo indutivo, . Logo teria de ser verdadeira. Contradição de novo.
Passo 3
Como em ambos os cenários chegamos a contradição, nossa hipótese de que
não é vazio cai por terra. Logo
é vazio, ou seja, não existe nenhum
que seja contraexemplo.