# 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: \$\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.