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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
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.
In Branch: Computability Theory, Lead sentence
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to
View the SourceReader 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.