4
$\begingroup$

I am poking on a proof of the subject theorem. Given sets $A_i$ and injections $f_i:A_i\to A_{1-i}$, $i\in \{0,1\}$, theorem defines a bijection $b$ between $A_0$ and $A_1$. $b$ uses an auxilary function

$degree (x:A_i) := \cases{ 1+degree(f_{1-i}^{-1}(x)), x\in f_{1-i}(A_{1-i}) \cr 0}$

“degree” may loop, denote this $\bot$. Then $b$ returns some value$\neq\bot$ on $\bot$ and is not constant in general. $b$ solves the halting problem. So, it is possible? (I assume that the codomain of “degree” is a flat domain.) (I have not posted this on cstheory because this is not a research-level question.)

  • 1
    I'm not sure I understand. b is not a Turing machine.2011-02-25

1 Answers 1

8

I believe that you are asking for a computable version of the Cantor-Schroeder-Bernstein theorem.

The traditional answer to this question is to point to Myhill's theorem, which asserts that if $A$ and $B$ are sets of natural numbers and you have a computable one-reduction of $A$ to $B$ (that is, a computable one-to-one function taking $A$ to $B$ and the complement of $A$ to the complement of $B$) and a computable one-reduction of $B$ to $A$, then there is a computable permutation of the natural numbers taking $A$ exactly to $B$.

The proof of Myhill's theorem follows the idea of the classical proof of the Cantor-Schroeder-Bernstein theorem, but gets around the problem you mention of not knowing the nature of the loop that a given input is in with a clever switching method, which periodically closes the bijection off into finite loops.