1
$\begingroup$

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.

  • 0
    I am not sure if [Schroeder Bernstein](http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem) will help!2012-02-13
  • 0
    @KannappanSampath: In the presence of AC it will; in its absence it won't. See the duplicate link.2012-02-13
  • 0
    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! :)2012-02-13

2 Answers 2

9

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.

  • 0
    Thanks, and thanks for posting the duplicate link thing. I looked for it initially but couldn't find it.2012-02-13
  • 0
    @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 ?2014-03-14
  • 0
    @Tom: Yes, the point is that without assuming the axiom of choice it might not be provable.2014-03-14
  • 0
    @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).2014-03-14
  • 0
    @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.2014-03-14
2

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