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.)

$\endgroup$
  • 1
    $\begingroup$ I'm not sure I understand. b is not a Turing machine. $\endgroup$ – Qiaochu Yuan Feb 25 '11 at 12:32
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.