Bom Salhab.. Muito obrigado. Entendi tudo.
Realmente, desenhando os diagramas consegui visualizar bem o problema. Esse é um exercício de uma disciplina que fala de axiomas e conjuntos. Nela, quase nada é óbvio. Por exemplo, nem mesmo 2^|A| <= 2^|B| <==> |A| <= |B| pode ser colocado na demonstração sem que seja bem explicado. Pelo que estudei, tenho quase certeza de que a resolução esperada pra esse exercício é que se construa uma função injetora H: P(A) -> P(B).. Onde P(X) é o conjunto das partes de X. Sem muita experiência com demonstrações, depois que entendi bem o problema, acabei fazendo assim: -- Seja g : B->A, sobrejetor. Considere H: P(A)->P(B) definido assim: H(X) = g-1[X], onde X é um subconjunto de A. Precisamos mostrar que H é injetora. Tome X_1, X_2 subconjuntos distintos de A. (X_1 != X_2). Precisamos mostrar que H(X_1) != H(X_2). Podemos supor sem perder generalidade que x pertence a X_1 e x não-pertence a X_2. X pertence a X_1 ==> X pertence a A ==> existe b pertencente a B tal que g(b) = x ==> b pertence a H(X_1). Suponha que b pertence a H(X_2). Então, b pertence a g^-1[X_2] ==> g(b) pertence a X_2. Mas g(b) = x, então acabamos de concluir que x pertence a X_2. Absurdo, pois, por definição, x não-pertence a X_2. Logo, b não pertence a H(X_2). Como sabemos que b pertence a H(X_1), então H(X_1) != H(X_2). Mostramos que X_1 != X_2 ==> H(X_1) != H(X_2), portanto, H é injetora. Com H é injetora, temos que |P(A)| <= |P(B)| ==> 2^|A| <= 2^|B|. (Essa coisa de mostrar que |X| <= |Y| criando funções injetoras de X em Y é uma das poucas coisas que o professor deixa a gente usar sem demonstrar.) Bem, vou entregar a solução desse exercício assim mesmo - a menos que você ou alguém ache que essa solução não está suficientemente rigorosa ou encontre alguma falha lógica nas passagens.. Mais uma vez obrigado, David > -----Mensagem original----- > De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Em > nome de Marcelo Salhab Brogliato > Enviada em: domingo, 2 de setembro de 2007 04:05 > Para: [email protected] > Assunto: Re: [obm-l] Sobre funções sobrejetoras e cardinalidade de > conjuntos > > 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 > ======================================================================= > == ========================================================================= 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 =========================================================================
