Pular para o conteúdo principal

Indução

Real Analysis - Capítulo Zero

Real Analysis - Capítulo Zero

Fernando Francisco de Sousa Filho

19/11/2013

Exercicio: Prove que n < 2n por indução.
Prova:
(I) Para n = 1 temos 1 < 2.
(II) Consideremos P(n): = n < 2n como verdadeira. Mas se n < 2n então n + 1 < 2n + 1 e 2n + 1 < 2n + 2n, logo, n + 1 < 2n + 2n, ou seja, n + 1 < 2n + 1.
■
Exercicio: Prove que para um conjunto finito A de cardinalidade n, a cardinalidade de P(A) é igual a 2n.
Prova: (Indução)
(I) P(φ) = {φ} e se A é um conjunto unitário, P(A) = {φ, A};
(II) Suponhamos verdadeira a proposição P(n): = |P(A)| = 2n. Vamos considerar o conjunto An de n elementos e o acréscimo de mais um elemento, digamos, o elemento an + 1, formando o conjunto An + 1. Todos os subconjuntos do conjunto An também são subconjuntos de An + 1. Além disto, todos os subconjuntos do conjunto An não possuem o elemento an + 1. Então, ao associarmos o elemento an + 1 a cada subconjunto de An com a operação união, teremos todos os subconjuntos de An + 1que contém an + 1, pois são todos os possiveis subconjuntos de An com o acréscimo do elemento an + 1. Para reforçar este argumento, suponhamos que houvesse um subconjunto de An + 1 ao qual o elemento an + 1 pertencesse e que não tivesse sido considerado no raciocício anterior. Ora, mas ao retirarmos deste conjunto o elemento an + 1 teriamos obrigatoriamente um subconjunto de An, logo, todos os subconjuntos com o elemento an + 1 são obtidos ao acrescentarmos este elemento a todos os subconjuntos de An. Ao fazermos isto, obtemos para cada subconjunto de An um subconjunto de An + 1 que contém o elemento an + 1. Como os subconjuntos de An + 1 podem ser divididos entre aqueles em que an + 1 não está, que por hipótese de indução são em número de 2n, e aqueles em que o elemento an + 1 está, que correspondem ao mesmo número de subconjuntos de An, portanto, 2n, concluímos que o número de subconjuntos de An + 1 é 2n + 2n = 2n + 1.
■

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