(a)
Defina o que vem a ser um conjunto enumerável em
.
(b)
Mostre que se
e
são conjuntos enumeráveis de
então
é enumerável.
(b)
Passo 1
O enunciado pede duas coisas:
- Definir o que é um conjunto enumerável em
. - Mostrar que, se
e são enumeráveis, então também é enumerável.
Vamos usar a ideia de que “enumerável” significa “imagem depor uma função sobrejetora”.
Passo 2
Definição de conjunto enumerável:
Um conjunto é enumerável se existe uma função
Um conjunto
que seja sobrejetora (ou seja, para todo
existe
com
). Em particular, isso inclui o caso em que
é finito (basta estender a sequência com valores repetidos).
Passo 3
Como
e
são enumeráveis, existem duas funções sobrejetoras
Passo 4
Vamos construir uma nova função
intercalando é ímpar},\ g\bigl(n/2\bigr), &se
é par. \end{cases}]
Passo 5
Prova de que
é sobrejetora em
:
Se , então existe
tal que
, e
.
Se , então existe
tal que
, e
.
Logo, todo elemento de é atingido por
.
Se
Se
Logo, todo elemento de
Passo 6
Como existe
sobrejetora, concluímos que
é enumerável.
Resposta
(a) Um conjunto
(b) Sejam
sobrejetoras. Definindo
vemos que . Portanto
é enumerável.