Set Theory – Cantor-Schroder-Bernstein Statement About Surjective Maps

axiom-of-choicefunctionsset-theory

Let $A,B$ be two sets. The Cantor-Schroder-Bernstein states that if there is an injection $f\colon A\to B$ and an injection $g\colon B\to A$, then there exists a bijection $h\colon A\to B$.

I was wondering whether the following statements are true (maybe by using the AC if necessary):

  1. Suppose $f \colon A\to B$ and $g\colon B\to A$ are both surjective, does this imply that there is a bijection between $A$ and $B$.
  2. Suppose either $f\colon A\to B$ or $g\colon A\to B$ is surjective and the other one injective, does this imply that there is a bijection between $A$ and $B$.

Best Answer

For the first one the need of the axiom of choice is essential. There are models of ZF such that $A,B$ are sets for which exists surjections from $A$ onto $B$ and vice versa, however there is no bijection between the sets.

Using the axiom of choice we can simply inverse the two surjections and have injections from $A$ into $B$ and vice versa, then we can use Cantor-Bernstein to ensure a bijection exists.

The second one, I suppose should be $f\colon A\to B$ injective and $g\colon A\to B$ surjective, again we need the axiom of choice to ensure that there is a bijection, indeed there are several models without it where such sets exist but there is no bijection between them. Using the axiom of choice we reverse the surjection and use Cantor-Bernstein again.

It should be noted that without the axiom of choice it is true that if $f\colon A\to B$ is injective then there is $g\colon B\to A$ surjective. Therefore if the first statement is true, so is the second, and if the second is false then so is the first.

Another interesting point on this topic is this: The Partition Principle says that if there is $f\colon A\to B$ surjective then there exists an injective $g\colon B\to A$. Note that we do not require that $f\circ g=\mathrm{id}_B$, but simply that such injection exists.

This principle implies both the statements, and is clearly implied by the axiom of choice. It is open for over a century now whether or not this principle is equivalent to the axiom of choice or not.

Lastly, as stated $f\colon A\to B$ injective and $g\colon B\to A$ surjective cannot guarantee a bijection between $A$ and $B$ with or without the axiom of choice. Indeed the identity map is injective from $\mathbb Z$ into $\mathbb R$, as well the floor function, $x\mapsto\lfloor x\rfloor$ is surjective from $\mathbb R$ to $\mathbb Z$ but there is no bijection between $\mathbb Z$ and $\mathbb R$.

Related Question