Cantor-Bernstein-like theorem: If $f\colon A\to B$ is injection and $g\colon A\to B$ is surjective, can we prove there is a bijection as well?

Solution 1:

This is generally not true in $ZF$ (cf. this MathOverflow question).

Assuming the axiom of choice, this becomes relatively simple.

Since $g$ is surjective, for every $b\in B$ the set $g^{-1}(b)$ is nonempty. If so we can choose $a_b$ to be such that $g(a_b) = b$ for every $b\in B$ (this can be a proper subset of $A$). The function $b\mapsto a_b$ is an injective function from $B$ into $A$.

By the Cantor-Bernstein theorem (which does not require the axiom of choice) we have that there exists a bijection $h$ as needed.

Addendum: Proof of the Cantor-Bernstein theorem using the axiom of choice

Suppose $A$ and $B$ are sets and there exists $f\colon A\to B$ injective, and $g\colon B\to A$ injective. Then there exists $h\colon A\to B$ bijective.

Proof: By the axiom of choice we can well order $A$ and $B$ as the least order type possible. So without the loss of generality we may assume $A=\alpha$ and $B=\beta$ for two ordinals.

Since two well orders are comparable in the embedding relation (i.e. $\alpha$ can be embedded into an initial segment of $\beta$, or vice versa) and in particular $\alpha\subseteq\beta$ or $\beta\subseteq\alpha$, we have if so that $f\colon\alpha\to\beta$ and $g\colon\beta\to\alpha$ are two injective functions.

Recall that $\beta$ was the least ordinal bijectible with $B$, so if $\alpha<\beta$ there is no injection from $\beta$ into $\alpha$. Therefore $g$ witnesses $\beta\le\alpha$.

The same argument holds for $\alpha$ and $A$ so $f$ witnesses $\alpha\le\beta$. Since the ordinals are linearly ordered, anti-symmetry implies $\alpha=\beta$.

The function $h$ is the composition of the well ordering functions of $A$ and $B$, that is if $w_1\colon A\to\alpha$ is the bijection of $A$ with $\alpha$, and $w_2\colon B\to\beta$ the bijection we used to well order the set $B$, define $h=w_2^{-1}\circ w_1\colon A\to B$ which is a bijection.

I'm not sure that this is the original Cantor proof, but it works, and I don't think that the proof Cantor used was too different, perhaps the use of ordinals was slightly different (back then they only used the fact that well orders are embeddable into each other nicely).

Solution 2:

As soon as we know that existence of surjective map $A\to B$ is equivalent implies to existence of injective map $B\to A$, this is the Cantor-Bernstein theorem.

The above claim follows from the following equivalent form of Axiom of Choice:

(S) For every surjective map $g: A\to B$ there exists a map $h: B\to A$ such that $(\forall b\in B) h(g(b))=b$. http://en.wikipedia.org/wiki/Axiom_of_Choice#Equivalents

The proof of AC $\Rightarrow$ (S) was given in Asaf's post. A map $h$ fulfilling the above property is injective.

Some proofs of Cantor-Bernstein can be found here: http://www.proofwiki.org/wiki/Cantor-Bernstein-Schroeder_Theorem

I do like the proof which uses Knaster-Tarski theorem. (In fact proof 3 from the above link is the same thing as showing Knaster-Tarski in this special case.)

http://planetmath.org/?op=getobj&from=objects&name=ProofOfSchroederBernsteinTheoremUsingTarskiKnasterTheorem

Brown, Pearcy: An introduction to analysis, Theorem 4.1

EDIT: GEdgar pointed out an error in my original formulation. Let me address this shortly. (I hope I remember it correctly.) The following two claims work for any sets $A$, $B$:

• $g: A\to B$ is surjective $\Leftrightarrow$ there exists $h: B\to A$ such that $g\circ h=id_B$. (I.e., $g$ has right inverse.)
• We are given a map $h: B\to A$. If there exists $g: A\to B$ such that $h\circ g=id_A$, then $h$ is injective.

Under the assumption $B\ne\emptyset$ we get

• $h: B\to A$ is injective $\Rightarrow$ there exists $g: A\to B$ such that $h\circ g=id_A$. (I.e., $h$ has left inverse.)

The last claim is not true for $B=\emptyset$ and $A\ne\emptyset$, since empty function from $\emptyset$ fo $A$ is injective, but there is no function from a non-empty set to $\emptyset$.