Resolva os seguintes itens:
(a) Defina o que é um conjunto X ser enumerável;
(b) Mostre que o produto cartesiano de dois conjuntos enumeráveis também é enumerável;
(c) Mostre que Q é enumerável;
(d) Assumindo como fato conhecido que R não seja enumerável, use um argumento simples para explicar por que os números \mathbb{R} reais não têm como ser construídos usando uma construção do tipo \mathbb{R}=Q \times Q / \approx como foi feito para \mathbb{Z}=\mathbb{N} \times \mathbb{N} / \sim e para \mathbb{Q}=\mathbb{Z} \times \mathbb{Z} / \approx.

Passo 1

O enunciado pede quatro coisas separadas; vou listar claramente o que cada item solicita e quais informações relevantes são dadas:
(a) Definir o que significa um conjunto X ser enumerável.
(b) Mostrar que o produto cartesiano de dois conjuntos enumeráveis também é enumerável.
(c) Mostrar que \mathbb{Q} é enumerável.
(d) Partindo do fato conhecido (assumido) de que \mathbb{R} não é enumerável, dar um argumento simples explicando por que não se pode obter \mathbb{R} a partir de uma construção do tipo \mathbb{R}=\mathbb{Q}\times\mathbb{Q}/\approx análoga às construções \mathbb{Z}=\mathbb{N}\times\mathbb{N}/\sim e \mathbb{Q}=\mathbb{Z}\times\mathbb{Z}/\approx.
Informações/hipóteses úteis que o enunciado dá ou que vamos usar: existe a noção usual de \mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}; foi mencionado que \mathbb{R} não é enumerável (assumir como fato). Também aparecem exemplos de construções por produto cartesiano seguido de relação de equivalência para formar \mathbb{Z} e \mathbb{Q}; isso sugere comparar cardinalidades e usar propriedades de imagens de função/quotients.

Passo 2

Definição precisa (item (a)). Vou explicar com calma o que significa “enumerável” e dar exemplos simples.
Definição: direi que um conjunto X é enumerável quando ele é finito ou quando existe uma bijeção entre X e \mathbb{N}. Vou também mencionar a versão que muitos autores usam: às vezes “enumerável” significa “contável infinito” (ou seja, bijeção com \mathbb{N} especificamente). Aqui, para ficar abrangente e prático, usaremos a definição: X é enumerável se existe uma função bijetora
f: \mathbb{N}\to X
ou, alternativamente, se X é finito. Em palavras simples: dá para listar todos os elementos de X numa sequência x_0,x_1,x_2,\dots que atinge todo elemento de X (cada elemento aparece em alguma posição da lista).
Explicação didática do que isso quer dizer:
  • “Bijeção” significa que a lista não repete elementos (injeção) e também atinge todos eles (sobrecção).
  • Exemplos:
    • \mathbb{N} é enumerável (obviamente): a bijeção é a identidade.
    • \mathbb{Z} é enumerável: uma enumeração possível é 0,1,-1,2,-2,3,-3,\dots. Aqui eu mostro explicitamente uma lista que contém cada inteiro exatamente uma vez.
    • Qualquer conjunto finito (por exemplo, \{a,b,c\}) é enumerável porque você pode listar seus elementos em ordem finita.
Vou guardar esta definição para usá-la nos próximos itens. Se você preferir na prova usar a versão "enumerável = bijeção com \mathbb{N}" (excluindo conjuntos finitos), basta tratar o caso finito separadamente; os argumentos a seguir funcionam sem problemas em ambas as interpretações.

Passo 3

