According to the Cantor-Bernstein Theorem, if $A$ and $B$ are two sets, and there exists injections $f:A\rightarrow B$ and $g:B\rightarrow A$, then there exists a bijection from A to B.
I recently proved the CB theorem independently by constructing a bijection between the two sets, and I was surprised to learn that apparently a constructive proof of the theorem either requires the Axiom of Choice or the Principle of Excluded Middle, since I didn't think I had used either. I can only conclude that either 1) I used one of those axioms and didn't realize it or 2) my proof doesn't work. Please let me know where I used the AoC or the PEX, or where I made a mistake.
Proof:
Let $A$ and $B$ be sets, and let $f:A\rightarrow B$ and $g:B\rightarrow A$ be injections.
Since the composition of two injections is also an injection, $g\circ{f}:A\rightarrow A$ is also an injection
$\Rightarrow$ $g\circ f:A\rightarrow (g\circ f)(A)$ is a bijection from A onto a subset of A.
$\Leftrightarrow\exists$ bijection $\alpha:(g\circ f)(A)\rightarrow A$
Similarly, $\exists$ bijection $\beta:(f\circ g)(B)\rightarrow B$, with $(f\circ g)(B)\subseteq B$.
Let $b\in (f\circ g)(B)$. Then $b=f(g(b_0))$, some $b_0\in B$.
$g(B)\subseteq A \Rightarrow\exists a\in A |a = g(b_0) \Rightarrow\exists x\in(g\circ f)(A) | \alpha (x)=a \Rightarrow f(\alpha(x))=f(g(b_0))=b$.
So $\phi = f\circ\alpha: (g\circ f)(A)\rightarrow (f\circ g)(B)$ is a surjection, and since it is a composition of injections, $\phi$ is also a bijection.
$\therefore\beta\circ\phi\circ\alpha^{-1}:A\rightarrow B$ is a bijection.
The mistake in your proof is when you write "$\phi = f\circ \alpha\colon (g\circ f)(A)\to (f\circ g)(B)$ is a surjection."
In fact, $\phi$ (which is just $g^{-1}$ restricted to $(g\circ f)(A)$) is a surjection onto $f(A)$, not onto the smaller set $(f\circ g)(B)$. So it establishes a bijection between $(g\circ f)(A)$ and $f(A)$. This proves nothing, since both of these sets are already in bijection with $A$.