Rekursive Isomorphie ist in der Berechenbarkeitstheorie eine Äquivalenzrelation auf Mengen natürlicher Zahlen.
Definition Bearbeiten
Mengen natürlicher Zahlen heißen rekursiv isomorph , falls es eine totale berechenbare Bijektion gibt, so dass gilt.
Nummerierungen einer (höchstens) abzählbaren Menge heißen rekursiv isomorph, falls es eine ebensolche Bijektion mit gibt.
Die Abbildung heißt dann rekursiver Isomorphismus.
Eigenschaften Bearbeiten
- Rekursive Isomorphie ist eine Äquivalenzrelation auf der Potenzmenge der natürlichen Zahlen.
- Insbesondere ist sie transitiv.
- Ist ein rekursiver Isomorphismus, so ist notwendig auch seine Umkehrfunktion berechenbar.
- Eine Menge ist genau dann rekursiv isomorph zum Halteproblem , wenn sie kreativ ist.
- Dies sind außerdem nach unten stehendem Satz genau die RE-vollständigen Mengen.
Isomorphiesatz von Myhill Bearbeiten
Folgender Satz von John Myhill liefert eine Charakterisierung des Begriffes der rekursiven Isomorphie:
Seien erneut Mengen natürlicher Zahlen, so gilt:
Zwei Mengen sind also genau dann rekursiv isomorph, wenn sie one-one-äquivalent sind.
Der Beweis zu diesem Satz ist eine effektive Variante des Beweises des Satzes von Schröder-Bernstein.
In der Theorie der Turing-Grade lässt sich mit Hilfe des Isomorphiesatzes eine weitere wichtige Äquivalenz folgern:
Zwei Mengen befinden sich also genau dann im gleichen Turing-Grad, wenn ihre jeweiligen Turing-Sprünge rekursiv isomorph sind.
Literatur Bearbeiten
- J. Myhill: Creative Sets. In: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik Vol. 1 (1955), S. 97–108.
- H. Rogers: Theory of recursive function and effective computability (2nd ed.). 1987, MIT Press, Cambridge, MA.