Does a injective function $f: A \to B$ and surjective function $g : A\to B$ imply a bijective function exists? [duplicate]
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.
Solution 1:
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.
Solution 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$.