I had a discussion with one of my teachers the other day, which boiled to the following question:



> 
> Assume ZF. Let $A,B$ be sets such that there exist $f\colon A\to B$ which is injective and $g\colon A\to B$ which is surjective.
> 
> 
> Is there $h\colon A\to B$ which is bijective?
> 
> 
> 


Of course it is enough to show that there is an injection from $B$ into $A$, and by the Cantor-Bernstein theorem (which does not require choice) we finish the proof.


My intuition says that this is true, his intuition says it is false.


Insights, references and possible solutions will be appreciated!




---


As Ricky shows below, it depends on $A$ and $B$.


So to a more specific choice of sets (for which I think it is true) we have $A=\mathbb R^\omega$ (i.e. infinite sequences of real numbers) and $B=[\mathbb R]^\omega$ (i.e. countable subsets of real numbers)



Half Cantor-Bernstein Without Choice
If $A = \{0\}\times 2^{\omega}$ and $B = (\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1)$ and there is no injection from $\omega\_1$ to $2^{\omega}$,
  

then there does not exist such a bijection.
  
  
  

Define $f : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1))$ by $f(x) = x$. Obviously, $f$ is injective.
  

Define $\operatorname{pair} : \omega^2 \to \omega$ by $\operatorname{pair}(\langle m,n\rangle) = ((m+n)\cdot (m+n+1))+(2\cdot n)$.
  

Define $g\_1 : 2^\{\omega\} \to \omega\_1$ by


$g\_1(x) = \begin{cases} \alpha & \text{if } \{\langle m,n\rangle \in \omega^2 : \operatorname{pair}(\langle m,n\rangle) \in x\} \text{ is a well-order of } \omega \text{ with order type } \alpha \\ 0 & \text{else} \end{cases} \quad .$


Define $g : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1))$ by


$g(\langle 0,x\rangle) = \begin{cases} \langle 0,\{n\in \omega : (n+1) \in x\}\rangle & \text{if } 0 \notin x \\ \langle 1,g\_1(\{n\in \omega : (n+1) \in x\})\rangle & \text{if } 0\in x\end{cases} \quad .$


Since $g\_1$ is surjective, $g$ is also surjective. Let $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1)) \to (\{0\}\times 2^{\omega})$ be a function. Define $h\_1 : \omega\_1 \to 2^{\omega}$ by $h\_1(\alpha) = \operatorname{secondentry}(h(\langle 1,\alpha \rangle))$.
  

$h\_1$ is not injective, so $h$ is not injective either.
  

This works for all functions $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1)) \to (\{0\}\times 2^{\omega})$, so
  

there does not exist a bijection $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega\_1)) \to (\{0\}\times 2^{\omega})$.
  
  
  
  

if $A = \{\}$ and $B = \{\}$, then there does exist such a bijection.


Define $h : A\to B$ by $h(x) = x$.
  
  
  
  
  

Therefore there does not have to be a single answer, it can depend on $A$ and $B$.
  
  
  

  
  
  

If all sets of reals have Baire property, then there is no injection from $[\mathbb R]^\omega$ to $\mathbb R^\omega$.


Let $h : [\mathbb R]^\omega \to \mathbb R^\omega$ be a function. Define $\leq$ as the lexicographic order of $\mathbb R^\omega$.
  

By [this answer](https://mathoverflow.net/questions/26861/explicit-ordering-on-set-with-larger-cardinality-than-r/26893#26893) there is no total order of ${\mathbb R}/\sim$. All members of ${\mathbb R}/\sim$ are countable subsets of $\mathbb{R}$.
  

Define $\leq\_h$ on ${\mathbb R}/\sim$ by $x\: \leq\_h\: y$ if and only if $h(x) \leq h(y)$. Since $\leq\_h$ is not a total order, $h$ is not injective. This works for all functions $h : [\mathbb R]^\omega \to \mathbb R^\omega$, therefore there is no injection $h : [\mathbb R]^\omega \to \mathbb R^\omega$.
  
  
  

By shelah.logic.at/files/446.ps (which I can't figure out how to make markdown link to),
  

$\operatorname{ZF} + \operatorname{DC}(\omega\_1)$ does not prove that there is an injection from $[\mathbb R]^\omega$ to $\mathbb R^\omega$.


