Re: [obm-l] Sobre funções sobreje toras e cardinalidade de conjuntos

["Marcelo Salhab Brogliato" <msbrogli@xxxxxxxxx>]

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 <david-obm@suati.com.br> 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
=========================================================================