Prove o princípio de indução como uma conseqüência do princípio da boa ordenação.
Passo 1
Primeiro, vamos resumir o enunciado e o que queremos provar. Temos uma propriedade P(n) sobre os naturais. Sabemos que P(0) é verdadeira e que, para todo n em ℕ, se P(n) é verdadeira então P(n+1) também é. Queremos deduzir que P(n) vale para todo n em ℕ usando o Princípio da Boa Ordenação, que diz que todo subconjunto não vazio de ℕ tem um menor elemento.
Passo 2
Definimos o conjunto dos contra-exemplos de P como
Se conseguirmos mostrar que S não pode conter nenhum elemento, então S é vazio e logo para todo n em ℕ temos P(n).
Passo 3
Suponha, por absurdo, que S seja não vazio. Então, pelo Princípio da Boa Ordenação, existe m = min S. Como m ∈ S, temos ¬P(m).
Passo 4
Note que m não pode ser 0, pois P(0) é verdadeira. Logo m ≥ 1, e podemos escrever m = k+1 para algum k em ℕ. Como m é o menor elemento de S, para todo j < m temos P(j). Em particular, para j = k temos P(k).
Passo 5
Pela hipótese de indução, de P(k) segue P(k+1). Ou seja, P(m) é verdadeira. Mas isso contradiz m ∈ S, que exige ¬P(m). Portanto, nossa suposição de que S ≠ ∅ é impossível.
Passo 6
Concluímos que S deve ser vazio, ou seja, não existe n em ℕ com ¬P(n). Logo, para todo n em ℕ, P(n) é verdadeira. Isso demonstra o Princípio da Indução a partir do Princípio da Boa Ordenação.
Resposta
Como não existe n em ℕ tal que ¬P(n), concluímos que ∀n ∈ ℕ, P(n).