Re: [obm-l] Enrolado com cardinalidades

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, Jan 10, 2004 at 12:51:46PM -0200, André Martin Timpanaro wrote:
> Estou com uma dúvida quanto a prova da afirmação abaixo:
> 
> -Dado um conjunto C, a cardinalidade do conjunto P de todos os subconjuntos 
> de C é sempre maior que a cardinalidade de C.
> 
> PROVA: Se C é um conjunto finito de cardinalidade n, então P tem 
> cardinalidade 2^n. E 2^n>n para todo n>=0.
> 
> Suponha agora que C seja infinito, C tem a mesma cardinalidade que o 
> subconjunto de P que contém todos os subconjuntos unitários de C e portanto 
> a cardinalidade de C é menor ou igual a cardinalidade de P.
> 
> Suponha por absurdo que exista uma bijeção entre C e P. Seja M um conjunto 
> com a seguinte propriedade, se x é um elemento de C e a bijeção associa a x 
> um conjunto ao qual x não pertence, então x pertence a M, do contrário, x 
> não pertence a M. Então por essa definição, M é subconjunto de C e essa 
> bijeção deve associar um elemento y de C ao conjunto M.
> Mas suponha que y pertence a M. Então, por definição, y não pertence a M 
> pois senão y estaria associado a um conjunto ao qual ele pertence e 
> pertenceria a M ao mesmo tempo. Mas se y não pertence a M, ele está 
> associado com um conjunto ao qual ele não pertence e ao mesmo pertence a C, 
> logo por definição deve pertencer a M. Então o fato de M ter algum elemento 
> associado a ele (qualquer elemento) é contraditório e logo M não está 
> associado a nenhum elemento de C. Absurdo!
> 
> Logo as cardinalidades de C e P são diferentes e portanto a cardinalidade de 
> P é maior que a de C.
> CQD.
> 
> -A minha dúvida é a seguinte: Ele não deveria considerar a possibilidade de 
> que M pertencesse a P antes de começar a construir M?
> 
> Encontrei a prova no livro abaixo e ela era atribuida a Georg Cantor:
> "The Art of Infinity"

Como está tudo certo, apenas você está confuso, eu sugeriria reescrever
com um pouco mais de notação matemática.

Seja f: C -> P seja uma função. Seja

R = { c em C | c não pertence a f(c) }

Assim, para x em C,

x em R <=> x não em f(x).

Suponha R = f(r): teríamos

r em R <=> r não em R

o que é um absurdo. Assim R não está na imagem de f
e portanto não existe nenhuma bijeção de C em P.

[]s, N.
=========================================================================
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
=========================================================================