# Thread: Proving countability from surjectivity

1. ## Proving countability from surjectivity

let f: S --> T be a surjective function
if S is countable, prove that T is countable

I see that f(S) = T, but and I know that there is a surjection from the natural numbers to S, and an injection from S to N, but I'm not really sure where to head to show that T is countable...Please help

2. Originally Posted by blackmustachio
let f: S --> T be a surjective function
if S is countable, prove that T is countable.
Though this answer is a bit late, it may help someone.
This is a well known theorem: $\displaystyle F:A \mapsto B$ is injective if and only if there is a surjection $\displaystyle G:B \mapsto A$.
Because you are given that $\displaystyle f:S \mapsto T$ is a surjection then by the theorem there is an injection $\displaystyle h:T \mapsto S$.
Also because S is countable then there in an injection $\displaystyle g:S \mapsto Z^ +$.
Hence $\displaystyle g \circ h:T \mapsto Z^ +$ is an injection, proving that T is countable.