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
f: N to S
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
f: N to S
a enumeração de S. Vamos extrair de f apenas os termos que caem em A. Definimos recursivamente os índices n₁,n₂,… assim:
n1 = minkinN: f(k)in A,
ni+1 = mink>ni: f(k)in A
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.

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.

Exercícios relacionados