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

Definition

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

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

Die Abbildung ${\displaystyle i}$ heißt dann rekursiver Isomorphismus.

Eigenschaften

• Rekursive Isomorphie ist eine Äquivalenzrelation auf der Potenzmenge ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ der natürlichen Zahlen.
  • Insbesondere ist sie transitiv.
• Ist ${\displaystyle i\colon \mathbb {N} \to \mathbb {N} }$ ein rekursiver Isomorphismus, so ist notwendig auch seine Umkehrfunktion ${\displaystyle i^{-1}}$ berechenbar.
• Eine Menge ist genau dann rekursiv isomorph zum Halteproblem ${\displaystyle 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 ${\displaystyle A;B\subseteq \mathbb {N} }$ erneut Mengen natürlicher Zahlen, so gilt:

${\displaystyle 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:

${\displaystyle 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.