Mostre que qualquer subconjunto de um conjunto enumerável é também enumerável.
Passo 1
A questão pede para mostrar que se temos um conjunto enumerável S e um subconjunto A⊆S, então A também é enumerável. O conteúdo aqui é a definição de conjunto enumerável (existe enumeração por N) e como, a partir de uma enumeração de S, extrair uma enumeração de A.
Passo 2
Primeiro, recorde a definição de conjunto enumerável: um conjunto S é enumerável se existe uma função sobrejetiva
que “lista” todos os elementos de S. Note também os casos triviais: se A for vazio ou finito, já é contável por definição.
Passo 3
Agora, suponha que A seja infinito. Pegue
a enumeração de S. Vamos extrair de f apenas os termos que caem em A. Definimos recursivamente os índices n₁,n₂,… assim:
Como A⊆S e A é infinito, essa sequência define infinitos n_i.
Passo 4
Finalmente, definimos
g: \mathbb{N} \to A
por
g(i) = f(n_i).
Por construção, g é sobrejetiva em A (todo elemento de A ocorre em alguma f(n_i)). Logo g é uma enumeração de A, mostrando que A é enumerável.
g: \mathbb{N} \to A
por
g(i) = f(n_i).
Por construção, g é sobrejetiva em A (todo elemento de A ocorre em alguma f(n_i)). Logo g é uma enumeração de A, mostrando que A é enumerável.
Resposta
Qualquer subconjunto de um conjunto enumerável é também enumerável, pois podemos extrair da enumeração original uma enumeração que lista exatamente os elementos do subconjunto.