Para cada n in N, seja Pn=X subset N ; card X=n. Prove que Pn é enumerável. Conclua que o conjunto Pf dos subconjuntos finitos de N é enumerável.

Passo 1

Resumo do enunciado e conteúdo
O exercício pede para mostrar que, para cada ninN, o conjunto
Pn=,XsubsetNmidcard,X=n
é enumerável (ou seja, possui bijeção ou injeção em N). Em seguida, devemos concluir que
Pf=cupninNPn
— o conjunto de todos os subconjuntos finitos de N — também é enumerável.
Para isso, vamos usar dois fatos clássicos:
  1. O produto cartesiano de conjuntos enumeráveis é enumerável (em particular N^n é enumerável para todo n).
  2. A união enumerável de conjuntos enumeráveis é enumerável.

Passo 2

N^n é enumerável
Base: N^1=N é enumerável por definição.
Passo indutivo: suponha que N^n seja enumerável. Então
N^n+1 ;=;N^ntimesN
é produto de dois conjuntos enumeráveis, logo é enumerável.
Por indução, N^n é enumerável para todo ninN.

Passo 3

Injeção de Pn em N^n
Dado XinPn, escrevemos seus elementos em ordem crescente:
X=,x1,x2,dots,xn, x1<x2<cdots<xn
Definimos
fcolonPn;longrightarrow;N^n, f(X)=(x1,x2,dots,xn)
Essa aplicação é injetiva porque a tupla ordenada determina unicamente o conjunto X.

Passo 4

Conclusão de que Pn é enumerável
Como há uma injeção fcolonPntoN^n e N^n é enumerável (Passo 2), segue que Pn é, no máximo, enumerável. Além disso, Pn é não-vazio para todo n, logo é enumerável infinito.

Passo 5

Pf é enumerável
Por definição
Pf=cupninNPn
Cada Pn é enumerável (Passo 4) e a união sobre ninN é união enumerável de conjuntos enumeráveis. Portanto Pf é enumerável.

Resposta

Para cada ninN, Pn é enumerável, e consequentemente o conjunto
Pf=cupninNPn dos subconjuntos finitos de N também é enumerável.

Exercícios relacionados