Rekursive Isomorphie

Rekursive Isomorphie ist in der Berechenbarkeitstheorie eine Äquivalenzrelation auf Mengen natürlicher Zahlen.

Definition

Mengen $A;B\subseteq \mathbb {N}$ natürlicher Zahlen heißen rekursiv isomorph $A\equiv B$, falls es eine totale berechenbare Bijektion $i\colon \mathbb {N} \to \mathbb {N}$ gibt, so dass $i(A)=B$ gilt.

Nummerierungen $\mu ;\nu \colon \mathbb {N} \to M$ einer (höchstens) abzählbaren Menge $M$ heißen rekursiv isomorph, falls es eine ebensolche Bijektion $i\colon \mathbb {N} \to \mathbb {N}$ mit $\mu =\nu \circ i$ gibt.

Die Abbildung $i$ heißt dann rekursiver Isomorphismus.

Eigenschaften

• Rekursive Isomorphie ist eine Äquivalenzrelation auf der Potenzmenge ${\mathcal {P}}(\mathbb {N} )$ der natürlichen Zahlen.
  • Insbesondere ist sie transitiv.
• Ist $i\colon \mathbb {N} \to \mathbb {N}$ ein rekursiver Isomorphismus, so ist notwendig auch seine Umkehrfunktion $i^{-1}$ berechenbar.
• Eine Menge ist genau dann rekursiv isomorph zum Halteproblem $H$, wenn sie kreativ ist.
  • Dies sind außerdem nach unten stehendem Satz genau die RE-vollständigen Mengen.

Isomorphiesatz von Myhill

Folgender Satz von John Myhill liefert eine Charakterisierung des Begriffes der rekursiven Isomorphie:

Seien $A;B\subseteq \mathbb {N}$ erneut Mengen natürlicher Zahlen, so gilt:

$A\equiv B\Leftrightarrow A\preceq _{1}B\land B\preceq _{1}A$

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:

$A\equiv _{T}B\Leftrightarrow A'\equiv B'$

Zwei Mengen befinden sich also genau dann im gleichen Turing-Grad, wenn ihre jeweiligen Turing-Sprünge rekursiv isomorph sind.

Literatur

• 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.