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