(José Igor) Prove que se X é infinito enumerável, o conjunto das partes finitas de X também é (infinito) enumerável.

Passo 1

O enunciado pede para mostrar que, se X é um conjunto infinito enumerável, então o conjunto
F = ,Asubseteq X mid A é finito é
também é enumerável (e infinito).
O conteúdo que vamos usar envolve:
– a noção de enumerabilidade (contável) de um conjunto,
– o fato de que produto finito de conjuntos enumeráveis é enumerável,
– que união enumerável de conjuntos enumeráveis é enumerável.

Passo 2

Como X é enumerável infinito, existe uma bijeção
fcolon Nto X
Denotemos xn = f(n). Assim
X = ,x1,x2,x3,dots
Vamos particionar F pelo tamanho dos subconjuntos:
F = cupk=0^infty Fk,
onde
Fk = ,Asubseteq X mid |A|=k

Passo 3

Para cada k>=1, considere o produto cartesiano
X^k = Xtimes Xtimescdotstimes X(k vezes)
Sabemos que X é enumerável e, por indução, qualquer produto finito de conjuntos enumeráveis é enumerável. Logo,
X^k é enumerável éá
Além disso, existe uma função sobrejetiva
pik: X^k to Fk
que a uma k-tupla (xn1,xn2,dots,xnk) associa o conjunto
xn1,xn2,dots,xnk.
Isto mostra que Fk é no máximo enumerável.

Passo 4

O caso k=0 é trivial, pois F0=varnothing tem um único elemento.
Assim cada Fk é enumerável (ou finito, no caso k=0), e
F = cupk=0^infty Fk
é união contável de conjuntos enumeráveis. Como união contável de enumeráveis é enumerável, F é enumerável.

Passo 5

Para ver que F é infinito, basta notar que, para cada ninN, o conjunto x1,x2,dots,xn pertence a F, e esses são todos distintos. Logo há infinitos elementos em F.

Resposta

O conjunto das partes finitas de X é enumerável infinito.

Exercícios relacionados