Mostrar que o produto cartesiano de dois conjuntos enumeráveis é enumerável (item (b)). Vou dar um método que dá uma enumeração concreta (prático para prova) e explicar por que funciona.
Hipótese: sejam A e B conjuntos enumeráveis. Pelo que definimos, existem enumerações
A=\{a_0,a_1,a_2,\dots\},\qquad B=\{b_0,b_1,b_2,\dots\}.
(Se algum dos conjuntos for finito, você pode completar a enumeração com elementos repetidos ou tratar o caso finito à parte; o argumento principal é para o caso infinito contável.)
Queremos listar todos os pares (a_i,b_j) de modo que cada par apareça exatamente uma vez numa sequência. A ideia clássica (diagonalização estilo Cantor) é listar os pares por soma do índice i+j. Vou construir explicitamente a sequência:
  1. Considere as “antidiagonais” indexadas por s=i+j. Para s=0 temos os pares (a_0,b_0). Para s=1 temos (a_0,b_1),(a_1,b_0). Para s=2 temos (a_0,b_2),(a_1,b_1),(a_2,b_0). E assim por diante.
  2. Para cada s fixe a ordem, por exemplo, percorrendo i=0,1,\dots,s e pegando (a_i,b_{s-i}). Agora concatene essas listas para s=0,1,2,\dots. Isso dá uma sequência
(a_0,b_0),\; (a_0,b_1),(a_1,b_0),\; (a_0,b_2),(a_1,b_1),(a_2,b_0),\;\dots
que contém cada par (a_i,b_j) em exatamente uma posição (quando s=i+j aparece, e dentro dessa antidiagonal escolhemos a ordem i=0,\dots,s).
Por que essa enumeração é bijetiva entre \mathbb{N} e A\times B?
  • Injetividade no sentido de “sem repetições”: cada par (a_i,b_j) aparece apenas quando consideramos a antidiagonal s=i+j; dentro dessa antidiagonal aparecem pares com índices diferentes, então não há repetição de mesma combinação de índices. Como a enumeração de A e B não repete elementos, isso garante que cada par distinto de A\times B aparece em posição única.
  • Sobrescrtividade (atinge todos): dado qualquer par (a_i,b_j), existe s=i+j e então esse par aparece na antidiagonal s, logo aparece na lista.
Conclusão: construímos uma enumeração de A\times B, logo A\times B é enumerável. Este procedimento é prático na prova: reduce-se ao caso em que cada conjunto tem enumeração por \mathbb{N} e então procede-se por antidiagonais.
Observação alternativa (fórmula explícita): existe também uma função bijetora conhecida \pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N} (função de pareamento de Cantor),
\pi(m,n)=\frac{(m+n)(m+n+1)}{2}+n,
que dá um número natural único para cada par (m,n). Se você prefere uma expressão fechada em provas, pode citar essa função; a prova de bijetividade é um cálculo mecânico. A construção por antidiagonais é mais intuitiva e suficiente.

Passo 4

Mostrar que \mathbb{Q} é enumerável (item (c)). Vou dividir em subpassos e dar uma enumeração concreta que você poderia usar numa prova.
Passo preliminar: \mathbb{Z} é enumerável. Uma enumeração explícita é
0,\,1,\,-1,\,2,\,-2,\,3,\,-3,\dots
formalmente pode-se definir z_0=0 e para n\ge 1
z_{2n-1}=n,\qquad z_{2n}=-n.
Isso é uma bijeção \mathbb{N}\to\mathbb{Z}. Assim \mathbb{Z} é enumerável.
Agora use o que acabamos de provar: \mathbb{Z}\times\mathbb{N} é enumerável, porque \mathbb{Z} e \mathbb{N} são enumeráveis (aplicar o item (b)). Considere a função
\varphi:\mathbb{Z}\times\mathbb{N}_{>0}\to\mathbb{Q},\qquad \varphi(p,q)=\frac{p}{q},
onde \mathbb{N}_{>0}=\{1,2,3,\dots\} (usamos denominadores positivos para evitar sinal duplicado por q). Essa função é sobrajetora: para qualquer racional r\in\mathbb{Q} existes p\in\mathbb{Z}, q\in\mathbb{N}_{>0} tais que r=p/q. Assim \mathbb{Q} é imagem de um conjunto enumerável por uma função sobrejetiva.
Propriedade usada (fato importante e simples): imagem de um conjunto enumerável por uma função sobrejetiva é enumerável (ou ao menos “no máximo enumerável”). Raciocínio rápido: se S é enumerável e f:S\to T é sobrejetora, então enumerando S e aplicando f obtemos uma lista que contém todos elementos de T (talvez com repetições); remover repetições dá uma enumeração de T (porque se T for infinito a remoção de repetições deixa uma sequência infinita enumerando tudo; se for finito também ok).
Portanto \mathbb{Q} é enumerável.
Se quiser uma enumeração explícita sem falar só em sobrejeção: comece com a enumeração de \mathbb{Z}\times\mathbb{N}_{>0} por antidiagonais, aplique \varphi a cada par e, ao listar, ignore repetições (ou sempre escrever a fração na forma reduzida e só aceitar a primeira vez que aparece). Assim você obtém uma lista explícita de todos os números racionais sem repetir nenhum, por exemplo:
0,\,1,-1,\,\tfrac12,\,2,-2,\,\tfrac13,\,\tfrac32,-\tfrac12,\dots
(esta é só ilustrativa; a ordem exata depende de escolhas, o importante é que existe uma).
Resumo: concluímos que \mathbb{Q} é enumerável.

