Re: [obm-l] Subconjuntos

["Cl�udio \(Pr�tica\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

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" <tertuca@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
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 � <nicolau@mat.puc-rio.br>
=========================================================================

=========================================================================
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 � <nicolau@mat.puc-rio.br>
=========================================================================