Say we have two sets $|A| = a$ and $|B| = b$, where $a \geq b$ and $a$ is infinite. How would you go about proving that the number of surjective functions from A onto B is $b^a$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
HINT: Partition $A$ into sets $A_0$ and $A_1$, where $|A_0|=b$ and $|A_1|=a$. Let $f:A_0\to B$ be any bijection. For each function $g:A_1\to B$, the function $f\cup g$ is a surjection from $A$ to $B$. Use this to show that there are at least $b^a$ surjections from $A$ to $B$. Showing that there are no more than $b^a$ surjections from $A$ to $B$ is straightforward.