Lista de Exercícios Resolvidos - Conjuntos e Indução Matemática

1 Considere X e Y conjuntos finitos Prove que a Se Y X então Y X Dica Se X n significa que X In Se for provado para X In o resultado é generalizado pela equivalência Então basta provar para X In b Se X e Y são disjuntos então X Y X Y c X Y X Y X Y Dica Perceba que X pode ser escrito como a união disjunta X X Y X Y e que X Y pode ser escrito como a união disjunta X Y X Y Y d X x Y X Y Prova de Análise 1 Prove por indução a 1 3 5 2n 1 n² n ℕ b 2n n n ℕ c 2n n n ℕ e n 4 d De Moivre cosθ isenθn cosnθ isennθ n ℕ e θ ℝ fixado 3 Exprima ℕ ℕ1 ℕ2 ℕn como a união infinita de subconjuntos infinitos dois a dois disjuntos 4 Seja A o conjunto de todas as sequências infinitas formadas apenas pelos algarismos 0 e 1 Um exemplo de um elemento de A seria a 10111001 Mostre que o conjunto A é não enumerável Dica Suponha que A seja enumerável e faça uma listagem L de todos os seus elementos em uma sequência Depois pense em uma construção de um elemento a que não pertença a L contrariando a afirmação de que todos estavam listados Conclua que A é não enumerável 5 Sejam abcd ℝ Prove que a Se a b e c d então a c b d b Se 0 a b e 0 c d então ac bd c Se 0 a b então b¹ a¹ 6 Sejam ab ℝ Prove a Desigualdade Simplificada de Young ab a²2 b²2 Parte 1 da prova 1 Prove por indução c 2n n n N e n 4 d De Moivre cosθ i sinθn cosnθ i sinnθ n N e θ R fixado Solução item c Com efeito vamos verificar o caso n 4 Em particular para n 4 temos que 24 16 e que 4 24 logo segue que 2n n para n 4 Agora vamos assumir a hipótese de indução para n R Com efeito então teremos que 2R R para R 4 Agora vamos verificar o caso n R 1 Com efeito veja que temos que R 1 R 1R R 12R R2R 2R 2R 2R 2 2R 2R1 onde usamos o fato de que R 4 na quarta linha Logo obtemos que R 1 2R1 que verifica o caso de indução para n R 1 Com isso segue que por indução em n temos que 2n n para todo n 4 com n N Solução do item d Provaremos a relação de De Moivre Com efeito para o caso inicial isto é n 1 é evidente que a relação vale De fato veja que temos que cosθ i sinθn cosθ i sinθ1 cos1 θ i sin1 θ Então assumamos a validade da hipótese de indução para n R Com efeito então temos que cosθ i sinθR cosRθ i sinRθ De posse disso vamos verificar a validade da relação para o caso n R 1 Com efeito por meio da hipótese de indução temos o seguinte desenvolvimento cosθ i sinθR1 cosθ i sinθRcosθ i sinθ cosRθ i sinRθcosθ i sinθ cosRθ cosθ sinRθ sinθ i sinRθ cosθ sinθ cosRθ cosRθ θ i sinθ Rθ cosR 1θ i sinR 1θ e portanto a relação fica provada para o caso n R 1 Com efeito segue que por indução em n temos que a Lei de De Moivre fica provada para todo n natural 1 Parte 2 da prova Questão 1 1 Considere X e Y conjuntos finitos Prove que b Se X e Y são disjuntos então X Y X Y Solução da questão 1 da parte 2 item b Com efeito consideremos que X e Y sejam conjuntos finitos com cardinalidades digamos m e n respectivamente Em particular isso nos permite ainda rotular os elementos dos conjuntos dada sua finitude Desse modo podemos escrever sem perda de generalidade que X x1 x2 xm Y y1 y2 yn Ademais pela definição de conjunto finito segue que existem as seguintes funções f Im X e g In y que são bijeções Em particular podemos explicitálas da seguinte forma f Im X p Im fp xp e g In Y p Im gp yp Agora note que a partir disso podemos definir uma função ψ do seguinte modo ψ Imn X Y p Imn ψp fp se 1 p m gp m se m 1 p n Note que a função ψp é em suma uma função bem definida tendo em vista que as funções f e g estão bem postas dado a definição dos conjuntos finitos Ademais perceba que ψp é uma função que varre todos os elementos xp X e todos os elementos yp Y Em particular dado ao fato de que X e Y são disjuntos essa construção não permite que haja algum p tal que fp gp m Nesse sentido segue que por construção a função ψ é uma bijeção e logo o conjunto X Y tem cardinalidade do conjunto Imn isto é m n Ou seja veja que temos então que X Y Imn m n X Y e logo o resultado fica demonstrado Questão 4 4 Seja A o conjunto de todas as sequências infinitas formadas apenas pelos algarismos 0 e 1 Um exemplo de um elemento de A seria a 1 0 1 1 1 0 0 1 Mostre que o conjunto A é não enumerável Dica Suponha que A seja enumerável e faga uma listagem L de todos os seus elementos em uma sequência Depois pense em uma construção de um elemento a que não pertença a L contrariando a afirmação de que todos estavam listados Conclua que A é não enumerável Solução da questão 4 Note que as sequências de números 0 e 1 devem ter a forma geral a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14a15 a16 a17 a18 a19 onde cada ai pode ser 0 ou 1 Note ainda que a quantidade de algarismos possíveis é exata mente dada pela quantidade de elementos do conjunto dos naturais N e de posse do princípio da contagem como cada a pode assumir dois valores temos que o conjunto de todas as sequências formadas por 0 e 1 devem ter 2N elementos Todavia 2N cardPN onde P denota o conjunto das partes ou seja o problema tornase equivalente e provar que o conjunto das partes é não enumerável nesse sentindo enunciamos o seguinte Teorema Teorema 1 Teorema de Cantor Não existe função sobrejetiva f A PA Portanto não existe bijeção f N PN e logo o conjunto das partes de N é não enumerável e por conseguinte o conjunto das sequências formadas pelos algarismos 0 e 1 é não enumerável Demonstração alternativa Façamos uma demonstração de posse do argumento da diago nal de Cantor Com efeito definamos o conjunto X de todos as sequências de números formados pelos algarismos 0 e 1 Assumamos que f N X é uma bijeção que definiremos por f1 a11 a12 a13 a1n f2 a21 a22 a23 a2n fn an1 an2 an3 ann Agora note que a sequência d d1 d2 d3 dn onde di aii para todo i N Por construção d difere de qualquer fi com i natural Daí segue que f não é bijetiva e logo o conjunto X é não enumerável Questão 5 5 Sejam a b c d R Prove que a Se a b e c d então a c b d b Se 0 a b e 0 c d então ac bd c Se 0 a b então b1 a1 3 Solução da questão 5 Solução da questão 5 item a a Como a b e c d temos que pela monotonicidade adição que a c b c adicionando c em ambos os lados da primeira desigualdade e analogamente podemos ter que bc dc adicionando b em ambos os lados da segunda desigualdade Agora note que com isso temos que a c b c d c portanto daí segue por transitividade que implica em a c b d e o resultado fica demonstrado Solução da questão 5 item b b Primeiro veja que temos que 0 a b b a 0 e que 0 c d d c 0 Com isso em mãos podemos mostrar o desejado Com efeito basta seguirmos o desenvolvimento de bd ac que é o seguinte bd ac bd bc bc ac bd c cb a 0 uma vez que b 0 d c 0 c 0 e b a 0 Portanto temos que bd ac 0 bd ac ou seja ac bd conforme desejado Solução da questão 5 item c c Como 0 a b temos que b a 0 Dividindo ambos os lados por ab obtemos b a 0 b a ab 0 1 a 1 b b a ab 0 1 a 1 b 0 1 a 1 b 1 b 1 b 1 a 1 b a1 b1 e logo temos que se a b b1 a1 e o resultado fica demonstrado Questão 6 6 Sejam a b R Prove a Desigualdade Simplificada de Young ab a2 2 b2 2 4 Solução da questão 6 Com efeito consideremos dois números reais a b Em particular como esses números pertencem ao corpo ordenado dos reais vale que a b2 0 Então veja que 0 a b2 a2 b2 2ab 2ab a2 b2 ab a2 2 b2 2 que prova a desigualdade para quaisquer a e b reais 5