ENUMERATIONEN I N SPEZIELLEN STmTDARDKLASSEN REKURSIV-AUFZBHLBARER MENGEN von HANS-DIETRICH HECKER in Grcifswald (DDR) Einleitung I n den Arbeiten 141, [7] und [ l l ] haben P. YOUNG und andere eine Theorie der Enumerationen von rekursiv-aufzahlbaren Mcngen mtwickelt. Wir habeii entsprechende Enumerationen aueh im Zusammenhang mit Approximationen partie1l-rekui.siver Funktionen durch endliche Funktionstabellen (IS]) untersucht. Andererseits hat A. LACHLAN ([S], [9]) sogenannte speziellc Standardklassen von rekursiv-aufzalilbaren Mengen studiert. fur die die Menge der Graphen der einstelligen partiell-rekur+en Funktionen ein Beispiel liefert. Wjr werden im folgenden Enuinerationseigenschafteri fur solche vpezielle Standardklasscn untersuchen. $ 1. Spezielle Standardklassen Wir verwenden folgende Bezeichnungen: Es sci N die Menge der natiirliclicn Zahlen, R das System der rekursiv-aufzlhlbaren Mengen naturlicher Zahlen und P das System der n-stelligen partiell-rekursiven arit,hmetischen Funktionen. Fiir Pl sehreihen wir auch cinfach P. Fiir p E P und z E N schreiben wir p(x)J, falls p an der Stelle :G definicrt ist. Sonst schreiben wir p(.r)t. Mit A" bezeichnen wir das System der ri-stclligen allgemein-rekursiven arithmetischen Funktionen. Mit, n bzw. ~t bezeichnen wir die Post-hzw. Kleenenumerierung der Mengen R bzw. P. Die Funktionen aus P identifizieren wir gewohnlich mit ihrem Graphen, genauer niit, der Menge der Kummern ( 2 , p(z)> bei einer gegebenen rekurxiven eineindeutigen Abbildung ,,(, >" voii N x N auf N. Damit wird P eine Teilmenge von R . Mit Z(,n) hzw. r(n) bezeichiien wir die linkc bzw. rechte Koordinate des Paares mit der Xummer n. Es gilt also fur alle n E N die Beziehung (Z(n), r ( n ) ) = n. Analog betrachten wir cine effektive Numerierung (, . . . ,) aller n-Tupel naturlicher Zahlen (11. 2 2), fur die wir fur alle m E N, 2 5 711 5 12, und alle naturlichen Zahlen r l , . . . , x,, der Einfachheit halber die Gultigkeit der Beziehung <(zl, . . ., x,,,), x , , , + ~, . . ., x,,) = (xl, . . ., x,,) voraussetzen. AuBerdeni verwenden wir einige Begriffsbildungen sus der Numerierungstheorie. Ein System K von rekursiv-aufzahlbaren Mengen heil3e spezielle Standardklasse (SSK), wenn cin stark aufzahlbares System E endlicher Mengen existiert, fur das gilt : a) 0 E E. b ) R E K e . R E R und es gibt eine wachsende Folge (Fi)isN von Mengen a.us E mit Wir geben zuniichst die folgende Cliarakterisierung der SSK an : S a t z 1.1 ([S], [9]). Ein System K 5 R ist genau dann eine spexielle Standardklasse, a) 1st z ( x ) = n,, E K, so i s t ngi.r.) = n,. (x E N). b ) Fur jedes x E N ist ng"() E K,