Myhill isomorfism teorem

För Goodman–Myhill-satsen i konstruktiv mängdlära, se Diaconescus sats .

I beräkningsbarhetsteorin ger Myhill isomorphism theorem , uppkallad efter John Myhill , en karakterisering för två numrering för att framkalla samma föreställning om beräkningsbarhet på en mängd.

Myhill isomorfism teorem

Mängder A och B av naturliga tal sägs vara rekursivt isomorfa om det finns en total beräkningsbar [[om det finns en total beräkningsbar bijektiv funktion f på de naturliga talen så att för alla $x$ , $x\in A\iff f(x)\in B$ .

En mängd A av naturliga tal sägs vara en-ett-reducerbar till en mängd B om det finns en total beräkningsbar injektiv funktion f på de naturliga talen så att $f(A)\subseteq B$ och $f(\mathbb {N} \setminus A)\subseteq \mathbb {N} \setminus B$ .

Myhills isomorfismsats säger att två mängder A och B av naturliga tal är rekursivt isomorfa om och endast om A är en-reducerbar till B och B är en-reducerbar till A .

Satsen påminner om Schroeder–Bernsteins sats , och har kallats en konstruktiv version av den. Beviset är dock annorlunda. Beviset för Schroeder-Bernstein använder inverserna av de två injektionerna, vilket är omöjligt i inställningen av Myhill-satsen eftersom dessa inverser kanske inte är rekursiva. Beviset för Myhill-satsen, å andra sidan, definierar bijektionen induktivt, vilket är omöjligt i Schroeder-Bernsteins miljö om man inte använder valets Axiom (vilket inte är nödvändigt för att bevisa Myhill-satsen).

En följd av Myhills teorem är att två totala numrering är en-ekvivalent om och endast om de är rekursivt isomorfa .

Se även

• Berman-Hartmanis förmodan , ett analogt uttalande inom beräkningskomplexitetsteori

•   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 rekursiva funktioner och effektiv beräkningsbarhet (2:a upplagan), Cambridge, MA: MIT Press, ISBN 0-262-68052-1 , MR 0886890 .
• Soare, Robert I. (1987), Rekursivt uppräknade mängder och grader: en studie av beräkningsbara funktioner och beräkningsbart genererade mängder, Perspectives in Mathematical Logic, Berlin Heidelberg: Springer-Verlag, ISBN 978-3-540-66681-3, MR 2 18829