Induction proof, help please? I have a problem that I need to prove using induction. Prove that a surjective function has at least as many members in its domain as it does in its codomain.
Do I begin by using the axiom of choice?
Thanks.
 A: If you need to use induction then it is probably that your function is between finite sets. In that case you don't need the axiom of choice. For the general case, you do need the axiom of choice. But you can't really use induction either. Since there seem to be a dispute on why induction is not a valid method for the infinite case, let me spell out the reason.
The reason you can't use induction is that in order to pass from a set of cardinality $\kappa$ to a set of cardinality $\kappa^+$, and in order to use the induction hypothesis (and that's where induction really works, otherwise using the word induction won't make it a proof by induction), you will have to start with a set of cardinality $\kappa^+$ and remove some part of it. Removing a part of cardinality less than $\kappa^+$ won't change the cardinality and therefore you cannot use the induction hypothesis; removing a part of cardinality $\kappa^+$ doesn't guarantee that you end up with a set of cardinality less than $\kappa^+$ in order to use the induction hypothesis; and if you do remove almost the entire set, then in order to deduce from the induction hypothesis on $\kappa$ to the case of $\kappa^+$ you have to actually assume that the case of $\kappa^+$ was correct to begin with -- thus begging the question.
Moreover, if you are not intending to use the axiom of choice then the claim is consistently false; that is to say it is perfectly possible that there is a set which can be mapped onto a strictly larger set than itself when the axiom of choice fails. So you have to use the axiom of choice in order to prove this claim, and if you do -- then you might as well use it directly. As in Peter's answer on this page.
In any case, for the issue of finite sets, here is some elaborated hint:
Suppose $f\colon A\to B$ is a surjection, we prove by induction that if $A$ has $n$ members then $B$ has no more than $n$ members.
For $n=1$ this is trivial because $A$ is a singleton, so $B$ must be a singleton as well. Suppose this is true for $n$, and let $A$ be a set of size $n+1$.
Pick some $a\in A$, and consider $A'=A\setminus\{a\}$. If $f\upharpoonright A'$ is still a surjection onto $B$, then we can use the induction hypothesis to conclude that $B$ has at most $n$ members and we are done.
In the other case, $f\upharpoonright A'$ is not surjective. Conclude that there is some $b\in B$ such that $f\upharpoonright A'\colon A'\to B\setminus\{b\}$ is a surjection, therefore $B\setminus\{b\}$ has at most $n$ members and therefore $B$ has at most $n+1$ members as wanted.
A: DSC Asaf already gave an answer assuming the sets are finite. Without said assumption, we cannot use usual induction and can give the following proof, assuming the Axiom of Choice.
P Say $f:A\to B$. Since $f$ is surjective, for each $b\in B$ there exists $a\in A$ such that $f(a)=b$. Thus $f^{-1}(b)=\hat b$ is nonempty for each $b\in B$. Take a choice function for the collection of fibers over the elements of $b$ to obtain an injection $B\to A$, thus proving $|B|\leq |A|$. That is, for each $b\in B$ pick $a\in f^{-1}(b)$. Then $b\mapsto a\in f^{-1}(b)$ is an injection: if $b\neq b'$ then $f^{-1}(b)\cap f^{-1}(b')=\varnothing$; so $a\neq a'$.
