Myhill isomorphism theorem

For the Goodman–Myhill theorem in constructive set theory, see Diaconescu's 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 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 $f(A) \subseteq B$ and $f(\mathbb{N} \setminus A) \subseteq \mathbb{N} \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 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.

References

Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1: 97–108, doi:10.1002/malq.19550010205, MR 0071379 .
Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 886890 .

This article is issued from Wikipedia - version of the Monday, September 29, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.