Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Proof of a Cantor-Bernstein-like theorem

If $A, B$ are sets and there exists an injective function $f : A \to B$ and a surjective function $g: A \to B$, does this imply there is a bijective function $h : A \to B$?

If not is there a simple counter example?

I was wondering because while reading about Cantor's Theorem, it seems like an injective function existing is like saying $|A| \le |B|$, and surjective function existing says $|A| \ge |B|$. So when they both exist I would expect a bijection to exist too.

Am I correct in my reasoning?

Thanks.

share|improve this question

marked as duplicate by Asaf Karagila, Kannappan Sampath, anon, J. M., Ilya Feb 13 '12 at 10:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
I am not sure if Schroeder Bernstein will help! –  user21436 Feb 13 '12 at 8:05
    
@KannappanSampath: In the presence of AC it will; in its absence it won't. See the duplicate link. –  Asaf Karagila Feb 13 '12 at 8:05
    
Ah, I see. Thank you @AsafKaragila. I was aware of this but I had long ago given up doing set theory and hence the gap! :) –  user21436 Feb 13 '12 at 8:10
add comment

2 Answers

up vote 7 down vote accepted

Assuming the axiom of choice then indeed the existence of a surjection from $A$ onto $B$ implies $|B|\le|A|$. This is simply because the axiom of choice is equivalent to the assertion that every surjection has an injective inverse, so from the said surjection we can define an injection from $B$ into $A$ showing $|B|\le|A|$.

However this is not necessarily true without the axiom of choice. In fact there are many strange cases where a surjection exists from $X$ onto $Y$, but there are no injections from neither into the other.

It can get even stranger: It is possible to have a surjection from $X$ onto $Y$ and an injection from $X$ into $Y$, but still... no bijection.

The Cantor-Bernstein theorem, however, holds without the need of the axiom of choice. So if $X$ has an injection into $Y$ and $Y$ has an injection into $X$ then there is a bijection between them. This is why cardinality is defined using injections rather than surjections.

share|improve this answer
    
Thanks, and thanks for posting the duplicate link thing. I looked for it initially but couldn't find it. –  Danikar Feb 13 '12 at 8:23
    
@Asaf. I follow your answer, except the bit about examples. Wouldn't an example of a surjection without an injective inverse disprove the axiom of choice ? Is there a simple example you can refer to ? –  Tom Collinge Mar 14 at 14:07
    
@Tom: Yes, the point is that without assuming the axiom of choice it might not be provable. –  Asaf Karagila Mar 14 at 15:08
    
@Asaf. Do I understand then that there are "many strange examples" of a surjection from A to B where no-one has demonstrated an injection from B to A (rather than that there is a surjection from A to B and someone has proved that there is no injection from B to A). –  Tom Collinge Mar 14 at 19:02
    
@Tom: Again, when the axiom of choice fails. Yes. Every model that we know of where the axiom of choice fails usually includes at least one "surprising bizarre surjection" like that. –  Asaf Karagila Mar 14 at 19:24
add comment

Take your surjective function $g:A \to B$ and use choice to build an injection $\pi: B \to A$ out of it. I.e. for each $b \in B$, consider the set $g^{-1}(b)$, pick one such element $a \in g^{-1}(b)$, and define $\pi(b) = a$. Doing this for all $b$ gives an injection, as the inverse sets $g^{-1}(b)$ are all disjoint. Apply Cantor-Schroeder-Bernstein to obtain a bijection $h$.

share|improve this answer
add comment

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