Exercícios Resolvidos - Conjuntos Enumeráveis, Funções Injetivas e Sobrejetivas

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 N N N pondo f1n 2n 1 e fm 1 n 2m 2n 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 IR sinx 1 é enumerável Corolário 3 exercício O produto cartesiano de dois conjuntos enumeráveis é enumerável Exemplo sabemos que N é enumerável então N N é enumerável Definir N primos e ideais Maximals e dê exemplo Defina Ideais e MDC e dê exemplo resolvido Defina Relação de equivalência e dê exemplo resolvido Defina classe de equivalência e dê exemplo resolvido Defina Conjunto quociente e dê exemplo resolvido Defina operação binária e dê exemplo resolvido EXERCÍCIO Prove que ab 1 rs Z tais que ar bs 1 1 O produto cartesiano de dois conjuntos enumeráveis é enumerável Prova Sejam X e Y conjuntos enumeráveis Então existem Funções injetivas f X IN e g Y IN Logo h X x Y IN x IN dada por hxy fx gy é injetiva Resta mostrar que IN x IN é enumerável o que implica que X x Y é enumerável Para isso defina a Função l IN x IN IN dada por lmn 2m 3n Pela decomposição em Fatores primos l é injetiva Logo temos uma bijeção entre IN x IN e lIN x IN IN que é enumerável Portanto IN x IN é enumerável e conseqüente X x Y é enumerável Obs usamos o seguinte resultado Corolário 1 pág 7 livro Elon Análise Real f X Y é injetiva e Y é enumerável então X é enumerável 2 Se X é infinito e f injetova então Y é infinito Prova Sejam X infinito e f X Y uma Função injetiva Como X é infinito podemos definir uma função injetiva g IN X conforme o seguinte diagrama IN X Y f o g IN Y Como f e g são injetivas segue que f o g IN Y é injetiva pois a composta de funções injetivas é injetiva Logo concluímos que Y é infinito 3 Se Y infinito e f sobrejetiva então X é infinito Prova Sejam Y infinito e f X Y uma função sobrejetiva Como f é sobrejetiva temos que b Y a X tal que fa b Além disso podemos escolher a gb Y tal que fa b Definimos assim uma função g Y X injetiva De fato note que Y X Y b g a fa fogb fgb fa b g é injetiva pois considerando b₁ b₂ Y com gb₁ gb₂ Aplicando f em ambos membros da última igualdade obtemos fgb₁ fgb₂ f gb₁ f gb₂ Logo por definição da composta temos b₁ b₂ Como Y é infinito então existe uma função injetiva h IN Y tal que IN Y X g o h g o h IN X é injetiva pois é composta de funções injetivas Portanto 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 Prova Primeiro vamos provar que existe uma função f X Y injetiva Como X é finito e X pois se X não temos que provar podemos considerar a seguinte função bijetiva ℓ In X Sua inversa ℓ¹ X In é também bijetiva Como Y é infinito existe uma aplicação injetiva ψ In Y Logo podemos definir uma função injetiva f ψ ℓ¹ X Y conforme o diagrama X IN Y ℓ¹ In ψ f ψ ℓ¹ X Y Pois a composta de funções injetivas é injetiva Portanto f X Y é injetiva como f X Y é injetiva logo f X fX Y é uma bijeção possuindo inversa g¹ fX X Considere a função g Y X dada por gy g¹y se y fX e gy y₁ X se y fX Portanto g é uma função sobrejetiva 5 f IN x IN IN tal que f1n 2n 1 e fm 1 n 2m2n 1 Prove que f é uma bijeção Prova Seja f IN x IN IN dada por f1n 2n 1 e fm 1 n 2m2n 1 f é sobrejetora Dado n IN podemos escrever n como produto dos seus fatores primos n k1n pkαk 2α₁ k2n pkαk Como os primos maiores que 2 são ímpares e o produto de números ímpares é um número ímpar então n 2m2n 1 Logo f é sobrejetora f é injetora seja fmn fpq então 2m2n1 2p2q1 Se m p então os números são diferentes pela unicidade de fatoração Logo m p e portanto n q então mn pq e portanto f é injetora como f é sobrejetora e injetora então f é bijetora 6 sejam Y enumeravel e f X Y sobrejetiva tal que para cada y Y f1y é enumeravel Prove que X é enumeravel Prova Como f X Y é sobrejetiva então X f1y y Y ou seja X é a união de conjuntos enumeráveis e portanto X é enumerável 7 Prove que o conjunto X x ℝ senx 1 é enumerável Prova Temos que Senx 1 Senx sen90 x 90 k360 k ℤ Ou seja a solução da equação senx1 é x π2 2kπ k ℤ Logo podemos reescrever o conjunto X da seguinte forma X 2kπ π2 k ℤ Podemos definir uma bijeção entre ℤ e X ou seja f ℤ X dada por fk 2kπ π2 Logo como f é sobrejetiva pois é uma bijeção e ℤ é enumerável então o conjunto X é enumerável 1 o Seja n um número inteiro positivo n 1 Dizemos que n é primo se os únicos divisores positivos de n são 1 e n Exemplo são números primos 2 3 5 7 11 13 o Seja A um anel Um ideal M A chamase maximal se para qualquer ideal I de A tal que M I implica I M ou I A Exemplo No anel dos inteiros Z o ideal gerado por 5 5 Z é maximal Pois se 5 m Z m5 m 1 ou m 5 m Z ou m 5 2 Seja A um anel comutativo Um subconjunto I A I é dito um ideal de A se i xy I x y I ii ax I a A e x I Exemplo Seja Z anel O conjunto 2Z 2n n Z Z é um ideal de Z De fato 2Z Pois 20 0 2Z Além disso i sejam 2m₁ 2m₂ 2Z então 2m₁ 2m₂ 2m₁ m₂ 2Z ii sejam a Z e 2m₁ 2Z a2m₁ 2am₁ 2Z o Sejam a b Z um elemento de Z dizse máximo divisor comum mdc de a e b se i d 0 ii d a e d b iii se d Z tal que d a e d b então d d Exemplo Sejam a 4 e b 6 mdc 4 6 2 De fato i 2 0 ii 2 4 e 2 6 iii Os divisores comuns a 4 e 6 são 1 2 todos divisores de 2 3 Uma relação R sobre um conjunto Ē ø é dita relação de equivalência sobre Ē se e só se R é reflexiva simétrica e transitiva Ou seja i x R x x Ē ii se x R y então y R x xy Ē iii se x R y e y R z então x R z xyz Ē Exemplo A relação de igualdade sobre IR é uma relação de equivalência Pois i x x IR x x ii xy IR tal que x y y x iii xyz IR tais que x y e y z então x z 4 Seja R uma relação de equivalência sobre E E um conjunto não vazio Seja a Ē chamase classe de equivalência determinada por a módulo R o subconjunto ȧ de Ē constituído por elementos x tais que x R a ou seja ȧ x Ē x R a Exemplo Considere a seguinte relação de equivalência R aa bb cc ab ba Temos ȧ ab b ab c c 5 O conjunto das classes de equivalência determinadas sobre Ē um conjunto não vazio pela relação de equivalência R é chamado conjunto quociente de Ē por R e denotado por Ē R Exemplo Considere a relação de equivalência R aa bb cc ab ba Temos ȧ ab b c c e o conjunto quociente é Ē R ab c 6 uma operação binária em um conjunto X é uma Função X x X X dada por xy x y Exemplo A soma dos números reais IR é uma operação binária IR x IR IR xy x y 7 ab 1 rs Z tais que ar bs 1 Prova Sabemos que para quaisquer ab Z existem rd Z tais que ar bs d mdcab Como ab 1 então existem rs Z tais que ar bs 1 Reciprocamente supoña que existam rs Z tais que ar bs 1 Logo qualquer divisor de a e b é também divisor de 1 Então os únicos divisores comuns aos elementos a e b são 1 Donde o máximo divisor comum é 1 ou seja ab 1