1

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.

2 Answers2

4

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.

Asaf Karagila
  • 393,674
  • What do you think of my idea? – Pedro Jul 09 '13 at 17:33
  • 1
    @Peter: It's true, assuming the axiom of choice, but it's not a proof by induction... And I feel that it obscures the (likely) importance of this exercise: both to understand a bit better inductions and the cardinality of finite sets, which is something we take for granted. – Asaf Karagila Jul 09 '13 at 17:38
  • That's why I deleted it. (I know it is not a proof by induction! =) ) But since the OP talked about AC... – Pedro Jul 09 '13 at 17:39
  • I think the statements in your first paragraph are not correct. – OR. Jul 09 '13 at 17:49
  • @Franklin: Which statements exactly? – Asaf Karagila Jul 09 '13 at 17:53
  • @Franklin: First note that induction not usually refers to transfinite induction. Secondly, you don't really use the induction hypothesis when you move to a successor cardinal. Because removing a very large set render the hypothesis useless, and demoing a small set is insufficient for usin it. What you are using is the well-ordering of the cardinal. Regardless to the induction "framework". – Asaf Karagila Jul 09 '13 at 17:57
  • Well-ordering is equivalent to induction, transfinite induction, tomAto, tomEIto. I am not removing sets, only using induction. The OP wanted 'by induction' I gave him/her 'by induction'. – OR. Jul 09 '13 at 18:01
  • 2
    @Franklin. Using the word induction in your proof doesn't make it a proof by induction. Note that transfinite induction is a theorem of $\sf ZF$, without the axiom of choice. By this argument of yours any proof anyone has ever written is a proof by induction, and that's just not right. This is like saying "okay let's give a different proof, then prove by induction that $x=x$". – Asaf Karagila Jul 09 '13 at 18:05
  • OK... I undeleted and got downvoted. Yikes. – Pedro Jul 09 '13 at 18:13
  • @Peter: Maybe because your answer didn't contain the magic word "induction" ;-) – Asaf Karagila Jul 09 '13 at 18:15
  • Right... and now someone downvoted my answer. I wonder why. – Asaf Karagila Jul 09 '13 at 18:19
  • @Franklin: Your move. – Asaf Karagila Jul 09 '13 at 18:35
  • 2
    @AsafKaragila You're implacable. – Pedro Jul 09 '13 at 18:36
  • @AsafKaragila Now what? – OR. Jul 09 '13 at 18:55
  • @AsafKaragila I now understand what you were trying to say. A 'proof by induction' is a proof that the proof itself has the structure typical of induction. My proof is not a 'proof by induction'. My proof is a proof that shows the result 'using that induction is true on the domain of the function'. – OR. Jul 09 '13 at 21:42
  • @Franklin: Yes. That was my point, and I'm glad that we agree on that. – Asaf Karagila Jul 09 '13 at 23:05
  • Summing up... – Pedro Sep 02 '13 at 22:32
1

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'$.

Pedro
  • 122,002