# Proving countability from surjectivity

• Sep 20th 2007, 06:32 PM
blackmustachio
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
• Sep 21st 2007, 01:28 PM
Plato
Quote:

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: $F:A \mapsto B$ is injective if and only if there is a surjection $G:B \mapsto A$.
Because you are given that $f:S \mapsto T$ is a surjection then by the theorem there is an injection $h:T \mapsto S$.
Also because S is countable then there in an injection $g:S \mapsto Z^ +$.
Hence $g \circ h:T \mapsto Z^ +$ is an injection, proving that T is countable.