Indução e boa-ordenação:
(a) Demonstre o princípio de indução usando o princípio de indução forte.
(b) Demonstre o princípio de indução forte usando o princípio de boa-ordenação.
© Demonstre o princípio de boa-ordenação usando o princípio de indução.
Conclua que os os princípios de indução, indução forte e boa-ordenação são equivalentes.
(a) Demonstre o princípio de indução usando o princípio de indução forte.
(b) Demonstre o princípio de indução forte usando o princípio de boa-ordenação.
© Demonstre o princípio de boa-ordenação usando o princípio de indução.
Conclua que os os princípios de indução, indução forte e boa-ordenação são equivalentes.
Passo 1
Esta questão pede para mostrarmos as equivalências entre três princípios sobre números naturais: o princípio de indução tradicional, o princípio de indução forte e o princípio de boa ordenação. Vamos precisar das definições de cada um: indução tradicional (base em 0 e passo de n para n+1), indução forte (para provar P(n+1) podemos assumir P(0),…,P(n)) e boa ordenação (todo subconjunto não vazio de ℕ tem menor elemento).
Passo 2
Queremos provar o princípio de indução tradicional a partir do princípio de indução forte. Suponha que P(0) vale e que para todo n temos P(n)⇒P(n+1). Para aplicar indução forte, note que, se P(k) vale para todo k≤n, então em particular P(n) vale e, pelo passo usual, P(n+1) também vale. Logo satisfazemos a hipótese da indução forte: ∀nigl[(∀k≤n o P(k))⇒P(n+1)igr]. Portanto, por indução forte, ∀n P(n), ou seja, o princípio de indução tradicional.
Passo 3
Agora vamos mostrar o princípio de indução forte usando o princípio de boa ordenação. Seja P(n) uma propriedade com P(0) verdadeira e tal que, para todo n, se P(k) vale para todo k<n então P(n) vale. Suponha, por contradição, que existe algum n com ¬P(n). Então o conjunto A={n∈ℕ:¬P(n)} é não vazio; pela boa ordenação, m=min A existe. Como m∈A temos ¬P(m). Mas por minimalidade, todo k<m satisfaz P(k), e portanto pelo passo da indução forte teria P(m), contradição. Logo não existe tal m e vale ∀n P(n).
Passo 4
Por fim, demonstremos a boa ordenação usando indução tradicional. Dado A⊆ℕ não vazio, queremos mostrar que A tem mínimo. Definimos a propriedade Q(n): “todo subconjunto não vazio de {0,1,…,n} tem menor elemento”. Base n=0: qualquer A⊆{0} não vazio só pode ser {0}, cujo mínimo é 0. Suponha Q(n) e considere A⊆{0,1,…,n+1}, A≠∅. Se n+1∉A, então A⊆{0,…,n} e por Q(n) tem mínimo. Se n+1∈A, então ou A={n+1} e seu mínimo é n+1, ou existe algum k<n+1 em A; nesse caso A∩{0,…,n} é não vazio e, por Q(n), tem mínimo, que é também mínimo de A. Assim Q(n+1) vale. Por indução, Q(n) vale para todo n, ou seja, todo subconjunto finito inicial de ℕ tem mínimo, e portanto qualquer subconjunto não vazio de ℕ também (basta notar que todo conjunto não vazio tem algum elemento em {0,…,m} para m grande o suficiente).
Resposta
Portanto, mostramos que cada princípio implica o outro, concluindo que indução tradicional, indução forte e boa ordenação são equivalentes.