Sejam
um conjunto finito e
enumerável. Mostre que
é enumerá vel.
Passo 1
O que o enunciado dá e o que pede.
- Dado:
é um conjunto finito. - Dado:
é enumerável. - Pedido: mostrar que
é enumerável.
Aqui “enumerável” será usado no sentido usual: existe uma enumeração por uma sequência, isto é, existem elementos
(uma sequência indexada por
) que listam todos os elementos de
. A enumeração pode repetir termos, mas o importante é que todo elemento de
apareça na sequência.
Passo 2
Lembrando definições e estratégias possíveis (explicação didática).
- Conjunto finito: dizer que
é finito significa que existe um inteiro e uma lista finita que contém exatamente os elementos de . - Conjunto enumerável: dizer que
é enumerável significa que existe uma sequência tal que cada elemento de aparece em algum . Em termos de funções, existe tal que (surjetiva); muitas vezes assume-se bijetora se for infinito contável. - Estratégia: construir explicitamente uma sequência que enumere
. A ideia simples é primeiro listar os elementos de (são finitos) e depois listar os elementos da enumeração de . Precisamos só observar que repetições não atrapalham a propriedade de ser enumerável: a sequência pode repetir elementos, desde que cubra todos.
Passo 3
Tratar primeiro o caso trivial:
finito.
Se
for finito então
é a união de dois conjuntos finitos, logo finito. Todo conjunto finito é enumerável (basta escrever seus elementos em uma lista finita). Assim, neste caso
é enumerável. Fim deste caso.
Passo 4
Caso principal:
é infinito e enumerável.
Como
é enumerável, existe uma enumeração
isto é, uma sequência
que atinge todos os elementos de
.
Como
é finito, escrevemos
para algum
(o caso
corresponde a
).
Passo 5
Construção explícita da enumeração de [A\cup B).
Defina uma sequência
por
Ou seja, os primeiros
(lista de
) e, a partir do termo
, aparecem
(a enumeração de
).]
Passo 6
Verificação de que
enumera
.
- Todo elemento de
aparece entre por construção, logo . - Todo elemento de
aparece em algum e, como , também aparece em . Logo . - Portanto
. Como por definição do codomínio de , segue .
Observação: se algum
coincidir com algum
haverá repetições na sequência
; isso não é problema, pois a enumeração só exige que todo elemento apareça pelo menos uma vez.
Passo 7
Conclusão final e comentário prático.
A sequência
dada é uma enumeração de
. Logo
é enumerável. Em linguagem prática: anexar uma lista finita (os elementos de
) no começo de uma enumeração de
dá uma enumeração de
.