Questão 1: (3.0 pontos) Escolha e demonstre duas, e apenas duas, das afirmações abaixo. Marque com "
" as opções escolhidas.
( )
é enumerável, mas
não é enumerável.
( ) Seja
o conjunto de todas as sequências infinitas formadas com os símbolos 0 e 1, por exemplo
. Noutras palavras,
é o conjunto das funções
. Mostrar que
é não enumerável.
( )
é infinito.
( )
( ) Seja
( )
Passo 1
O enunciado pede que escolhamos e demonstremos exatamente duas das três afirmações sobre tamanho de conjuntos (enumerabilidade e infinitude). Vou marcar e demonstrar:
(X) é enumerável, mas
não é enumerável.
(X) Seja o conjunto de todas as sequências infinitas em
. Mostrar que
é não enumerável.
(X)
(X) Seja
Passo 2
Definição de enumerável: um conjunto
é enumerável se existe bijeção
.
(i) Mostramos que é enumerável construindo uma enumeração explícita. Cada racional não negativo pode ser escrito em forma irredutível
com
. Organize todos os pares
numa grade infinita e percorra em diagonais (método de Calkin–Wilf ou Cantor), pulando repetições. Isso define uma enumeração bijetora de
em
. Analogamente enumera-se
. Concatene as duas listas, obtendo
(i) Mostramos que
Logo
é enumerável.
Passo 3
(ii) Agora, sabemos que
é não enumerável por diagonal de Cantor. Como
é enumerável,
seria união de dois conjuntos enumeráveis se
fosse enumerável. Mas união de dois enumeráveis é enumerável, o que contradiz o fato de
ser não enumerável. Portanto
não pode ser enumerável.
Passo 4
(iii) Para
, suponha, por contradição, que existe enumeração
Cada
é uma sequência
Construa então a sequência
definindo para todo
:
Por construção,
difere de
na coordenada
, logo
não aparece em nenhuma posição da enumeração. Contradição à suposição de enumeração completa. Assim
é não enumerável.
Resposta
(X)
é enumerável, mas
não é enumerável.
(X) é não enumerável.
( ) é infinito.
(X)
( )