I am having some trouble solving the following homework question and some help would be greatly appreciated!!
Q: Prove that if $A$ is a denumerable set, and there exists a surjective function from $A$ to $B$, then $B$ is denumerable.
My intuition:
Since $A$ is denumerable, we can write $A$ as ${a1,a2,a3…}$. Furthermore, since there is a surjective function from $A$ to $B$, then every element of $B$ is mapped to an element of $A$. Thus, it makes sense to say that since $A$ is denumerable and every element of $B$ is being mapped to $A$, then $B$ is denumerable. Thus, we can write $B$ as ${b1,b2,b3…}$.
This seems logical however I feel as though it is not a complete and mathematical proof. Help would be greatly appreciated to make this informal reasoning more in line with what mathematicians expect!
Thank you š
Best Answer
The case $A=\emptyset $ is trivial, so we may dispose of it. Based on the formulation of what you are trying to prove, it seems the meaning of denumerable for you is that of a set that is either finite or has the same cardinality as $\mathbb N$. So, prove first that a set $S\ne \emptyset $ is denumerable if, and only if, there exists a surjection $f:\mathbb N \to S$.
Now, if $g:A\to B$ is surjective and $A$ is denumerable, then there exists a surjection $f:\mathbb N \to A$. The composition of surjective functions is surjective, thus $g\circ f:\mathbb N \to B$ is a surjection, so $B$ is denumerable.