A equivalência dos Princípios de Indução e da Boa Ordenação.
Prove que a primeira forma do PIM é equivalente ao PBO.

Passo 1

O enunciado pede para mostrar que a primeira forma do Princípio da Indução Matemática (PIM) é equivalente ao Princípio da Boa Ordenação (PBO). Vamos precisar das definições: PIM diz que se uma propriedade P(n) vale para 0 e sempre que vale para n vale para n+1, então P(n) vale para todo ninN. PBO diz que todo subconjunto não vazio de N tem elemento mínimo. Vamos provar duas implicações: PIM RightarrowPBO e PBO RightarrowPIM.

Passo 2

Prova de PIM RightarrowPBO: suponha PIM. Seja SsubseteqN não vazio. Queremos mostrar que S tem menor elemento. Se não, S não tem mínimo. Defina a propriedade P(n): “todo k<= n não pertence a S”.
Checamos a base: como S não tem mínimo, 0notin S, logo P(0) é verdadeira. Agora, passo indutivo: suponha P(n) verdadeira, ou seja, knotin S para todo k<= n. Se n+1in S, então n+1 seria o menor elemento (pois nenhum S está em S), contradizendo a hipótese de que n+1notin S não tem mínimo. Logo P(n+1) e vale.

Passo 3

Pela PIM, P(n) vale para todo n, isto é, nenhum n pertence a S. Assim S é vazio, contradizendo que S era não vazio. Portanto S sempre tem mínimo: PBO vale.

Passo 4

Prova de PBO RightarrowPIM: suponha PBO. Seja P(n) tal que P(0) vale e P(n)Rightarrow P(n+1) para todo n. Queremos P(n) para todo n. Considere T=ninNmid neg P(n). Se T é vazio, pronto. Se T é não vazio, então por PBO existe mínimo min T. Mas mne0 (pois P(0) é verdadeira), então m-1>=0 e m-1notin T implica P(m-1). Pela hipótese indutiva P(m) valeria, contradizendo min T. Logo T não pode ser não vazio.

Passo 5

Como mostramos ambas as implicações, concluímos que PIM e PBO são equivalentes.

Resposta

O Princípio da Indução Matemática na sua forma usual é logicamente equivalente ao Princípio da Boa Ordenação de N.

Exercícios relacionados