Re: [obm-l] Comparacao de Infinitos

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

Claudio Buffara said:
> Caros colegas:
>
> Qual a relacao entre as cardinalidades dos seguintes conjuntos?
> A = P(N) = conjunto das partes de N (N = conjunto dos numeros naturais);
> B = conjunto das bijecoes de N em N;
> C = conjunto das funcoes de N em N.
>
> Naturalmente, B estah contido em C e, alem disso, dado um elemento
> qualquer de A (ou seja, um subconjunto {x1, x2, ...} de N) eh possivel
> encontrar um elemento de B (ou seja, uma bijecao f: N -> N ) tal que
> f(1) = x1, f(2) = x2, ... Isso implica que card(A) <= card(B) <=
> card(C).
>
> Se ao inves de N tivessemos um conjunto finito com k elementos, as
> cardinalidades de A, B e C seriam, respectivamente, 2^k, k! e k^k. Como
> 2^k/k! -> 0 e k!/k^k -> 0, quando k -> infinito, eh de se esperar que
> card(A) < card(B) < card(C) (desigualdades estritas), mas com conjuntos
> infinitos nunca se sabe...
> [...]

Como você já demonstrou, |A| <= |B| <= |C|.

Dada f em C, considere a aplicação g:N -> N definida por g(n) = f(1) +
f(2) + ... + f(n) (para simplificar as coisas, estou considerando N como o
conjunto {1, 2, ...}). Evidentemente, g é injetiva.

Defina agora, indutivamente, h(1) = g(1) e, para todo n, h(n+1) vale:

* min({n+1, n+2, ...} inter Im(g)) se h(n) - 1 pertence à h({1, 2, ..., n})
* h(n) - 1 caso contrário.

Não é muito difícil ver que h é uma bijeção, e que para toda função f
existe uma e só uma função h associada a ela. Logo |C| >= |B| <==> |B| =
|C|.

Finalmente, dada uma função f em C, considere a função g associada a ela
criada acima e tome o conjunto g(N). Novamente, isto é uma injeção de C em
A, logo |C| >= |A| <==> |C| = |A|. Logo |A| = |B| = |C|.

[]s,

-- 
Fábio Dias Moreira


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