Função injetora/sobrejetora e conjuntos enumeráveis
Seja $f:A\rightarrow B$ uma função. Mostre que
a) Se $f$ é injetora e $B$ é enumerável, então $A$ é enumerável.
b) Se $f$ é sobrejetora e $A$ é enumerável, então $B$ é enumerável.
1 answer
a) Como $B$ é enumerável, existe uma função $\phi :B \rightarrow \mathbb{N}$ que é bijetora. Agora, como $f$ é injetora, para cada $a \in A$, existe um único $b \in B$ tal que $f(a) = b$. Ou seja, ao tomarmos uma função $g$ como $g = \phi \circ f$, com $g:A\rightarrow \mathbb{N}$ é uma função injetora.
Isto é, a imagem de A na função $g$ é um subconjunto de $\mathbb{N}$, que é enumerável (todo subconjunto dos naturais é enumerável). Veja que $\left. g \right|_{A}:A \rightarrow g(A)$ é bijeção e tome $h: g(A) \rightarrow \mathbb{N}$ bijeção também.
Por fim, tome $j = h \circ \left. g \right|_{A}$. Como $j$ é a composição de bijeções, temos que $j: A \rightarrow \mathbb{N}$ é bijeção e, portanto, A é enumerável.
b) Como $f$ é sobrejetiva, para cada $b\in B$ podemos escolher um $a = g(b) \in A$. Dessa forma, criamos uma função $g: B \rightarrow A$ tal que $f(g(b))=b)$ para todo $b \in B$. Isto é, $g$ deve ser injetiva.
Pelo item anterior, sai que B é enumerável.
0 comment thread