8
$\begingroup$

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
    Look up "Cantor-Schröder-Bernstein".2011-06-18
  • 1
    Are you assuming the Axiom of Choice? (If so, I'm guessing that using Cantor-Bernstein is what you mean by "using cardinality"?)2011-06-18
  • 4
    @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.2011-06-18
  • 0
    @Yuval: Arturo is correct, see the link in my answer.2011-06-18
  • 0
    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.2011-06-18
  • 0
    @Grigory M: Of course, but without choice this theorem fails, while Cantor-Bernstein holds. Therefore the two theorems are not equivalent, I added "-like" to the title, to reflect exactly that.2011-06-19
  • 0
    @Asaf Fair point. That's better.2011-06-19
  • 0
    @Pedro: If something is missing from one of the answers, please add information about that; otherwise please accept one of the answer by clicking on the transparent check mark by the vote counts.2011-06-25
  • 0
    @LePressentiment: If you are trying to get an Archaeologist badge, at least make the titles reasonable. The previous title had more to do with the question with the current one.2013-10-29

2 Answers 2

15

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

  • 0
    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?2011-06-19
  • 4
    Wow, the history of that theorem is just great if [citizendium](http://en.citizendium.org/wiki/Schröder-Bernstein_theorem) 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.2011-06-19
  • 1
    @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!) :-)2011-06-20
  • 0
    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.2011-06-20
3

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

  • 1
    **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.2011-06-19
  • 0
    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.2011-06-20