Questão 44 Suponha que f: A \rightarrow B seja uma função, onde A é um conjunto nãoenumerável e B seja enumerável. Mostre que existe b \in B tal que f^{-1}(b) seja um conjunto não-enumerável.

Passo 1

O que o enunciado dá e o que pede.
  • Dado: uma função f: A \to B.
  • Dado: A é um conjunto não-enumerável (ou seja, não é contável).
  • Dado: B é enumerável (ou seja, é finito ou contável infinito).
  • Definição útil que vem no enunciado (vou usá-la): para b\in B, a pré-imagem f^{-1}(b) é o conjunto \{a\in A \mid f(a)=b\}.
  • Pedido: mostrar que existe b\in B tal que f^{-1}(b) seja não-enumerável.

Passo 2

Explicar e fixar claramente o significado de “enumerável” e uma propriedade-chave que usarei.
  • Vou entender “enumerável” como sinônimo de “contável” (ou seja, finito ou equipotente a \mathbb{N}).
  • Uma propriedade fundamental que vou usar e que preciso justificar é:
\text{União contável de conjuntos contáveis é contável.}ãááéá
Isto é: se (C_n)_{n\in\mathbb{N}} é uma sequência de conjuntos, cada C_n contável, então \bigcup_{n\in\mathbb{N}} C_n é contável.
Vou agora explicar por que essa propriedade é verdadeira (a prova é uma ferramenta padrão e muito útil em provas deste tipo).

Passo 3

Prova (intuitiva e construtiva) de que a união contável de conjuntos contáveis é contável.
  • Como cada C_n é contável, existe uma enumeração (possivelmente finita) para cada um. Isto é, para todo n podemos escrever uma lista (com possíveis repetições) \;C_n=\{c_{n,1},c_{n,2},c_{n,3},\dots\}, onde a lista pode ser finita (então só alguns c_{n,k} existem) ou infinita.
  • Agora pense nas pares (n,k) com n,k\in\mathbb{N}. Os pares (n,k) são contáveis (há uma enumeração padrão dos pares, por exemplo pela enumeração diagonal de Cantor). Assim existe uma bijeção ou enumeração \varphi:\mathbb{N}\to\mathbb{N}\times\mathbb{N} que percorre todos os pares.
  • Compose essa enumeração com as listagens dos elementos: para m\in\mathbb{N} escreva \varphi(m)=(n_m,k_m) e considere o termo c_{n_m,k_m}. Assim obtemos uma sequência que contém todos os elementos de \bigcup_{n} C_n, possivelmente com repetição.
  • Retirando repetições (ignorando já vistos quando aparecem de novo) obtemos uma enumeração sem repetições de \bigcup_{n} C_n. Isso mostra que \bigcup_{n} C_n é, no máximo, contável.
  • Conclusão: a união contável de conjuntos contáveis é contável.
(Dica prática: na prova é suficiente referir esta propriedade e, se pedirem, esboçar a enumeração diagonal ou o argumento de composição acima.)

Passo 4

Argumento por contradição aplicado ao enunciado.
  • Suponha, visando Contradição, que para todo b\in B a pré-imagem f^{-1}(b) seja enumerável (contável).
  • Como B é enumerável, existe uma enumeração B=\{b_1,b_2,b_3,\dots\} (se B for finito, a sequência termina, mas o argumento abaixo também vale).
  • Observe que todo elemento de A pertence à pré-imagem de algum elemento de B; em símbolos:
A=\bigcup_{b\in B} f^{-1}(b)=\bigcup_{n=1}^{\infty} f^{-1}(b_n).
  • Pela hipótese de contradição, cada conjunto f^{-1}(b_n) é contável. Logo A é união contável de conjuntos contáveis, e pelo resultado do Passo 3 conclui-se que A é contável (enumerável).
  • Isso contraria a hipótese do enunciado de que A é não-enumerável.
  • Portanto a suposição de que todas as pré-imagens f^{-1}(b) fossem contáveis é falsa.

Passo 5

Conclusão final e intuição.
  • Conclui-se que existe pelo menos um b\in B tal que f^{-1}(b) não é enumerável.
  • Intuição: a função f “particiona” A em fibras \{f^{-1}(b):b\in B\}. Se todas essas fibras fossem pequenas (contáveis) e há apenas contavelmente muitas fibras, então a união seria contável — impossível porque A é grande (não-contável). Logo alguma fibra tem que ser grande (não-contável).

Resposta

Existe b\in B tal que f^{-1}(b) é não-enumerável.

Exercícios relacionados