Re: [obm-l] Teorema de Cantor

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 17.03.05 09:13, Paulo Santa Rita at p_ssr@hotmail.com wrote:

> Ola Marcio e demais
> colegas desta lista ... OBM-L,
> 
> Algumas problemas sobre funcoes e cardinalidade de conjuntos sao muito
> bonitos ... Lendo este ai embaixo eu me lembrei de alguns outros, tambem
> faceis mas que tem solucoes engenhosas :
> 
> 1) Seja X um conjuto infinito enumeravel. Mostre que o conjunto de todas as
> PARTES FINITAS de X e enumeravel.
>
S.p.d.g. podemos supor que X = N.
Esse conjunto eh igual a UNIAO(k>=0) P_k, onde P_k = conjunto das partes de
N com exatamente k elementos.
Cada P_k eh enumeravel, pois existe uma sobrejecao obvia de N^k em P_k e N^k
eh enumeravel para todo k em N.
Logo, UNIAO(k>=0) P_k eh a uniao enumeravel de conjuntos enumeraveis. Logo,
eh enumeravel.

> 2) Seja X um conjunto e f:X->X uma funcao. Um conjunto Y contido em X e dito
> ser estavel em relacao a funcao f se f(Y) esta contido em Y. Claramente que
> o CONJUNTO VAZIO e o proprio X sao estaveis em relacao a qualquer funcao
> f:X->X. Isto posto, mostre que um conjunto A e finito se, e somente se,
> existe uma funcao f:A->A que so admite como conjuntos estaveis A e o
> CONJUNTO VAZIO.
>
Seja A finito. 
Se A eh vazio ou unitario, o resultado eh obvio.
Se A tiver 2 ou mais elementos, podemos escrever s.p.d.g. A = {1,2,...,n}.
Seja f:A -> A dada por f(k) = k+1 para 1<=k<=n-1 e f(n) = 1.
Seja X um subconjunto proprio nao vazio de A e seja k o maior elemento de X.
Se k < n, entao f(k) = k+1 nao pertence a X.
Logo, nesse caso F(X) nao estah contido em X.
Se k = n, seja h o menor elemento de A-X (que existe pois X eh proprio).
Se h = 1, entao 1 = h = f(k) = f(n), ou seja F(X) nao pertence a X.
Se h > 1, entao h-1 pertence a X mas h = f(h-1) nao. Novamente concluimos
que F(X) nao pertence a X.
Logo, os unicos subconjuntos estaveis de A sao o conjunto vazio e o proprio
A.

Sejam A infinito e f:A -> A uma funcao arbitraria.
Precisamos provar que A tem um subconjunto proprio B tal que f(b) estah
contido em B.
Seja a um elemento arbitrario de A.
Seja B = {f(a), f(f(a)), f(f(f(a))), ...}.
Eh obvio que f(B) estah contido em B.
Se a nao pertencer a B, entao B serah um subconjunto proprio de A.
Se f(a) = a ou, para algum b em B, f(b) = a, entao B serah finito e,
portanto, um subconjunto proprio de conjunto infinito A.
Logo, se A eh infinito, entao qualquer que seja f:A -> A, vai existir um
subconjunto proprio de A que eh estavel em relacao a f.

 
> 3) Seja X um conjunto infinito NAO-ENUMERAVEL. Mostre que e possivel
> exprimir X como uma uniao infinita de conjuntos infinitos dois a dois
> disjuntos.
>
Seja A_1 um subconjunto enumeravel de X.
Para cada n em N, escolhemos um subconjunto enumeravel A_(n+1) de
X - (A_1 uniao A_2 uniao ... uniao A_n).
UNIAO(n em N) A_n eh enumeravel (uniao enumeravel de conjuntos enumeraveis).
Alem disso, eh obvio que A_i inter A_j = vazio se i <> j.
Finalmente, pondo Y = X - UNIAO(n em N) A_n, teremos que:
A_i inter Y = vazio, para todo i.
Logo, a decomposicao eh X = Y uniao UNIAO(n em N) A_n.

[]s,
Claudio.

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