ZERLEGUNG MIT VERGLEICHSBEDINGUNGEN EINER GODELNUMERIERUNG
roil BRITTA SCHINZEL in Darmstadt (BRD)
1. Einleitende Definitionen
Die Kategorie der Aufzuhlungen der einstelligen partiell rekursiven Funktionen P, enthalt als Objekte die Aufztihlungen (9, PI ) , wo P, die aufgezahlte Menge und v: N -+ P, eine totale effektive Funktion ist. Fur jedes u E P, heifit p-l(u) die Faser iiber a. Morphismen von einer Aufzahlung (p, P, ) = Q! in eine Aufzahlung ( y , PI ) = y sind effektive Abbildungen von N in N, also partiell rekursive Funktionen f , fur die y = y . f gilt fur alle Elernente des Definitionsbereichs von f . Sie werden auch ubersetzer genannt. Endliche Summen von Aufzahlungen Q! und y werden definiert durch Sci gegeben eine rekursiv aufzahlbare Familie von Aufzahlungen von P, , {pi}iEN, danri ist die direkte Summe 0 pi = 7c definiert durch i e N Die*e Summe erfullt die universelle Eigenschaft von Summen in der Kategorie der dnfziihlungen uber P, . Wir betrachten nun spezielle Objekte dieser Kategorie : Eine Godelnumerierung Q! ist definiert durch : (a) dns Aufzahlungstheorem (es gilt fur jede Aufzahlung) : 35: Vy, z : pz(y, z) = Q!,(z), (b) das s:-Theorem (es genugt das sj-Theorem): 3; E R,: Vx, y, z : pz(y, z ) = ysLl(,,!!)(z).
(a) und (b) sind ayuivalent mit der Existenz von ubersetzern von p in eine Standard-g6rlelnumcrieruiig und umgekehrt. H. ROGERS zeigt in [3], da13 alle Godelnumerierungen rckursiv isomorph sind. Frierlberg?i.rcmerierungei~ sind bijektive Aufzahlungen von P, , d. h., sie haben einelenientige Fasern. Ihre Existenz wurde von R. FRIEDBERG in [1] bewiesen. Gibt es zwiwhen zwei Friedbergnumerierungen einen Obersetzer, so sind sie aquivalent, d. h., es existieren Obersetzer in beiden Richtungen. M. B. POUR-EL zeigt in [2], daD es tcn-eergleic7Lbare Friedbergnumerierungen gibt, d. h. solche, zwischen denen kein Ubersetzer existiert. I n [4] wurde gezeigt, dal3 jede Godelnumerierung in paarweise unvergleichbare Friedbergnumerierungen effektiv zerfallt.