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>
=========================================================================