Questão 37 Seja f: X \rightarrow Y uma aplicação tal que, dado qualquer y \in Y, seja finito ou infinito enumerável, a imagem inversa de y por f, isto é,
f^{-1}(y)=\{x \in X ; f(x)=y\}
Mostre que, se Y for enumerável, então X será finito ou enumerável.

Passo 1

O enunciado dá uma aplicação f: X \to Y e as seguintes informações:
  • Para todo y\in Y, a pré-imagem f^{-1}(y)=\{x\in X;\\ f(x)=y\} é ou finita ou enumerável (isto é, finita ou numerável infinito).
  • Sabe-se que Y é enumerável (ou seja, finito ou numerável infinito).
O que o problema pede:
  • Mostrar que, sob essas hipóteses, X também é finito ou enumerável.
Resumo das informações úteis (retiradas do enunciado):
  • Para todo y\in Y, f^{-1}(y) é finito ou enumerável.
  • Y é enumerável.
  • Objetivo: provar que X é 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 \mathbb{N} sobre o conjunto (equivalente a dizer que o conjunto é finito ou equiparável a \mathbb{N}). 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 f:
  • As pré-imagens pelo f de elementos diferentes de Y são disjuntas: se y_1\neq y_2 então f^{-1}(y_1)\cap f^{-1}(y_2)=\varnothing. Isso é óbvio porque cada x\in X tem uma única imagem f(x).
  • Logo podemos escrever
X=\bigcup_{y\in Y} f^{-1}(y),
uma união disjunta (ou pelo menos uma união em que os conjuntos não se sobrepõem) dos conjuntos f^{-1}(y).

Passo 4

Tratei dois casos para Y.
Caso A: Y é finito.
  • Se Y tem k elementos, então X é a união de k conjuntos, cada um finito ou enumerável.
  • Como união finita de conjuntos enumeráveis é enumerável, então X é enumerável (ou talvez finito, que também está coberto por “enumerável” aqui).
  • Assim, no caso Y finito, a conclusão é imediata: X é finito ou enumerável.
Caso B: Y é enumerável infinito.
  • Podemos enumerar os elementos de Y como uma sequência \{y_1,y_2,y_3,\dots\}.
  • Para cada n\in\mathbb{N} defina A_n := f^{-1}(y_n). Pelas hipóteses, cada A_n é finito ou enumerável.
  • Como observado, os A_n são disjuntos e
X=\bigcup_{n=1}^{\infty} A_n.

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 n, como A_n é finito ou enumerável, existe uma enumeração (possivelmente finita) dos seus elementos. Escreva essa enumeração como
A_n=\{x_{n,1},x_{n,2},x_{n,3},\dots\},
onde, se A_n for finito, a sequência termina (ou seja, só existem índices m até um certo limite), e se for infinita há elementos para todo m\in\mathbb{N}.
  • Considere a grade de pares de índices (n,m) com n,m\in\mathbb{N}. Podemos percorrer todos esses pares com a ordenação em diagonais, por exemplo na ordem
(1,1),\\ (1,2),(2,1),\\ (1,3),(2,2),(3,1),\\ (1,4),(2,3),(3,2),(4,1),\dots
  • Para cada par (n,m) na ordem acima, se x_{n,m} existe (isto é, se o m-ésimo elemento de A_n existe) então lista-se esse elemento. Como os conjuntos A_n são disjuntos, não haverá repetições ao listar assim.
  • Todo elemento x\in X pertence a algum A_n, e se x\in A_n então é o m-ésimo elemento de A_n para algum m. Portanto esse par (n,m) aparece em alguma etapa do percurso em diagonais, e assim x será listado em algum momento.
  • Assim construímos uma enumeração de X (talvez finita, talvez infinita), provando que X é enumerável.
Observação alternativa (mais formal): existe uma bijeção conhecida entre \mathbb{N}\times\mathbb{N} e \mathbb{N} (por exemplo a função de Cantor ou a enumeração por diagonais), e como cada A_n pode ser indexado por \{n\}\times\mathbb{N} a união corresponde a uma imagem de um subconjunto de \mathbb{N}\times\mathbb{N}, portanto é enumerável.

Passo 6

Conclusão final das duas situações:
  • Se Y for finito, X é união finita de conjuntos finitos/contáveis, logo X é finito ou enumerável.
  • Se Y for enumerável infinito, escrevendo X=\bigcup_{n=1}^{\infty} A_n com cada A_n finito ou enumerável, usamos a enumeração em diagonais para listar todos os elementos de X e concluímos que X é enumerável.
Portanto, em todo caso, sob as hipóteses do enunciado, X é finito ou enumerável.

Resposta

X é finito ou enumerável.

Exercícios relacionados