Atividade 3

I 20 pt Para cada função a seguir informe se ela é injetora e se ela é sobrejetora Os domínio e contradomínio das funções são o conjunto dos números inteiros Justifique sua resposta 1 fn n 1 2 fn n2 1 3 fn n 4 fn n2 II 15 pt Seja f a função de X 012345 para X definida como fx 4x mod 6 Responda os itens a seguir 1 Escreva f como um conjunto de pares ordenados 2 A função f é injetora Justifique sua resposta 3 A função f é sobrejetora Justifique sua resposta III 10 pts Responda os seguintes itens Qual o conjunto 3 para a relação de equivalência ρ 11221221133132233344554554 Qual o conjunto 1 para a relação de equivalência de congruência módulo 2 em Z IV 15 pt Encontre a relação de equivalência expressa como um conjunto de pares ordenados sobre abcde cujas classes de equivalência são a bde c V 20 pt Encontre cinco relações de equivalência expressa como conjuntos de pares ordenados definidas sobre 123 VI 20 pts Sejam A e B conjuntos finitos Responda justificando sua resposta 1 Quantas funções F A B podem existir no máximo se A 2 e B 4 2 Quantas funções injetoras F A B podem existir no máximo se A 2 e B 3 3 Quantas funções sobrejetoras F A B podem existir no máximo se A 3 e B 2 4 Quantas funções bijetoras F A B podem existir no máximo se A 3 e B 3 5 1 Relação onde cada elemento é equivalente apenas a si mesmo relação identidade R1 1 1 2 2 3 3 2 Relação onde 1 e 2 são equivalentes e 3 é equivalente apenas a si mesmo R2 1 1 2 2 3 3 1 2 2 1 3 Relação onde 2 e 3 são equivalentes e 1 é equivalente apenas a si mesmo R3 1 1 2 2 3 3 2 3 3 2 4 Relação onde todos os elementos são equivalentes entre si R4 1 1 2 2 3 3 1 2 2 1 1 3 3 1 2 3 3 2 5 Relação onde 1 e 3 são equivalentes e 2 é equivalente apenas a si mesmo R5 1 1 2 2 3 3 1 3 3 1 Essas são cinco diferentes relações de equivalência definidas sobre o conjunto 1 2 3 1 6 Item 1 Quantas funções F A B podem existir no máximo se A 2 e B 4 A quantidade total de funções F A B é dada pelo número de escolhas possíveis para cada elemento de A Como A 2 temos 2 elementos em A e cada elemento pode ser mapeado para um dos 4 elementos de B Para cada um dos 2 elementos de A existem 4 escolhas possíveis em B Logo o número total de funções é 42 16 Resposta Existem 16 funções no máximo Item 2 Quantas funções injetoras F A B podem existir no máximo se A 2 e B 3 Para que a função seja injetora cada elemento de A deve ser mapeado para um elemento diferente em B O primeiro elemento de A tem 3 opções em B e o segundo elemento de A tem 2 opções restantes já que a função é injetora Portanto o número de funções injetoras é 3 2 6 Resposta Existem 6 funções injetoras no máximo Item 3 Quantas funções sobrejetoras F A B podem existir no máximo se A 3 e B 2 Para que a função seja sobrejetora todos os elementos de B devem ser atingidos por pelo menos um elemento de A Nesse caso o número de funções sobrejetoras corresponde ao número de maneiras de particionar A em dois subconjuntos não vazios que serão mapeados para os dois elementos de B Isso é dado pelo número 1 de maneiras de dividir 3 elementos em dois subconjuntos não vazios que é igual ao número de funções sobrejetoras Número de funções sobrejetoras 23 2 6 Resposta Existem 6 funções sobrejetoras no máximo Item 4 Quantas funções bijetoras F A B podem existir no máximo se A 3 e B 3 Para que a função seja bijetora ela precisa ser injetora e sobrejetora ou seja deve mapear cada elemento de A para um único elemento de B sem repetir ou omitir nenhum elemento O número de funções bijetoras é dado pelo número de permutações de 3 elementos que é 3 3 2 1 6 Resposta Existem 6 funções bijetoras no máximo 2 1 Função 1 fn n 1 Se fn1 fn2 então n1 1 n2 1 n1 n2 Logo a função é injetora pois n1 n2 implica que fn1 fn2 Dada a equação y n 1 temos n y 1 Como n Z para todo y Z a função é sobrejetora Conclusão A função fn n 1 é injetora e sobrejetora ou seja é bijetora Função 2 fn n2 1 Se fn1 fn2 então n2 1 1 n2 2 1 n2 1 n2 2 Isso significa que n1 n2 ou n1 n2 Portanto a função não é injetora pois dois valores distintos um positivo e seu negativo podem ter a mesma imagem A equação que precisamos resolver é y n2 1 o que resulta em n2 y 1 Para que n2 seja um número inteiro y 1 deve ser um quadrado perfeito Como nem todo número y Z faz com que y 1 seja um quadrado perfeito a função não é sobrejetora Conclusão A função fn n2 1 não é injetora e não é sobreje tora 1 Função 3 fn n Se fn1 fn2 temos n1 n2 Isso significa que n1 n2 ou n1 n2 Portanto a função não é injetora pois dois valores diferentes um positivo e seu negativo podem ter a mesma imagem Como fn n a imagem de fn inclui apenas números inteiros não negativos ou seja Z0 Portanto a função não é sobrejetora pois não cobre todos os inteiros apenas os não negativos Conclusão A função fn n não é injetora e não é sobrejetora Função 4 fn n2 Aqui x representa a função piso que retorna o maior número inteiro menor ou igual a x Se fn1 fn2 temos n12 n22 Isso significa que n1 e n2 podem ter valores diferentes e ainda assim resultar no mesmo valor quando divididos por 2 e arredondados para baixo Por exemplo f3 1 e f4 2 o que mostra que valores diferentes podem resultar em valores próximos arredondados Portanto a função não é injetora Dada a equação fn n2 para qualquer valor inteiro y Z podemos sempre encontrar um n tal que n2 y Portanto a função é capaz de cobrir todos os valores inteiros y Z Conclusão A função fn n2 não é injetora mas é sobrejetora 2 Item 1 A função fx 4x mod 6 aplica a operação de multiplicação por 4 no conjunto X 0 1 2 3 4 5 e depois o resultado é calculado módulo 6 Valores de fx Para x 0 f0 4 0 mod 6 0 Para x 1 f1 4 1 mod 6 4 Para x 2 f2 4 2 mod 6 8 mod 6 2 Para x 3 f3 4 3 mod 6 12 mod 6 0 Para x 4 f4 4 4 mod 6 16 mod 6 4 Para x 5 f5 4 5 mod 6 20 mod 6 2 Assim f pode ser representada como o conjunto de pares ordenados f 0 0 1 4 2 2 3 0 4 4 5 2 Item 2 f0 f3 0 f1 f4 4 f2 f5 2 Como há diferentes valores de x que produzem o mesmo valor de fx a função não é injetora 1 Item 3 Os valores que fx assume são 0 2 4 Portanto a função não é sobre jetora pois os valores 1 3 e 5 não são atingidos por nenhum x X 2 3 Qual o conjunto 3 para a relação de equivalência ρ A relação de equivalência ρ é dada como ρ 1 1 2 2 1 2 2 1 1 3 3 1 3 2 2 3 3 3 4 4 5 5 4 5 5 4 Queremos encontrar o conjunto 3 ou seja o conjunto de todos os ele mentos que são equivalentes a 3 de acordo com a relação ρ A partir da relação ρ podemos ver os pares que envolvem o número 3 1 3 3 1 3 2 2 3 3 3 Portanto o conjunto 3 contém os elementos que são equivalentes a 3 ou seja 1 2 3 Resposta O conjunto 3 1 2 3 Qual o conjunto 1 para a relação de equivalência de con gruência módulo 2 em Z Na congruência módulo 2 dois números a e b são equivalentes se a b mod 2 ou seja se a diferença a b é divisível por 2 Para o número 1 o conjunto de todos os inteiros que são congruentes a 1 módulo 2 são aqueles que deixam o resto 1 quando divididos por 2 Esses números são todos os ímpares ou seja 1 3 1 1 3 5 Resposta O conjunto 1 3 1 1 3 5 1 4 Relação de Equivalência A classe a indica que a só é equivalente a si mesmo Logo os pares da relação que envolvem a são a a A classe b d e indica que b d e e são todos equivalentes entre si Logo os pares da relação que envolvem esses elementos são b b b d b e d b d d d e e b e d e e A classe c indica que c só é equivalente a si mesmo Logo os pares da relação que envolvem c são c c Assim a relação de equivalência é composta pelos seguintes pares orde nados a a b b b d b e d b d d d e e b e d e e c c 1