# A question dealing with cardinals, and axiom of choice.

I am given sets $A$,$B$ such that there exists $f:A\rightarrow B$ s.t. $f$ is onto $B$.

I am trying to show that $B\le A$

Let $b\in B$, consider $\{a\in A \mid f(a) = b\}$, assuming axiom of choice, this set can be well ordered such that we can pick its smallest element; denote this element by $a_b$.

then $f_0:B\rightarrow A,f_0(b)=a_b$ is an injective function and we are done.

Is this correct?

• thnx for edit, I did not know about ./mid – H_B Dec 6 '14 at 21:59
• If you’re going to use well-ordering, it would be neater to well-order $A$ once and for all and just choose the least element of $f^{-1}[\{b\}]$ each time. Your version amounts to saying directly that there’s a choice function for $\{f^{-1}[\{b\}]:b\in B\}$, since you’re choosing a separate well-order out of thin air for each $f^{-1}[\{b\}]$. – Brian M. Scott Dec 6 '14 at 22:02
• lol wow I feel silly. That would be much nicer and cleaner. But does this work the way I did it? – H_B Dec 6 '14 at 22:07
• It depends on what you’ve already done with $\mathsf{AC}$. You’re already using $\mathsf{AC}$ in a different form just to choose the well-orders that you use, so the well-orders aren’t actually doing anything for you. If you already have that the well-ordering principle is equivalent to the existence of choice functions, then your argument is correct but unnecessarily complicated, since you could use a choice function directly to get $f^{-1}$. If not — if you have only the well-ordering principle — then it’s not correct: it doesn’t justify the ability to choose the little well-orders. – Brian M. Scott Dec 6 '14 at 22:12
• I would probably have scored it $8$ or $9$, out of $10$ when I was still teaching; that means that it’s basically sound but could stand some cleanup (which I would have explained in a note on the paper). Your idea was good; the point that you were overlooking is a little bit subtle. – Brian M. Scott Dec 6 '14 at 22:18

Your idea is not a good one.

Here's a plausible scenario. Suppose that $S$ is a set such that $S=\bigcup_{n\in\Bbb N}P_n$ where each $P_n$ is a set of cardinality $2$, and there is no choice function from each pair.

It is clear that $S$ can be mapped onto $\Bbb N$, simply by mapping by $f$, $s$ to the unique $n$ such that $s\in P_n$. But now taking $S_n=\{s\in S\mid f(s)=n\}$, it satisfies satisfies $S_n=P_n$. Each $P_n$ can be well-ordered, but it doesn't mean that we can choose, uniformly, from each $P_n$ an element. In this particular case we can't.

The problem is that you need to choose a well-ordering for each $S_n$, and that's something that there is no guarantee that you can do uniformly for each $S_n$.

Instead, given a surjection from $A$ onto $B$, find a family of non-empty sets and define a choice function which is the injection form $B$ into $A$ that you are looking for.

• Could you explain the part about there being no choice function for each pair. – H_B Dec 7 '14 at 10:22
• What do you want me to explain about it? – Asaf Karagila Dec 7 '14 at 10:26
• I don't understand what is meant. We have sets of of two elements, and there is no way to choose from there? Sorry I am new to all of this choice stuff... – H_B Dec 7 '14 at 19:22
• Each $S_n$ has two elements, but there is no function with domain $\Bbb N$, such that $f(n)\in S_n$. So there is a function from $S$ onto $\Bbb N$, but there is no function from $\Bbb N$ into $S$ which is injective. This despite the fact that each $S_n$ can be well-ordered, because a set of two elements can be well-ordered. Of course, the issue here is that (1) you cannot well-order all the $S_n$'s uniformly; and therefore (2) you cannot well-order $S$, their union. If you could do that, then you could have picked the minimal of each pair. – Asaf Karagila Dec 7 '14 at 19:29