Resolva os seguintes itens:
(a) Defina o que é um conjunto
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
reais não têm como ser construídos usando uma construção do tipo
como foi feito para
e para
.
(a) Defina o que é um conjunto
(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
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
ser enumerável.
(b) Mostrar que o produto cartesiano de dois conjuntos enumeráveis também é enumerável.
(c) Mostrar que é enumerável.
(d) Partindo do fato conhecido (assumido) de que não é enumerável, dar um argumento simples explicando por que não se pode obter
a partir de uma construção do tipo
análoga às construções
e
.
(b) Mostrar que o produto cartesiano de dois conjuntos enumeráveis também é enumerável.
(c) Mostrar que
(d) Partindo do fato conhecido (assumido) de que
Informações/hipóteses úteis que o enunciado dá ou que vamos usar: existe a noção usual de
,
,
,
; foi mencionado que
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
e
; 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
é enumerável quando ele é finito ou quando existe uma bijeção entre
e
. Vou também mencionar a versão que muitos autores usam: às vezes “enumerável” significa “contável infinito” (ou seja, bijeção com
especificamente). Aqui, para ficar abrangente e prático, usaremos a definição:
é enumerável se existe uma função bijetora
ou, alternativamente, se
é finito. Em palavras simples: dá para listar todos os elementos de
numa sequência
que atinge todo elemento de
(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:
-
é enumerável (obviamente): a bijeção é a identidade. -
é enumerável: uma enumeração possível é . Aqui eu mostro explicitamente uma lista que contém cada inteiro exatamente uma vez. - Qualquer conjunto finito (por exemplo,
) é 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
" (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
e
conjuntos enumeráveis. Pelo que definimos, existem enumerações
(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
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
. Vou construir explicitamente a sequência:
-
Considere as “antidiagonais” indexadas por
. Para temos os pares . Para temos . Para temos . E assim por diante. -
Para cada
fixe a ordem, por exemplo, percorrendo e pegando . Agora concatene essas listas para . Isso dá uma sequência
que contém cada par
em exatamente uma posição (quando
aparece, e dentro dessa antidiagonal escolhemos a ordem
).
Por que essa enumeração é bijetiva entre
e
?
- Injetividade no sentido de “sem repetições”: cada par
aparece apenas quando consideramos a antidiagonal ; 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 e não repete elementos, isso garante que cada par distinto de aparece em posição única. - Sobrescrtividade (atinge todos): dado qualquer par
, existe e então esse par aparece na antidiagonal , logo aparece na lista.
Conclusão: construímos uma enumeração de
, logo
é enumerável. Este procedimento é prático na prova: reduce-se ao caso em que cada conjunto tem enumeração por
e então procede-se por antidiagonais.
Observação alternativa (fórmula explícita): existe também uma função bijetora conhecida
(função de pareamento de Cantor),
que dá um número natural único para cada par
. 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
é enumerável (item (c)). Vou dividir em subpassos e dar uma enumeração concreta que você poderia usar numa prova.
Passo preliminar:
é enumerável. Uma enumeração explícita é
formalmente pode-se definir
e para
Isso é uma bijeção
. Assim
é enumerável.
Agora use o que acabamos de provar:
é enumerável, porque
e
são enumeráveis (aplicar o item (b)). Considere a função
onde
(usamos denominadores positivos para evitar sinal duplicado por
). Essa função é sobrajetora: para qualquer racional
existes
,
tais que
. Assim
é 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
é enumerável e
é sobrejetora, então enumerando
e aplicando
obtemos uma lista que contém todos elementos de
(talvez com repetições); remover repetições dá uma enumeração de
(porque se
for infinito a remoção de repetições deixa uma sequência infinita enumerando tudo; se for finito também ok).
Portanto
é enumerável.
Se quiser uma enumeração explícita sem falar só em sobrejeção: comece com a enumeração de
por antidiagonais, aplique
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:
(esta é só ilustrativa; a ordem exata depende de escolhas, o importante é que existe uma).
Resumo: concluímos que
é enumerável.
Passo 5
Explicação por que não se pode construir
como
(item (d)). Vou usar um argumento de cardinalidade simples e direto, bem apropriado para prova.
Fatos já estabelecidos/assumidos:
-
é enumerável (Passo 4). - O produto
é, portanto, enumerável (Passo 3). - Uma relação de equivalência
em define um conjunto quociente cujos elementos são as classes de equivalência. Existe uma função natural de projeção
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
será, no máximo, enumerável.
Conclusão pelo absurdo simples: se fosse possível encontrar uma relação
tal que
então
seria enumerável (porque
é enumerável e o quociente por equivalência tem no máximo essa cardinalidade). Mas isso contradiz o fato conhecido de que
não é enumerável. Portanto não existe tal relação
capaz de representar
como quociente de
.
Intuição curta para gravar:
tem “tamanho” contável; formar classes de equivalência não pode aumentar esse tamanho para algo incontável. Como
é incontável, ela não cabe como conjunto de classes vindas de
.
Resposta
(a) Um conjunto
é enumerável se é finito ou se existe uma bijeção
(isto é, se seus elementos podem ser listados numa sequência
que atinge todo elemento de
).
(b) Se e
são enumeráveis, escreva
e
. Liste os pares
por antidiagonais (pela soma
); essa sequência contém cada par exatamente uma vez, logo
é enumerável.
(c) é enumerável (ex.:
); então
é enumerável; a função
é sobrejetora em
, portanto
é imagem de um conjunto enumerável e assim
é enumerável.
(d) é enumerável; qualquer quociente por relação de equivalência
tem no máximo cardinalidade enumerável (projeção sobrejetora). Como
é não enumerável, não pode haver relação
em
tal que
.
(b) Se
(c)
(d)