This is [cross-posted from MSE](https://math.stackexchange.com/questions/3420622/how-much-of-the-cantor-schr%C3%B6der-bernstein-theorem-is-constructively-recoverable) at the suggestion of a comment after receiving no answers over a few weeks.


Suppose we have $f : A \to B$ and $g : B \to A$, as well as left inverses $f\_r : B \to A$ of $f$ and $g\_r : A \to B$ of $g$. Suppose further that $f$ and $g$ have decidable images; i.e., we have $\forall b : B.(\exists a : A. f(a) = b) \vee \neg(\exists a : A. f(a) = b)$, and similarly in the other direction (replace $\vee$ with $+$ in a proof-irrelevant setting). So this is the structure necessary to work with an expression like $f^{-1}(b)$; we can ask whether it is defined, and what its value is if so.


My impression is that the inability to invert an arbitrary function is ordinarily the biggest obstacle in Cantor-Schröder-Bernstein, so I'm interested in knowing what difficulties are left if you skip over that issue by fiat.


I've been playing with these assumptions in Coq, and so far I've managed to adapt the standard proof by König to show that there exist sequences of functions $F\_n : A \to B$ and $G\_n : B \to A$ which gradually approximate the classically defined bijections. Most importantly, their sequences of compositions $G\_n \circ F\_n$ and $F\_n \circ G\_n$ "converge pointwise to" the identities on $A$ and $B$ in the following weak sense:
$$\forall a : A. \neg\neg\exists n : \mathbb N.\forall m \ge n.G\_m(F\_m(a)) = a$$
$$\forall b : B. \neg\neg\exists n : \mathbb N.\forall m \ge n.F\_m(G\_m(b)) = b$$


But this seems like a fairly weak result, and I'd like to know how much it may be possible to strengthen it! I did find the [Myhill isomorphism theorem](https://en.wikipedia.org/wiki/Myhill_isomorphism_theorem), but having looked at the proof, it seems like any adaptation of it to more general premises like the ones I've given might require the types in question to be subcountable or something like that.



How much of the Cantor-Schröder-Bernstein theorem is constructively recoverable if the injections have retractions and decidable images?
CSB fails intuitionistically even under the conditions which you describe. This was proved by Van Dalen in [A note on spread-cardinals](http://www.numdam.org/article/CM_1968__20__21_0.pdf), Compositio Mathematica, tome 20 (1968), p. 21-28. 


Van Dalen gives an intuitionistic counterexample to CBS consisting of two compact subspaces of Baire space $\sigma, \tau$ and two injective functions $f, g$ between them. 


These are such that $f(\sigma)$ is decidable in $\tau$ (and therefore a retract of $\tau$ since this is Baire topology) and vice versa $g(\tau)$ is decidable in $\sigma$ (and therefore a retract of $\sigma$), and yet there can be no bijection between $\sigma$ and $\tau$ in intuitionistic mathematics.


This shows that CSB cannot be proved constructively even under the conditions you mention.




---


[update 29 november to reflect the comments below:]


A fundamental reason why CSB fails in constructive mathematics is because in constructive mathematics total functions are 'always' continuous. Both in intuitionistic mathematics (INT) and in recursive mathematics (RUSS) total functions are provably continuous. Therefore a total function defined in BISH, being provably continuous in INT and RUSS, is 'always' continuous in BISH.


**For constructive CSB this entails that we are dealing with a strong topological version: given two topological spaces $X,Y$ where $X$ can be embedded in $Y$ and vice versa, is it true that $X$ and $Y$ are homeomorphic?**


One easily sees that this is only very rarely true. The extra conditions in your question somewhat amount to adding the following: 'where in addition the embedding of $X$ is clopen in $Y$ and vice versa'. This is topologically not enough to constructively ensure homeomorphism, as Van Dalen's example shows.


In general, because of this strong topological component, I have no hope at all that there are interesting (general enough) constructive versions of CSB. There can be truly topological theorems on what embeddability properties entail that two spaces are homeomorphic, but like I said, these theorems do not have the flavour of CSB in my eyes.


