Myhill Isomorphism Theorem

In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set.

Myhill isomorphism theorem

Sets ''A'' and ''B'' of natural numbers are said to be recursively isomorphic if there is a total computable if_there_is_a_total_computable_bijective_function_''f''_on_the_natural_numbers_such_that_for_any_$x$,_$x\in_A\iff_f(x)\in_B$.P._Odifreddi,_Classical_Recursion_Theory:_The_theory_of_functions_and_sets_of_natural_numbers_(pp.324--325)._Studies_in_Logic_and_the_Foundations_of_Mathematics,_vol._125_(1989),_Elsevier_0-444-87295-7.

A_set_''A''_of_natural_numbers_is_said_to_be_many-one_reduction.html" ;"title="bijective_function.html" ;"title="if there is a total computable bijective function">if there is a total computable bijective function ''f'' on the natural numbers such that for any $x$, $x\in A\iff f(x)\in B$.P. Odifreddi, Classical Recursion Theory: The theory of functions and sets of natural numbers (pp.324--325). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.

A set ''A'' of natural numbers is said to be many-one reduction">one-one reducible to a set ''B'' if there is a total computable injective function ''f'' on the natural numbers such that $f(A) \subseteq B$ and $f(\mathbb \setminus A) \subseteq \mathbb \setminus B$.

Myhill's isomorphism theorem states that two sets ''A'' and ''B'' of natural numbers are recursively isomorphic if and only if ''A'' is one-reducible to ''B'' and ''B'' is one-reducible to ''A''.

The theorem is reminiscent of the Schroeder–Bernstein theorem, and has been called a constructive version of it.P. Odifreddi, ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7. The proof is different, however. The proof of Schroeder–Bernstein uses the inverses of the two injections, which is impossible in the setting of the Myhill theorem since these inverses might not be recursive. The proof of the Myhill theorem, on the other hand, defines the bijection inductively, which is impossible in the setting of Schroeder–Bernstein unless one uses the Axiom of Choice (which is not necessary for the proof of the Myhill theorem).

A corollary of Myhill's theorem is that two total numberings are one-equivalent if and only if they are recursively isomorphic.

See also

*Berman–Hartmanis conjecture, an analogous statement in computational complexity theory

References

*.
*{{citation
, last = Rogers , first = Hartley, Jr. , author-link = Hartley Rogers, Jr.
, edition = 2nd
, isbn = 0-262-68052-1
, location = Cambridge, MA
, mr = 886890
, publisher = MIT Press
, title = Theory of recursive functions and effective computability
, year = 1987.
*Soare, Robert I. (1987), ''Recursively enumerable sets and degrees : a study of computable functions and computably generated sets,'' Perspectives in Mathematical Logic, Berlin Heidelberg : Springer-Verlag, ISBN 978-3-540-66681-3, MR 0882921
*

Computability theory