Rekursive Isomorphie
# 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.

