BEMERKUNGEN ZUM SPEKTRALPROBLEM von D. RODDING und H. SCHWICHTENBERG in Miinster (Westfalen) SCHOLZ stellte in [6] das Problem, ob sich fur das System 1131, aller Spektren S ( y ) : = { m I erf,,, g,}, q~ Ausdruck der ersten Stufe (mit Identitat, ohne Funktionssymbole), eine einfache zahlentheoretische Charakterisierung angeben 1aGt. Dieses Problem bleibt ungelost ; wir erhalten jedoch in Verscharfung von Resultaten von ASSER [l] und MOSTOWSKI [4] eine Abschiitzung P r l ( Go) 2 1131, 2 P r l ( el) und allgemeiner Prl( G,) 2 1131,+, C = P r l ( en+,) mit 1131, : = {S(g,) I g, Ausdruck der n-ten Stufe} und Funktionenklassen G, , die eine einigermafien natiirliche Klassifikation der elementaren Funktionen bilden (s. 9 1)l). Insbesondere ergibt sich 1) 1131, enthalt alle Mengen, deren charakteristische Funktion in GRZEGORCZYK'S G2 liegt.
2 ) U, 1131, besteht aus allen Mengen mit elementarer charakteristischer Funktion.
3) !YJln
C '$JInf2 (echte Inklusion). Weiter betrachten wir die Systeme 1131;+,, n 2 1, aller Spektren S (9) von Ausdriicken g, der ,,schwachen n + 1-ten Stufe" (freie Variable n + 1-ter Stufe sind nicht zugelassen). Fur % ; + , ergibt sich die folgende Charakterisierung : Ein (zahlentheoretisches) Pradikat heil3e beschrankt exponentiell arithmetisch (b. e. a.), wenn es aus den Pradikaten x + y = z , x * y = z , 29 = y mit Hilfe von Variablen fur natiirliche Zahlen, 1, A , h explizit definiert werden kann2). Dann besteht 1131;+, aus X<?/ allen Urbildern b. e. a. Mengen unter Funktionen der Form 2 m 8, ( ( m + r 2 1, mit Go(x) : = x , Gi+, ( x ) : = . Q 1. Eine Klassifikation der elementaren Funktionen Die im folgenden verwendete Klassifikation der elementaren Funktionen wurde in [5] eingefiihrt und diskutiert. Wir stellen hier die spater benotigten Definitionen und Satze zusammen. Eine (zahlentheoretische) Funktion heiGt elementar, wenn sie explizit definiert werden kann mit Hilfe von Variablen fur natiirliche Zahlen, der Konstanten 1, den Funktionen +,und [xly] und den Operationen 2 , 17 ; die Klasse der ~ X Z J X<Y elementaren Funktionen bezeichnen wir mit 6. Einfache AbschluBeigenschaften Mit Pr7(5) (Pr(&)) bezeichnen wir die Klasse aller r-stelligen (aller) Priidikate mit charakteristischer Funktion in 5. 2, Nach Resultaten von BENNETT (die uns aus einer Bemerkung in [S, p. 921 bekannt sind) stimmt die Klasse der b.e.a. Pradikate mit der Klasse der beschriinkt arithmetischen Priidikate (ohne 22 = y) und mit der der rudimentiiren Priidikate im Sinne von SMULLYAN [S] iiberein.
1 ztschr. f. math. Log&