Surjection allowing a countable set to imply another countable set.

Question

So, I have two sets A and B and there is a surjection from A to B. Given this surjection, I have to show that

A is countable implies B is countable.

Any help would be appreciated

Answer 1

Hint: $A$ is countable by definition means that either there is an injection from $A$ into $\mathbb{N}$ or there is a surjection from $\mathbb{N}$ onto $A$. Assume there is a surjection $g$ from $\mathbb{N}$ onto $A$. Then compose the surjection $g$ with the surjection $f$ from $A$ to $B$ to get a surjection from $\mathbb{N}$ to $B$. Can you see why this would imply that $B$ is countable?

Also note that the main set-theoretic argument you need to invoke here is that the composition of surjective functions is again surjective, try and prove this if you're not familiar witht his result.

Answer 2

Since $A$ is countable, we can write $A$ as a sequence $a_1,a_2,\dots$ Consider the sequence $f(a_1),f(a_2),\dots$ where $f$ is the surjection. This sequence contains all of $B$ but there may be repeats. Define a new sequence $b_n$ which starts with $b_1=f(a_1)$ but skips $f(a_i)$ whenever $f(a_i)$ was already included in $b_1,\dots,b_{i-1}$. The sequence $b_n$ now contains all of $B$ without repeats. Hence, $B$ can be enumerated as a sequence and is countable.