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?

  • $\begingroup$ thnx for edit, I did not know about ./mid $\endgroup$ – H_B Dec 6 '14 at 21:59
  • 1
    $\begingroup$ 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\}]$. $\endgroup$ – Brian M. Scott Dec 6 '14 at 22:02
  • $\begingroup$ lol wow I feel silly. That would be much nicer and cleaner. But does this work the way I did it? $\endgroup$ – H_B Dec 6 '14 at 22:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Dec 6 '14 at 22:12
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Could you explain the part about there being no choice function for each pair. $\endgroup$ – H_B Dec 7 '14 at 10:22
  • $\begingroup$ What do you want me to explain about it? $\endgroup$ – Asaf Karagila Dec 7 '14 at 10:26
  • $\begingroup$ 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... $\endgroup$ – H_B Dec 7 '14 at 19:22
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Dec 7 '14 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.