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.
Theorem
Definitions
Sets A and B of natural numbers are said to be recursively isomorphic if there is a total computable bijective function f on the natural numbers such that for any [math]\displaystyle{ x }[/math], [math]\displaystyle{ x\in A\iff f(x)\in B }[/math].[1]
A set A of natural numbers is said to be one-one reducible to a set B if there is a total computable injective function f on the natural numbers such that [math]\displaystyle{ f(A) \subseteq B }[/math] and [math]\displaystyle{ f(\mathbb{N} \setminus A) \subseteq \mathbb{N} \setminus B }[/math].
Statement
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.
Corollaries
Two total numberings are one-equivalent if and only if they are recursively isomorphic.
Myhill-Shepherdson Theorem
The Myhill-Shepherdson Theorem,[2] stemming from the Rice-Shapiro Theorem, defines the computable type 2 functionals. These functionals operate on computable partial functions, yielding numbers as results in cases of termination. Notably, they adhere to a specific effectiveness criterion and exhibit continuity as functionals.
Considering the notion of the Myhill isomorphism, which states there exists a total computable bijection, which maps elements reducible to each other in both directions, given the functions are extensional, this one specifies the definition for recursive functionals.
Specifically, it states:
1) Let [math]\displaystyle{ \phi: \mathbb{F}(\mathbb{N}^k) }[/math] [math]\displaystyle{ \rightarrow \mathbb{F}(\mathbb{N}^i) }[/math] be a recursive function. Then, there exists a total computable function [math]\displaystyle{ h_\Phi: \mathbb{N} \rightarrow \mathbb{N} }[/math] such that [math]\displaystyle{ \forall e \in \mathbb{N} (\phi_e^k) = \phi_{h_(\Phi)(e)}^{(i)} }[/math]
2) Let [math]\displaystyle{ h: \mathbb{N} \rightarrow \mathbb{N} }[/math] be a total computable function and [math]\displaystyle{ h }[/math] extensional. Then, there is a unique recursive functional [math]\displaystyle{ \phi: \mathbb{F}(\mathbb{N}^k) }[/math] [math]\displaystyle{ \rightarrow \mathbb{F}(\mathbb{N}^i) }[/math] such that [math]\displaystyle{ \forall e \in \mathbb{N} (\phi_e^k) = \phi_{h(e)}^{(i)} }[/math]
Discussion
The theorem implies that given two injective reductions in opposing directions, there is a computable bijection on the naturals that puts the sets in question in bijective correspondence. This is reminiscent of the Schröder–Bernstein theorem about general sets, and Myhill's theorem has been called a constructive version of it.[3] Their proofs are however different. The proof of Schröder-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 Schröder-Bernstein unless one uses the Axiom of Choice (which is not necessary for the proof of the Myhill theorem).
See also
- Berman–Hartmanis conjecture, an analogous statement in computational complexity theory.
References
- ↑ 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.
- ↑ Dekker, J. C. E. (September 1957). "J. Myhill and J. C. Shepherdson. Effective operations on partial recursive functions. Zeitschrift für mathematische Logik und Grundlagen der Mathetnatik, vol. 1 (1955), pp. 310–317." (in en). The Journal of Symbolic Logic 22 (3): 310–317. doi:10.2307/2963619. ISSN 0022-4812. https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/j-myhill-and-j-c-shepherdson-effective-operations-on-partial-recursive-functions-zeitschrift-fur-mathematische-logik-und-grundlagen-der-mathetnatik-vol-1-1955-pp-310317/206E6A95B1689C7C3F1ED8E2E67381D1.
- ↑ 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.
- "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1 (2): 97–108, 1955, doi:10.1002/malq.19550010205.
- Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, 1987, ISBN 0-262-68052-1.
- 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
![]() | Original source: https://en.wikipedia.org/wiki/Myhill isomorphism theorem.
Read more |