“Myhill isomorphism theorem”的意思、由来-开放百科全书

词条

Myhill isomorphism theorem

释义

Myhill isomorphism theorem
See also
References

{{for|the Goodman–Myhill theorem in constructive set theory|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 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 reminiscent of the Schroeder–Bernstein theorem. 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).

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

References

{{citation

| last = Myhill | first = John | authorlink = John Myhill
| doi = 10.1002/malq.19550010205
| journal = Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
| mr = 0071379
| pages = 97–108
| title = Creative sets
| volume = 1
| year = 1955}}.

{{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}}.

1 : Computability theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Myhill isomorphism theorem

See also

References