O Principio da Indução Forte é equivalente ao Principio da Indução Fraca

Real Analysis - Capítulo Zero

Fernando Francisco de Sousa Filho

14/11/2013

Prove que o principio da Indução Forte é equivalente ao principio da Indução Fraca.

Prova:(Indução Forte  ⇒  Indução Fraca) Em ambas, temos que P(1) = V. Então vamos considerar o segundo passo. Na indução forte temos que, dado r ∈ ℕ, com 1 ≤ r ≤ k, então, P(r) = V ⇒ P(k + 1) = V. Ora, se P(r) = V para todo 1 ≤ r ≤ k , então, tomando apenas o maior valor para r,  teremos P(k) = V. Por hipótese, P(k + 1) = V logo, o princípio da indução forte implica o principio da indução fraca.

(Indução Fraca  ⇒ Principio da Boa Ordenação) Consideremos que:

i) P(1) = V; e

ii) P(n) = V ⇒ P(n + 1) = V.

Seja A ⊂ ℕ um conjunto não vazio. Seja X ⊂ ℕ tal que X = ℕ\A. Consideremos a proposição P(x): = x ∈ X. Se aplicarmos a indução fraca a P(x) e ela se verificar, concluiremos que X = ℕ. Por contrapositiva, podemos abordar a questão assim: Se X ≠ ℕ então a indução fraca não se verifica para a proposição P(x). Mas, como A ≠ φ,  existe a ∈ A tal que a¬ ∈ X, logo X ≠ ℕ e, necessariamente, a indução fraca não se verifica para a proposição P(x). Temos então duas formas de a indução fraca não se confirmar:

i) P(1) = F ⇒ 1 ∈ A e A possui este menor elemento natural;

ii) P(1) = V, mas a implicação P(n) = V ⇒ P(n + 1) = V falha para algum n ∈ ℕ. Na primeira ocorrência desta falha, teremos P(n + 1) = F ⇒ (n + 1) ∈ A. Entretanto, teremos que 1 ≤ x ≤ n ⇒ x ∈ X, logo (n + 1) é o menor elemento do conjunto A.

(PBO ⇒  Indução Forte) Consideremos, pelo absurdo. A indução forte é a seguinte. Se:

i) P(1) = V; e

ii) Dado 1 ≤ r ≤ k , se P(r) = V ⇒ P(k + 1) = V; então, P(n) = V para todo n ∈ ℕ.

Suponhamos que a indução forte seja falsa, ou seja, suas hipóteses se verificam mas sua tese não. Assim, temos que P(1) = V e, dado 1 ≤ r ≤ k , se P(r) = V ⇒ P(k + 1) = V. Consideremos, então, o conjunto{n₁, ..., n_i, ...} formato por todos os valores para os quais tenhamos P(n) = F. Pelo PBO, este conjunto possui um menor elemento, digamosn_m. Mas se n_m é o menor natural deste conjunto, então P(n_m − 1) = V e, por hipótese, isto implica que P(n_m) = V, o que é uma contradição. logo confirma-se a indução forte.■

---

Document generated by eLyXer 1.2.3 (2011-08-31) on 2013-11-19T23:06:17.393477