Teorema de Cantor-Bernstein-Schröder y recursión

Question

Me estoy metiendo en una prueba de la asignatura teorema. Dado los conjuntos de $A_i$ e inyecciones $f_i:A_i\to A_{1-i}$, $i\in \{0,1\}$, teorema define un bijection $b$ $A_0$ y $A_1$. $b$ utiliza un auxilary función

$grado (x:A_i) := \casos{ 1+grado(f_{1-me}^{-1}(x)), x\f_{1-me}(A_{1-me}) \cr 0}$

"grado" de mayo de bucle, denotar esta $\bot$. A continuación, $b$ devuelve algún valor$\neq\bot$ $\bot$ y no es constante en general. $b$ resuelve la suspensión problema. Así, es posible? (Supongo que el codominio de "grado" es un plano de dominio.) (No he publicado esto en cstheory porque esto no es una investigación a nivel de la pregunta.)

Answer 1

Creo que usted está pidiendo una computable versión de el Cantor-Schroeder-teorema de Bernstein.

La respuesta tradicional a esta pregunta es el punto a del teorema de Myhill, que afirma que si $A$ $B$ son conjuntos de números naturales y tiene una computable de una reducción de $A$ $B$(es decir, una computable uno-a-uno de la función de tomar $A$ $B$y el complemento de $A$ al complemento de $B$) y una computable de una reducción de $B$$A$, entonces no es una computable permutación de los números naturales tomando $A$ exactamente a $B$.

La prueba de Myhill del teorema que sigue la idea de la clásica prueba del Cantor-Schroeder-teorema de Bernstein, pero se pone todo el problema que mencionas de no conocer la naturaleza del lazo que una entrada es con un ingenioso método de conmutación, que periódicamente se cierra el bijection en bucles finitos.