[obm-l] RES: [obm-l] Sobre funções sobrejetoras e cardinalidade de conjuntos

["David Cardoso" <david-obm@xxxxxxxxxxxx>]

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: owner-obm-l@xxxxxxxxxxxxxx [mailto:owner-obm-l@xxxxxxxxxxxxxx] Em
> nome de Marcelo Salhab Brogliato
> Enviada em: domingo, 2 de setembro de 2007 04:05
> Para: obm-l@xxxxxxxxxxxxxx
> 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 <david-obm@xxxxxxxxxxxx> 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
=========================================================================