I've been trying to find this proof:

If there exists $f \colon A\to B$ injective and $g \colon A \to B$ surjective, prove there exists $h \colon A \to B$ bijective.

I thought of using cardinality, but I think it's possible to prove that without using it. Anyone knows how to?

  • 5
    $\begingroup$ Look up "Cantor-Schröder-Bernstein". $\endgroup$ – Yuval Filmus Jun 18 '11 at 20:56
  • 1
    $\begingroup$ Are you assuming the Axiom of Choice? (If so, I'm guessing that using Cantor-Bernstein is what you mean by "using cardinality"?) $\endgroup$ – Arturo Magidin Jun 18 '11 at 20:59
  • 4
    $\begingroup$ @Yuval: I think you need AC before you can apply C-S-B, since you'll want to replace $g$ with an injective function going the other way. $\endgroup$ – Arturo Magidin Jun 18 '11 at 20:59
  • $\begingroup$ @Yuval: Arturo is correct, see the link in my answer. $\endgroup$ – Asaf Karagila Jun 18 '11 at 21:00
  • $\begingroup$ In view of the fact that we have stumbled into "depends on your set theory" territory, instead of dropping [set-theory] and keeping [elementary-set-theory], I've gone the other way. $\endgroup$ – Arturo Magidin Jun 18 '11 at 21:02

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

  • $\begingroup$ Well, that first part is trivial. But how do we prove this Cantor-Bernstein theorem? I looked up wikipedia and it had two proofs; it also mentions a proof by Cantor which relies on the axiom of choice. Do you know what proof would that be? $\endgroup$ – Pedro Jun 19 '11 at 1:31
  • 4
    $\begingroup$ Wow, the history of that theorem is just great if citizendium is to be trusted on that. Briefly: 1887: Dedekind proves it, but doesn't publish, 1895: Cantor states it but doesn't prove it, 1896: Schroeder announces a proof but fails to prove it because his proof is flawed 1897: Bernstein proves it, Dedekind re-proves it and finally 1898 Borel publishes it. $\endgroup$ – t.b. Jun 19 '11 at 23:17
  • 1
    $\begingroup$ @Theo: To quote Bon Scott, it's a long way to the top if you wanna rock'n'roll. (Which I am most certain Dedekind wanted to do!) :-) $\endgroup$ – Asaf Karagila Jun 20 '11 at 10:59
  • $\begingroup$ Ah, good ol' Bon Scott took the same road as Jon Bonham (waaay to much scotch and other things, I presume) and is sorely missed (not only by me). Well, Dedekind (1831-1916) probably was already too old to rock'n'roll but too young to die as Ian Anderson put it. $\endgroup$ – t.b. Jun 20 '11 at 11:36

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


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

  • 1
    $\begingroup$ existence of surjective map A→B is equivalent to existence of injective map B→A Actually there is a small exception that involves the empty set. $\endgroup$ – GEdgar Jun 19 '11 at 13:31
  • $\begingroup$ Thanks for pointing it out @GEdgar. I tried to correct my answere and add a clarification of this point in the end. I hope it is correct now. $\endgroup$ – Martin Sleziak Jun 20 '11 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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