Passo 5

Explicação por que não se pode construir \mathbb{R} como \mathbb{Q}\times\mathbb{Q}/\approx (item (d)). Vou usar um argumento de cardinalidade simples e direto, bem apropriado para prova.
Fatos já estabelecidos/assumidos:
  • \mathbb{Q} é enumerável (Passo 4).
  • O produto \mathbb{Q}\times\mathbb{Q} é, portanto, enumerável (Passo 3).
  • Uma relação de equivalência \approx em \mathbb{Q}\times\mathbb{Q} define um conjunto quociente (\mathbb{Q}\times\mathbb{Q})/\!\approx cujos elementos são as classes de equivalência. Existe uma função natural de projeção
\pi:\mathbb{Q}\times\mathbb{Q}\to (\mathbb{Q}\times\mathbb{Q})/\!\approx,
que é sobrejetora (cada classe tem pelo menos um representante).
Observação-chave: imagem (ou quociente) de um conjunto enumerável por uma função sobrejetora é enumerável. Em particular, o conjunto de classes de equivalência (\mathbb{Q}\times\mathbb{Q})/\!\approx será, no máximo, enumerável.
Conclusão pelo absurdo simples: se fosse possível encontrar uma relação \approx tal que
\mathbb{R}\cong (\mathbb{Q}\times\mathbb{Q})/\!\approx,
então \mathbb{R} seria enumerável (porque \mathbb{Q}\times\mathbb{Q} é enumerável e o quociente por equivalência tem no máximo essa cardinalidade). Mas isso contradiz o fato conhecido de que \mathbb{R} não é enumerável. Portanto não existe tal relação \approx capaz de representar \mathbb{R} como quociente de \mathbb{Q}\times\mathbb{Q}.
Intuição curta para gravar: \mathbb{Q}\times\mathbb{Q} tem “tamanho” contável; formar classes de equivalência não pode aumentar esse tamanho para algo incontável. Como \mathbb{R} é incontável, ela não cabe como conjunto de classes vindas de \mathbb{Q}\times\mathbb{Q}.

Resposta

(a) Um conjunto X é enumerável se é finito ou se existe uma bijeção \mathbb{N}\to X (isto é, se seus elementos podem ser listados numa sequência x_0,x_1,x_2,\dots que atinge todo elemento de X).
(b) Se A e B são enumeráveis, escreva A=\{a_0,a_1,\dots\} e B=\{b_0,b_1,\dots\}. Liste os pares (a_i,b_j) por antidiagonais (pela soma i+j); essa sequência contém cada par exatamente uma vez, logo A\times B é enumerável.
(c) \mathbb{Z} é enumerável (ex.: 0,1,-1,2,-2,\dots); então \mathbb{Z}\times\mathbb{N}_{>0} é enumerável; a função \varphi(p,q)=p/q é sobrejetora em \mathbb{Q}, portanto \mathbb{Q} é imagem de um conjunto enumerável e assim \mathbb{Q} é enumerável.
(d) \mathbb{Q}\times\mathbb{Q} é enumerável; qualquer quociente por relação de equivalência (\mathbb{Q}\times\mathbb{Q})/\!\approx tem no máximo cardinalidade enumerável (projeção sobrejetora). Como \mathbb{R} é não enumerável, não pode haver relação \approx em \mathbb{Q}\times\mathbb{Q} tal que \mathbb{R}\cong(\mathbb{Q}\times\mathbb{Q})/\!\approx.

Exercícios relacionados