Myhill isomorphism theorem
From Wikipedia, the free encyclopedia
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.
[edit] Myhill isomorphism theorem
Sets A and B of natural numbers are said to be recursively isomorphic if there is a total computable bijection f from the set of natural numbers to itself such that f(A) = B.
A set A of natural numbers is said to be one-one reducible to a set B if there is a total computable injection f on the natural numbers such that 
and 
.
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 proved by an effective version of the argument used for the Schroeder-Bernstein theorem.
A corollary of Myhill's theorem is that two total numberings are one-equivalent if and only if they are computably isomorphic.
[edit] References
- John Myhill: “Creative Sets”. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 1:97–108, 1955.
- Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
