Olá David.. veja que o q vc esta pedindo pra demonstrar se torna "obvio" qdo usamos diagramas de Venn... desenhe ai os conjuntos B e A.. para cada elemento a em A, tem que existir um elemento b em B, tal que g(b) = a.. [pois g é sobrejetiva]
podem existir 2 elementos diferentes em B que levam ao mesmo elemento em A? SIM! pois nada foi dito a respeito de injetividade.. isto é.. se a funcao for injetiva, eles possuem o mesmo numero de elementos (definicao?!).. mas se nao for, B possui necessariamente mais elementos que A.. por que? pq se B possuisse menor elementos que A, seria impossivel ele ser sobrejetivo, visto que cada elemento de B pode mapear um, e apenas um, elemento de A.. assim: |B| >= |A|... e, consequentemente, 2^|B| >= 2^|A|.. talvez uma prova por absurdo? vamos tentar... suponha que |B| < |A|... como temos |B| elementos em B, podemos mapear no maximo |B| elementos em A.. sobrando |A| - |B| > 0 elementos nao mapeados.. absurdo! pois g é sobrejetiva..logo: |B| >= |A|... e 2^|B| >= 2^|A|. vamos tentar uma outra ideia: Seja g: B->A sobrejetiva. vamos dizer que f(a) = g^-1(a)... entao f(a) é conjunto dos pontos de B que levam sobre o elemento a em A... (é um conjunto pois g nao eh necessariamente injetiva) como g é sobrejetiva, |f(a)| >= 1... pois existe ao menos 1 elemento em B que leva para a pertencente a A. como g é funcao, temos que g(b) pertencente a A tem cardinalidade 1.. isto é: cada elemento de B é levado a um unico elemento de A... assim, todos os conjuntos f(a) formam uma particao de B.. pois a uniao deles resulta em B, e eles sao disjuntos 2 a 2.. e a uniao de todos os conjuntos g(b) é igual a A... [eles nao sao necessariamente disjuntos 2 a 2] deste modo: |B| = |U f(a)| = Sum |f(a)| >= Sum 1 = Sum |g(b)| >= |A| logo: |B| >= |A|... e 2^|B| >= 2^|A| espero q nao tenha ficado mto confuso.. e existe uma chance razoavel deu ter errado alguma coisa.. tenho dificuldades em formalizar essas coisas.. abracos, Salhab On 9/1/07, David Cardoso <[EMAIL PROTECTED]> wrote: > Gostaria de ajuda com esse exercício: > > Mostre que se existe um mapeamento de B sobre A (i.e., sobrejetor), então > 2^|A| <= 2^|B|. > [Dica: Dado g mapeando B sobre A (i.e., sobrejetor), seja f[X] = g^-1[X], > para todo X contido em A] > > Alguém me ajuda? > > []s, David. > > > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > ========================================================================= > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================