Prove que, se f: A \rightarrow B é uma função sobrejetiva e A é enumerável, então B é também enumerável.
Dica: Seja f: A \rightarrow B uma função sobrejetiva. Então, existe uma função g: B \rightarrow A tal que f \circ g=I_{B}, onde I_{B} denota a função identidade de B em B. Em particular, g é injetiva. Depois use o corolário 1 do Teorema 4 do livro

Passo 1

O enunciado afirma que existe uma função sobrejetiva f\colon A\to B e que A é enumerável (isto é, ou finito ou equipolente a \mathbb{N}). Queremos mostrar que então B também é enumerável. Para isso usaremos o fato (Corolário 1 do Teorema 4) de que, se há uma injeção de um conjunto X em um conjunto enumerável Y, então X também é enumerável.

Passo 2

Como f\colon A\to B é sobrejetiva, podemos escolher para cada b\in B algum a\in A tal que f(a)=b. Essa escolha define uma função
g\colon B\to A
tal que
f\circ g = I_{B}.
Tomando b_{1},b_{2}\in B e supondo g(b_{1})=g(b_{2}), aplicamos f dos dois lados e obtemos
b_{1} = f\bigl(g(b_{1})\bigr) = f\bigl(g(b_{2})\bigr) = b_{2}.
Logo g é injetiva.

Passo 3

Agora temos uma função injetiva g\colon B\hookrightarrow A e sabemos que A é enumerável. Pelo corolário citado, qualquer conjunto que injeta em um enumerável também é enumerável. Portanto B é enumerável.

Resposta

B é enumerável.

Exercícios relacionados