The Myhill Isomorphism Theorem, published by John Myhill in his 1955 paper Creative Sets, states that two sets of natural numbers are computably isomorphic, meaning related by a computable bijection of the natural numbers to itself, exactly when each is one-one reducible to the other. The theorem is often described as a constructive, computability-theoretic counterpart to the Schroder-Bernstein theorem of set theory, giving a precise criterion for when two computability structures on a set are essentially the same.
Facts
StatementTwo sets of natural numbers A and B are computably isomorphic, meaning related by a computable bijection of the natural numbers, if and only if A is one-one reducible to B and B is one-one reducible to A. 1 Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
In Branch
Source Myhill isomorphism theorem, Wikipedia
Principal Result Of
Source John Myhill (Wikipedia)
Proved By
Source Myhill isomorphism theorem, Wikipedia
Sources
1. Myhill isomorphism theorem, Wikipedia
Formal statement section
Two sets A, B ⊆ ℕ are computably isomorphic if and only if A is one-one reducible to B and B is one-one reducible to A.
References section, Myhill 1955 citation
Myhill, John (1955), Creative sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1 (2): 97-108.
Proved By: John Myhill, Lead sentence
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.
In Branch: Computability Theory, Lead sentence
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to
In Group: Computability and Complexity Theory, Lead section
In computability theory the Myhill isomorphism theorem, named after John
View the SourceJohn Myhill (Wikipedia)
Principal Result Of: John Myhill, Contributions, isomorphism theoremQuote, Principal Result Of: John Myhill, Contributions, isomorphism theorem
The Myhill isomorphism theorem is a computability-theoretic analogue of the Cantor-Bernstein-Schroeder theorem that characterizes the recursive isomorphisms of pairs of sets.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.