Dá pra provar um resultado mais geral que é o seguinte: Seja X um conjunto qualquer. Então nenhuma função f : X --> P(X) é sobrejetora. DEM: Suponha o contrário. Seja F uma sobrejeção de X em P(X). (repare que a imagem de cada elemento de X por F é um subconjunto de X)
Seja A = { "x" pertencentes a X tais que "x" não pertence a F(x) } Como F é sobrejetora, existe "a" em X tal que F(a) = A. Pergunta: "a" pertence a A ? Se "a" pertence a A, então teremos (pela definição de A) que "a" não pertence a F(a) = A ==> Contradição Mas se "a" não pertence a A, então teremos que "a" pertence a F(a) = A ==> Contradição Assim, em qualquer caso caímos em contradição, a qual originou-se da nossa hipótese de que existe uma sobrejeção de X em P(X). Logo, tal sobrejeção não pode existir. ********* Agora voltamos ao problema original: Se P(N) é enumerável então existe uma bijeção G: N --> P(N). Em particular, G é sobrejetiva, o que contradiz o resultado que acabamos de provar. Logo, concluímos que P(N) não é enumerável. Um abraço, Claudio. ----- Original Message ----- From: "Tertuliano Carneiro de Souza Neto" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tuesday, January 21, 2003 4:46 PM Subject: [obm-l] Subconjuntos Olá! Alguém pode dar uma mãozinha? Prove que o conjunto P(N) de todos os subconjuntos de N não é enumerável. Obs: P simboliza o conjunto das partes. _______________________________________________________________________ Yahoo! GeoCities Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e acessórios. http://br.geocities.yahoo.com/ ========================================================================= 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 O administrador desta lista é <[EMAIL PROTECTED]> ========================================================================= ========================================================================= 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 O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================