Questão 1: (3.0 pontos) Escolha e demonstre duas, e apenas duas, das afirmações abaixo. Marque com " X " as opções escolhidas.
( ) \mathbb{Q} é enumerável, mas \mathbb{R} \backslash \mathbb{Q} não é enumerável.
( ) Seja S o conjunto de todas as sequências infinitas formadas com os símbolos 0 e 1, por exemplo \xi=(0,1,1,0,0,0,1,0, \ldots) \in S. Noutras palavras, S é o conjunto das funções s: \mathbb{N} \rightarrow\{0,1\}. Mostrar que S é não enumerável.
( ) \mathbb{Z} é infinito.

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) \mathbb{Q} é enumerável, mas \mathbb{R}\setminus\mathbb{Q} não é enumerável.
(X) Seja S o conjunto de todas as sequências infinitas em \{0,1\}. Mostrar que S é não enumerável.

Passo 2

Definição de enumerável: um conjunto A é enumerável se existe bijeção f\colon\mathbb{N}\to A.
(i) Mostramos que \mathbb{Q} é enumerável construindo uma enumeração explícita. Cada racional não negativo pode ser escrito em forma irredutível \tfrac{p}{q} com p,q\in\mathbb{N}. Organize todos os pares (p,q) numa grade infinita e percorra em diagonais (método de Calkin–Wilf ou Cantor), pulando repetições. Isso define uma enumeração bijetora de \mathbb{N} em \mathbb{Q}_{\ge0}. Analogamente enumera-se \mathbb{Q}_{<0}. Concatene as duas listas, obtendo
\mathbb{N}\;\longleftrightarrow\;\mathbb{Q}.
Logo \mathbb{Q} é enumerável.

Passo 3

(ii) Agora, sabemos que \mathbb{R} é não enumerável por diagonal de Cantor. Como \mathbb{Q} é enumerável, \mathbb{R} \;=\;\mathbb{Q}\;\cup\;(\mathbb{R}\setminus\mathbb{Q}) seria união de dois conjuntos enumeráveis se \mathbb{R}\setminus\mathbb{Q} fosse enumerável. Mas união de dois enumeráveis é enumerável, o que contradiz o fato de \mathbb{R} ser não enumerável. Portanto \mathbb{R}\setminus\mathbb{Q} não pode ser enumerável.

Passo 4

(iii) Para S=\{\,s\colon\mathbb{N}\to\{0,1\}\}, suponha, por contradição, que existe enumeração
s^{(1)},s^{(2)},s^{(3)},\dots\in S.
Cada s^{(n)} é uma sequência
s^{(n)} = \bigl(s^{(n)}(1),\,s^{(n)}(2),\,s^{(n)}(3),\dots\bigr).
Construa então a sequência \sigma\in S definindo para todo n\in\mathbb{N}:
\sigma(n) \;=\; 1 - s^{(n)}(n).
Por construção, \sigma difere de s^{(n)} na coordenada n, logo \sigma não aparece em nenhuma posição da enumeração. Contradição à suposição de enumeração completa. Assim S é não enumerável.

Resposta

(X) \mathbb{Q} é enumerável, mas \mathbb{R}\setminus\mathbb{Q} não é enumerável.
(X) S é não enumerável.
( ) \mathbb{Z} é infinito.

Exercícios relacionados