Effective Versions of Cantor-Bernstein Theorem

(Abstract)

Cantor-Bernstein theorem asserts that if there are 1:1 functions $f: A\rightarrow B$ and $g: B\rightarrow A$, then there exists a 1:1 onto function $h: A\rightarrow B$. Later, the effectiveness of this theorem is investigated by Remmel. Our discussion mainly focuses on the computation complexity and time complexity of $h$ for the special case $A=B=\mathbb{N}$, where the combinatorial method form Remmel turns out to be very useful. Furthermore, we will show that the general version of Remmel's theorem is equivalent to ACA$_0$, and will also find an effective version of Cantor-Bernstein theorem which is equivalent to WKL$_0$.