Pular para o conteúdo principal

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

Real Analysis - Capítulo Zero

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{n1, ..., ni, ...} formato por todos os valores para os quais tenhamos P(n) = F. Pelo PBO, este conjunto possui um menor elemento, digamosnm. Mas se nm é o menor natural deste conjunto, então P(nm − 1) = V e, por hipótese, isto implica que P(nm) = V, o que é uma contradição. logo confirma-se a indução forte.■

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Curso de Análise (Elon) - Cap. 3 Questão 4

Capítulo 3 - Questão 4 Livro Curso de Análise - Vol.1 - Elon Capítulo 3 - Questão 4 Fernando Francisco de Sousa Filho 12 de novembro de 2013 Sejam K ,  L corpos. Uma função f : K  →  L chama-se um homomorfismo quando se tem f ( x  +  y ) =  f ( x ) +  f ( y ) e f ( x ⋅ y ) =  f ( x )⋅ f ( y ) , quaisquer que sejam x ,  y  ∈  K . i) Dado um homomorfismo f : K  →  L , prove que f (0) = 0 . Prova : f (0) =  f (0 + 0) =  f (0) +  f (0) ⇒  f (0) = 2 f (0) . Se f (0) ≠ 0,  pela lei do corte, chegamos a 1 = 2 (Absurdo!). Logo, f (0) = 0 . ■ ii) Prove também que ou f ( x ) = 0 para todo x  ∈  K ou então f (1) = 1 e f é injetiva. Prova : Suponhamos f ( x ) = 0 para todo x  ∈  K , então teremos a) f ( x  +  y ) = 0 , mas f ( x  +  y ) =  f ( x ) +  f ( y ) = 0 + 0 = 0. b) f ( xy ) = 0 , mas f ( xy ) =  f ( x )⋅ f ( y ) = 0⋅0 = 0 . Logo, confirma-se a primeira possibilidade. Vamos mostrar, então, que, se f (1) ≠ 0 então f (1) = 1 .Suponhamos f (1...
Postar um comentário
Leia mais

Explicando a tabela lógica do Se... então

 Eu sempre me incomodei bastante com a tabela do Se... então (implicação). Afinal, a tabela do "e" e a tabela do "ou" são bastante lógicas, se é que eu posso usar este termo numa disciplina que se chama lógica! Poderia dizer também que são tabelas que fazem sentido, afinal, o "e" só resulta "V" se ambos forem "V"; e o "ou" só resulta "F" se ambos forem "F". Mas, e quanto à implicação? Tive minha curiosidade atendida no livro de DAVID J. HUNTER, Fundamentos da Matemática Discreta, em um breve trecho. Esta postagem é uma adaptação minha do que consta lá! Então, podemos usar diversos exemplos! Eu vou usar dois que eu inventei ao escrever esta postagem, e, depois, vou repetir o exemplo do livro citado. Suponha que uma mãe diga o seguinte a seu filho Mateus: Filho, se você fizer todos os exercícios de Matemática, vai tirar nota boa na prova. Suponha então que Mateus quisesse negar este conselho de sua mãe, prova...
Postar um comentário
Leia mais