Questão 37 Seja
uma aplicação tal que, dado qualquer
, seja finito ou infinito enumerável, a imagem inversa de y por
, isto é,
Mostre que, se
for enumerável, então
será finito ou enumerável.
Passo 1
O enunciado dá uma aplicação
e as seguintes informações:
- Para todo
, a pré-imagem é ou finita ou enumerável (isto é, finita ou numerável infinito). - Sabe-se que
é enumerável (ou seja, finito ou numerável infinito).
O que o problema pede:
- Mostrar que, sob essas hipóteses,
também é finito ou enumerável.
Resumo das informações úteis (retiradas do enunciado):
- Para todo
, é finito ou enumerável. -
é enumerável. - Objetivo: provar que
é finito ou enumerável.
Passo 2
Primeiro, vou lembrar o significado de “enumerável” que usaremos aqui, de forma bem prática e sem jargão:
- Dizer que um conjunto é enumerável significa que ele é finito ou que existe uma enumeração por índices naturais, isto é, existe uma função sobrejetora do conjunto dos naturais
sobre o conjunto (equivalente a dizer que o conjunto é finito ou equiparável a ). Vou chamá-lo informalmente de “contável”. - Propriedade importante que vamos usar: uma união finita de conjuntos contáveis é contável. Também usaremos que uma união contável (enumerável) de conjuntos contáveis é contável; mostrarei isso construtivamente.
Passo 3
Observação estrutural sobre a função
:
- As pré-imagens pelo
de elementos diferentes de são disjuntas: se então . Isso é óbvio porque cada tem uma única imagem . - Logo podemos escrever
uma união disjunta (ou pelo menos uma união em que os conjuntos não se sobrepõem) dos conjuntos
.
Passo 4
Tratei dois casos para
.
Caso A:
é finito.
- Se
tem elementos, então é a união de conjuntos, cada um finito ou enumerável. - Como união finita de conjuntos enumeráveis é enumerável, então
é enumerável (ou talvez finito, que também está coberto por “enumerável” aqui). - Assim, no caso
finito, a conclusão é imediata: é finito ou enumerável.
Caso B:
é enumerável infinito.
- Podemos enumerar os elementos de
como uma sequência . - Para cada
defina . Pelas hipóteses, cada é finito ou enumerável. - Como observado, os
são disjuntos e
Passo 5
Agora provamos que a união contável de conjuntos contáveis é contável, de modo construtivo e intuitivo (essa é a ideia usada para o caso B).
Descrição construtiva:
- Para cada
, como é finito ou enumerável, existe uma enumeração (possivelmente finita) dos seus elementos. Escreva essa enumeração como
onde, se
for finito, a sequência termina (ou seja, só existem índices
até um certo limite), e se for infinita há elementos para todo
.
- Considere a grade de pares de índices
com . Podemos percorrer todos esses pares com a ordenação em diagonais, por exemplo na ordem
- Para cada par
na ordem acima, se existe (isto é, se o -ésimo elemento de existe) então lista-se esse elemento. Como os conjuntos são disjuntos, não haverá repetições ao listar assim. - Todo elemento
pertence a algum , e se então é o -ésimo elemento de para algum . Portanto esse par aparece em alguma etapa do percurso em diagonais, e assim será listado em algum momento. - Assim construímos uma enumeração de
(talvez finita, talvez infinita), provando que é enumerável.
Observação alternativa (mais formal): existe uma bijeção conhecida entre
e
(por exemplo a função de Cantor ou a enumeração por diagonais), e como cada
pode ser indexado por
a união corresponde a uma imagem de um subconjunto de
, portanto é enumerável.
Passo 6
Conclusão final das duas situações:
- Se
for finito, é união finita de conjuntos finitos/contáveis, logo é finito ou enumerável. - Se
for enumerável infinito, escrevendo com cada finito ou enumerável, usamos a enumeração em diagonais para listar todos os elementos de e concluímos que é enumerável.
Portanto, em todo caso, sob as hipóteses do enunciado,
é finito ou enumerável.