Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
I'm not sure I understand. b is not a Turing machine. –  Qiaochu Yuan Feb 25 '11 at 12:32
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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