Demonstre o Princípio da Indução usando o Princípio da Boa Ordem.

Passo 1

Estamos em teoria dos números (ou lógica matemática) e queremos provar o Princípio da Indução em \mathbb{N}:
“Se \;P(1); é verdadeira e, para todo k\in\mathbb{N}, P(k)\Rightarrow P(k+1), então \forall n\in\mathbb{N}\colon P(n).”
Para isso, vamos usar o Princípio da Boa Ordem que diz:
“Qualquer subconjunto não vazio de \mathbb{N} possui um menor elemento.”

Passo 2

Suponha, por contradição, que a conclusão da indução falha. Defina o conjunto
S = \{\,n\in\mathbb{N}\mid P(n)\text{ é falsa}\}.é
Se a indução não valesse para algum natural, então S seria não vazio.

Passo 3

Pelo Princípio da Boa Ordem, S tem um menor elemento; seja m=\min S.
Como S\neq\varnothing, temos m\ge1.
Mas P(1) é verdadeira, logo m\neq1.
Então m>1, o que implica m-1\in\mathbb{N} e m-1<m.

Passo 4

Pelo minimalidade de m, para todo k<m vale P(k). Em particular, vale P(m-1).
Pela hipótese de indução “ P(k)\Rightarrow P(k+1) para todo k”, aplicando em k=m-1 obtemos P(m).
Isso contraria a definição de m\in S (onde P(m) seria falsa).
Logo, a hipótese de que S é não vazio é absurda. Portanto S é vazio e, consequentemente, \forall n\in\mathbb{N}\colon P(n).

Resposta

O Princípio da Indução decorre do Princípio da Boa Ordem, pois a suposição de existência de um contraexemplo leva a uma contradição pelo menor elemento de S.

Exercícios relacionados