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:\mathbb{N}\to \mathbb{N}$ gibt, so dass $i(A)=B$ gilt.

Nummerierungen $\mu ;\nu :\mathbb{N}\to M$ einer (höchstens) abzählbaren Menge $M$ heißen rekursiv isomorph, falls es eine ebensolche Bijektion $i:\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 $𝒫(\mathbb{N})$ der natürlichen Zahlen.
  • Insbesondere ist sie transitiv.
• Ist $i:\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\iff A{⪯}_{1}B\wedge B{⪯}_{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\iff A^{\prime }\equiv B^{\prime }$

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.