If A is a denumerable set, and there exists a surjective function from A to B, then B is denumerable

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.


There is a surjective function $f \colon \mathbb{N} \to A$, and another one $g \colon A \to B$. Then the composition $g \circ f \colon \mathbb{N} \to B$ is also surjective, and so $B$ is denumerable.


You are definitely on the right track here. However, what you have failed to consider for this proof to be complete is what to do with the elements of $B$ mapped to by several elements of $A$.

As an example, let's call the surjective function $f$, and let's say $f(a_1) = f(a_2) = f(a_3)$. Then your $b_1, b_2$ and $b_3$ will be the same element, and what you have is not really an indexing of $B$.

To counteract this, set $b_1 = f(a_1)$, then for each new index $i$ you can say that $b_i$ is $f(a_j)$ where $j$ is the lowest index such that $f(a_i)\in B$ has not yet been assigned an index.

Now to show that you have indexes on all elements of $B$, take any one of them (let's say the element $b$). This is mapped to by $f$, so the set $f^{-1}(\{b\})$ is non-empty. Thus there has to be a lowest index $k$ such that $f(a_k) = b$. By the method of giving elements of $B$ indices, by the time you got to $k$, you must have given an index to $b$. And there you go, $b$ has an index.

Of course, indexing of the set $B$ is really just a bijection with (possibly a finite subset of) $\Bbb N$, which is what denumerability is all about.