Exercicios Resolvidos sobre Conjuntos Enumeraveis - Demonstracoes e Solucoes

1 Prove que o produto cartesiano de dois conjuntos enumeráveis é um conjunto enumerável 2 Seja f X Y uma função injetiva Prove que se X é infinito então Y é infinito 3 Seja f X Y uma função sobrejetiva Prove que se Y é infinito então X é infinito 4 Sejam X um conjunto finito e Y um conjunto infinito Prove que existe uma função injetiva f X Y e uma função sobrejetiva g Y X 5 Defina f ℕ ℕ ℕ pondo f1n 2n 1 e fm 1n 2m2n 1 Prove que f é uma bijeção 6 Sejam Y enumerável e f X Y tal que para cada y Y f1y é enumerável Prove que X é enumerável 7 Prove que o conjunto X x ℝ sinx 1 é enumerável 1 Prova Sejam X e Y conjuntos enumeráveis Então existem sobrejeções f ℕ X e g ℕ Y Logo podemos definir a função ℓ ℕ ℕ X Y dada por ℓmn fm gn é sobrejetiva Logo basta provar que ℕ ℕ é enumerável Considere a função h ℕ ℕ ℕ dada por hmn 2m3n Pela unicidade da decomposição de um número em primos segue que h é injetiva Logo ℕ ℕ é enumerável e portanto X Y é enumerável Obs Na demonstração usamos o seguinte resultado se f X Y sobrejetiva e X enumerável então Y também é 2 Prova Sejam X infinito e f X Y injetiva Como X é infinito existe uma aplicação injetiva g ℕ X Logo podemos definir a composição fog ℕ Y como f e g são injetivas então fog ℕ Y é injetiva pois composição de injetivas também é Portanto Y é infinito 3 Sejam Y infinito e f X Y sobrejetiva Como f é sobrejetiva por definição y Y x X tal que fx y Também podemos tomar x gy Y tal que fx y Defina a Função g Y X injetiva de acordo com o diagrama Y y x gy y fx fogy fgy fx y De Fato se y1 y2 Y com gy1 gy2 Aplicando f a ambos lados da igualdade temos fgy1 fgy2 fogy1 fogy2 Por definição do composta segue y1 y2 Sendo Y infinito então existe uma Função injetiva h IN Y tal que goh IN X é injetiva pois composta de injetivas também é Portanto X é infinito 4 Prova Como x é Finito e X ϕ se x ϕ não há o que provar existe uma Função bijetiva l In X cuja inversa e1 X In também é bijetiva Como Y é infinito existe uma Função injetiva h IN Y Definimos assim uma Função injetiva f ho e1 X Y Como f X Y é injetiva logo f X fX Y é uma bijeção possuindo inversa g1 fX X Considere a Função g Y X tal que gy g1y y fX e gy y e X se y ϕ fX Portanto g Y X é uma Função sobrejetiva 5 Prova Afirmação 1 A Função f é sobrejetiva Se n IN n pode ser escrito como produto de seus fatores primos n k1n pkαk 2α1 k2n pkαk Os números primos maiores que 2 são ímpares e o produto de ímpares é ímpar Então n 2m 2n 1 Portanto f é sobrejetiva Afirmação 2 A Função f é injetiva Se fmn fpq então 2m2n 1 2p2q 1 Se m p então 2m 2n 1 2p 2q 1 pela unicidade da fatoração Logo m p implicando n q Então mn pq e portanto f é injetora 6 Prova Se f X Y é sobrejetiva Então X y Y f1y Logo X é a união de conjuntos enumeráveis e portanto X é enumerável Obs Como f X Y é sobrejetiva Por definição y Y x X tal que fx y ou seja todo elemento x X é préimagem de um elemento y Y isto é x f1y Logo X y Y f1y 7 Prova Note que X 2kπ π2 k Z Pois senx 1 senx sen90 x π2 2kπ k Z Então podemos definir uma bijeção entre Z e X f Z X definida por fk 2kπ π2 Logo f é sobrejetiva pois é uma bijeção e como Z é enumerável então X é enumerável