Let $A,B,$ and $C$ be sets such that there is no surjection from $A$ to $B,$ and there is no surjection from $B$ to $C.$ Show that there is no surjection from $A$ to $C.$
When $A,B,$ and $C$ are finite sets, it's quite easy to show that a surjection doesn't exist. However, how do we deal with the infinite case? I've been able to show that any surjection (if it exists) from $A$ to $C$ cannot be of the form $g\circ h$ where $h:A\to B,$ and $g:B\to C.$ I haven't gotten further than this, though.
This is one of those naive statements that seem reasonable, but require the axiom of choice (indeed, it is equivalent to the axiom of choice).
Depending on what you've seen already, this may be very easy or not. I will assume the following equivalent statement, that if there is no surjection from $A$ onto $B$, then there is an injection from $A$ into $B$. This is a consequence of "every two cardinals are comparable" along with "if there is an injection $X\to Y$ then there is a surjection $Y\to X$ or $X$ is empty" (the latter requires no choice).
Since there is no surjections $A\to B$ and $B\to C$, there are injections $A\to B$ and $B\to C$. So, if there was a surjection $A\to C$, there would be a surjection $A\to B$ as well.
To see this is equivalent to the axiom of choice, suppose that the axiom of choice fails, and let $X$ which cannot be well-ordered. Now, let $A=C=X$, $B=\aleph^*(X)$ its Lindenbaum number (this is the least non-zero ordinal onto which $X$ does not surject).
Then by definition there is no surjection from $A$ onto $B$, and since $A$ cannot be well-ordered, there is no surjection from $B$ onto $C$, but there is a pretty obvious surjection from $A$ onto $C$.