Upload
hilbert-levitz
View
215
Download
2
Embed Size (px)
Citation preview
llJber die FINSLERschen hiiheren arithmetischen Operationen
Von HILBERT LEVITZ*, New York University
1. Einleitung
In [4] stellte Finsler eine transfinite Folge von arithmetischen Operationen auf, die durch Funktionen 6~(~, t/) von zwei Variabeln ~, r/ gegeben sind, wobei c~, ~, r/ alle Ordnungszahlen kleiner als s'2 durchlaufen. Die kleinste Zahl /a, die die Gleichung 6~ (to, to) = x l/Sst, spielt eine besondere Rolle. Ist to < 2, </~, dann hat ~ die Darstellung 7=6~(~, t/), wobei ~, 4, r/<7 sind.
Bachmann [2] zeigte, dass/~ < E(0) ist, wobei E(0) eine bestimmte Zahl ist, die von Veblen [7] beschrieben wurde.
Hier geben wir eine Verbesserung dieses Ergebnisses von Bachmann. Wir beweisen, dass/~ gerade die sogenannte Schiitte-Feferman Zahl Xo ist. Es wurde von diesen Ver- fassern gezeigt, dass x o eine wichtige Bedeutung fiJr die verzweigte Typenlogik hat
[31, [51, [61. Wir beweisen auch: 6~(~, t/)<Xo so bald ~, r r/<~c o.
2. Die Operationen von Finsler
Die v-fache Iteration der Funktionen 6~(~, r/) sei durch die Forderungen erkl/irt:
6; +' (r ~) = 6~(r 6; (~, ~))
6~ (r r/) = Lim 6; (3, r/), wenn ), eine Limeszahl < f2 ist.
Man beweist sehr leicht mit transfiniter Induktion nach fl:
6; § (3, ~) = 6~ (3, 6; (r ~)). )
Die Funkt ionen 6,(4, t/) sind definiert, wie folgt:
60 (r ,1) = 60 (o, ,7) = ,7 + 1
6 , (~,n) = 6~o(0,,7) = ~ +
62 (r ~) = 6~ (,7, o) = ,r r
*) Diese Arbeit wurde yon dem Office of Scientific Research of the United States Air Force unter- sti.itzt.
274 H I L B E R T L E V I T Z
r (~, ~) = $~ (~, 1) = rlr
= u s w .
allgemein q~+l (~, t/) = r162 (r/, ~/) fiir ct > 3
q~x (~, r/) = Lim ~b~ (~, r/), wenn 2 eine Limeszahl < f2 ist. ~t<).
3. Einige Eigenschaften der Normalfunktionen
Wir beschreiben einige Eigenschaften der Normalfunkt ionen wie es in Bachmann steht [1, w 8].
Es sei ~b(x) eine beliebige Normalfunkt ion mit dem Argamentbereich 0 < x < f2. Die Iteration ~b n von ~k definiert man folgendermassen:
=
( r - _
Wenn die LSsungen der Gleichung ~k(x)=x der Gr6sse nach geordnet werden, erh~ilt man eine neue Normalfunkt ion, die man die Ableitung ~b' von ~b nennt. Es gilt [1, pg. 36]:
~b'(0) = Lim ~"(ct) fiJr ~t < ~k'(0), (1) n < t o
~ ' (~ + i) -- Elm ~k"(ct) fiJr ~b'(~) < Qt < ~b'(~ + 1). (2)
Ist 0 < ct < ~k' (fl), so ist ~b (~t) < ~b' (fl) fiir 0 < fl; dies ergibt sich aus ~k (~) < ~k (~k' (fl)) =
Ausgehend von der Normalfunkt ion fo (x)-- to x, 0 < x <f2, bildet man eine trans- finite Folge yon Ableitungen {f~}, wie folgt:
f , + , = f , ' ftir 0 < r / < f ~ ,
Vf~ = 0 Vf~, tl < ;L
wenn ,~ eine Limeszahl <12 ist und Vf~ die Wertbereich der Funktion f~ bezeichnet. Es gilt [1, pg. 39]:
f~+ 1 (0) = Lim f~ (~t) fiJr ct < f~+l (0), (3) t l < t o
f~+l (~ + 1) = Lim f~(~t) fiir f~+l (~) < ~t < f~§ (~ + 1), (4) / l < t ~
12ber die FINSLERschen h6heren arithmetischen Operationen 275
fa (0) = Lim f , (~) for ct < fa (0), (5) r/<Z
wenn ;t eine Limeszahl ist.
fa(~ + 1) = Lim f~(~) fur f~(~) < ~t < fa(r + 1), (6) q<).
wenn 2 eine Limeszahl ist. Eine weitere Eigenschaft vonf~ i s t f , (x) >/x [1, pg. 25]. Fiir 1 <r/, 0 < ~ istf,(ct) eine e-Zahl. Deshalb ist ftir 1 <~/die Menge von allen Ord-
nungszahlen, die kleiner als f,(ct) sind, gegeniiber den Operationen von Addition, Multiplikation, und Potenzbildung abgeschlossen [1, p. 68].
Die kleinste L~Ssung der Gleichung f~ (0)= x heisst die Schiitte-Feferman Zahl. Um eine biindige Bezeichnungsweise zu gewinnen, fiihren wir eine Gr6sse - 1 ein.
Fiir - 1 definieren wir folgendes:
- l < x fiir 0 < x ,
l x fiir ~o _< x , - l + x = - 1 ffir x = O ,
r/ far 0 < x < o9 und x = r /+ 1,
1 + ( - 0 = 0 , ~k ( - 1) = ~o, wenn ~, irgendeine Normalfunktion ist.
Offenbar gilt:
- 1 + ( ~ t + f l ) = ( - 1 + a ) + f l fiJr a, f l > O ,
1 + (fl + x) = (1 + fl) + x fiir fl > - 1 , x > O,
oJ.(1 + fl) + o~.x = co.(1 + fl + x) fiir fl > - 1,x >_ O.
4. Einige Hilfsiitze
HILFSATZ 1. Es ist ~bs(co'x, f l ( f l ) ) = f l ( f l + x ) fiir alle fl>_ - 1 , x>0 . Beweis: Nach der Definition der FINSLERschen Operationen gen~igt es zu zeigen:
q~'~( f l ( f l ) , f~( f l ) )=fx( f l+7) fiJr alle f l > - 1 , 7 > 0 .
Dies wird mit transfiniter Induktion nach ~ bewiesen: Fall 1. y=O:
~ : ' ~ (f~ (fl), f t (fl)) = ~o (f~ (fl), f~ (fl)) = f~ (fl) = f l (fl + O) = f l (fl + Y).
Fall 2. y = v + 1, d.h. y sei ein Nachfolger: Die Induktionsvoraussetzung lautet
~: .v (f~ (fl), f~ (fl)) = fx (fl + v) ;
276 H I L B E R T L E V I T Z
daraus folgt
~b: ~ (f~ (fl), f~ (fl)) = ~b~ ,+o, (fx (fl), f , (fl)) =
= ~ ' ( f t ('8), gb~" ( f , (fl), fx (fl))) =
= q~' 0"1 ('8), f t ('8 + v)) = Lim ~b]. ( f l ('8), f~ (fl + v)). n < t o
Nun zeigen wir mit Indukt ion nach n>_ 1, dass
~b~ (f~ ('8), f l ('8 + v)) = f0 (Q), wobei
f ~ - l ( f l ( , 8 + v ) + l ) < Q < f l ( , 8 + v + l ) i s t .
Ist diese Behauptung wahr, dann folgt
f ~ ( f t ( ' 8 + v) + 1) < fo(Q) = dP](fl( f l) , fx( '8 + v)) < f1('8 + v + 1).
Im Falle '8 + v = - 1 folgt nach (3), im Falle '8 + v g: - 1 nach (4)
Lim ~b] ( f t ('8), f l ('8 + V)) = Lim (f l ('8 + v) + 1) = f t ('8 + v + 1) = f l ('8 + Y); n < t o n < t o
weiterhin ergibt sich nach (7), (8)
q ~ ' r (f~ (fl), f~ (fl)) = f l ('8 + )').
Abet das ist, was bewiesen werden soll. Fall2.1 n = l : Fall2.1.1 ' 8 = - 1 , v = 0 :
4~,] ( f , ('8), f , ('8 + v)) = q54 (co ' ' ' ) ) = fo (co').
Setzt man Q = w '~ so hat Q die erforderlichen Eigenschaften:
f ~ - l ( f l ( , 8 + v ) + 1 ) = f ~ 1 ) = f x ( , 8 + v ) + 1--
= co + 1 < Q < f l ( O ) = f1( '8 + v + 1).
Fall 2.1.2 'sg: - 1 oder v#O: Dann ist '8 + v g: - 1, und fo ( f l ('8 + v)) =fx ('8 + v), d.h.
o~II (#+~) = fa ('8 + v); also
�9 4~]( f , ( '8) , f , ('8 + v)) = ~b~(f, (f l) ,fa ('8 + v)) = ( f , (/3 + v) (z' (#+,)S, (#))) =
= (oaS , (#+,))(s , (#+,) s' (#)) = o~(S , (#+,)s , (#))
Setzt man Q =fx ('8 + v) s' (#), dann ist
fg-i (fl ('8 "I" V) "at- I) = fl ('8 + v) + 1 < f, (,8 + vy' (#) = Q < fl ('8 + v + I).
(7)
(8)
Ober die FINSLERschen h6heren arithmetischen Operationen 277
Fall2.2 n = k + l , k # 0 : Die Induktionsvoraussetzung nach n lautet fiJr k <n :
wobei
Also gilt
tk k ( f , (fl), f , (fl + v)) = fo (P) ,
f ~ - ' ( f , ( f l + v) + 1) < P < f , ( f l + v + 1). (9)
sk+, ( f , (fl), f , (13 + V)) = ~b,, ( f , (fl), ~b~ (f , (fl), f t (fl + v))) = 4
= ~b4 ( f (fl), fo (P)) = fo (p)(:o (e)Y' (")) =
(0) (#)). =(coe)(:o a'):' (#)) = ~e . :o te):' = fo ( P ' f o (P) :~
Setzt man Q = P . f o ( P ) :x (#), dann hat Q die erforderlichen Eigenschaften, denn wegen (9) gilt
f k ( f , ( f l + V) + 1) < f o ( P ) < f , ( f l + v + 1),
aber f t (fl + v + 1) ist eine e-Zahl, und daraus folgt
f k ( f , ( f l + V) + 1) < P ' f , ( P ) : ' ( # ) = Q < f , ( f l + v).
Fall 3. 7 sei eine Limeszahl: Nach der Induktionsvoraussetzung nach 7 erh/ilt man
4)~" ' ( f l (fl), f t (fl)) = Lim ~ a ( f I (fl), f , (fl)) = Lim f l (fl + 2) = f , (fi + 7). 2<}' ).<y
Damit ist der Beweis von Hilfsatz 1. beendet.
HILFSATZ 2. Ist ~b,(~, r/) eine F INSLERsche Operat ion und g(x) eine Normal- funktion mit den Eigenschaften:
a) ~b~(og.x, g ( f l ) ) = g ( f l + x ) f i i r alle x_>0, f l> - 1 , b) g(x) ist eine e-Zahl fiir x>_0,
dann gilt: dp~+2(t.o'x,g'(fl)) = g'(fl + x) ftir x _> 0, fl > -- 1.
Beweis: Zuerst beweisen wir mit transfiniter Induktion nach y die folgende Be- hauptung:
~b_r(o~,t~) = g ( - 1 + ?) fiJr alle ? > 0. (10)
Fall 1. 7 = 0 :
~ (co, co) = ~b ~ (co, to) = co = g ( - - 1 + O) = g ( - 1 + y).
278 HILBERT LEVITZ
Fall2. y = v + l : Naeh der Indukt ionsvoraussetzung ist
~; (,o, co) = g ( - I + v) , also
~b~ (co, co) = q~*_ +' (co, co) = ~b, (60, ~b ~ _ (co, co)) = ~b, (co, g ( - 1 + v)).
Nach der Voraussetzung a) ist ~,(co, g( - 1 + v)) = g ( ( - 1 + v) + 1), also
q~(co, co) = g ( ( - 1 + v) + 1) = g ( - 1 + (v + 1)) = g ( - 1 + y).
Fall 3. Y sei eine Limeszahl:
~b~ (co, co) = Lira ~b~ (co, co) = Lira g ( - 1 + 2) = g ( - 1 + 7). ),<)' 2<y
Damit ist (10) bewiesen. Aus (10) ergibt sich nach der Definition der F INSLERschen Operat ionen
q~,+x (Y, co) = g ( - 1 + y) fiir alle 7 >- 0.
Sodann beweisen wir mit transfiniter Indukt ion nach 7
b-~ (g (P), g (P)) = g (P + g (//) '7) fiir alle 7 > 0 , / / ~ - 1.
Fall 1. y = 0 :
q~ (//, g (//)) = q~O (g (fl), g (fl)) = g (fl) = g ( / / + g (fl) '0) = g (fl + g (fl)" y).
Fall2. y = v + l : Aus fl ~ 1 und Voraussetzung b) folgt co.g(//)=g(//), also
~; (g (//), g (//)) = ~; + ' (g (//), g (//)) = ~, (g (//), ~; (g (//), g (//))) �9
Nach der Indukt ionsvorausse tzung ist
~b~ (g (//), g (//)) = g (fl + g (fl). v), also
~ , (g (//), ~; (g (//), g (//))) = ~ , (g (//), g ( / / + g (/ /) . v)) = ~, (co.g (//), g ( / / + g (/ /) . v)) .
Ferner ist nach der Voraussetzung a)
q~, (co-g (//), g ( / / + g (fl). v)) = g ( / / + g (fl). v + g (fl)) = = g(fl + g(//) .(v + 1)) = g(fl + g(f l ) '7) .
Fall 3. 7 sei eine Limeszahl:
4), r (g (fl), g (//)) = Lim q~ (g (//), g (//)) = Lim g ( / / + g (//). 2) = g ( / / + g (//). 7). 2<y ~<~
Dami t ist (12) bewiesen.
(11)
(12)
l~ber die FINSLERschen h6heren arithmetischen Operationen
Aus (12) ergibt sich nach der Definition der FINSLERschen Operationen
~b,+l (Y, g (8)) = g (8 + g (8)'Y) ftir alle y >__ 0, 8 ~ - 1.
Sodann beweisen wit mit transfiniter Induktion nach 7:
tk,+l (g (8), g (8)) = g' (8 + 7) fiir alle y > 0, 8 > - 1.
Fall l. y=O
~b~'+ ~ (g' (8), g'(8)) = q5~ (g' (fl), g' (fl)) = g' (fl) = g ' (8 + 0) = g'(8 + Y).
Fall2. y = v + l :
~b~'~ ~ (g' (8), g' (8)) = ~'+ ~+ ~ (g' (8), g' (fl)) = ~b~+l (g' (8), ~ '~ [ (g' (8), g' (8)))
Nach der Induktionsvoraussetzung folgt
q~'+ ~ (g' (fl), g' (fl)) = g' (8 + v), somit
q~+l (g' (8), ~b~+ [ (g' (8), g' (8))) = ~b~'+ 1 (g' (8), g' (8 + v))
= Lira qS," +1 (g' (8), g' ( / / + v)) n < t o
Fall2.1 8 = - 1 , v = 0 : Wir zeigen mit Induktion nach n >_ 1 :
~,+x (g ' ( f ) , g ' ( 8 + v) = g(Q),
279
(13)
(14)
wobei g " - ' (0) < Q < g' (0).
Ist diese Behauptung wahr, so gewinnen wir durch Anwendung von (1) die gewtinschte Beziehung (14).
Fall 2.I.1. n = 1 : Nach (11) folgt
~b~ +, (g' (fl), g' (fl + v)) -- ~b~+, (co, co) = g ( - 1 + co) = g (co).
Setzt man Q = co, so hat Q die erforderlichen Eigenschaften, denn
g n - , (0) = gO(0) = 0 < co --- Q < g ' ( 0 ) .
Fall2.1.2. n = k + l :
~,~ ~ (g' (8), g' (8 + v)) = ~ , + , (g' (8), ~*,+, (g' (8), g' (8 + v))).
Da aber die Induktionsvoraussetzung nach n fiir k < k + 1 = n
ck*•+ l (g' (fl),g' (8 + v)) = g(P)
lautet, wobei g~-' (0) < P < g'(0) (15)
2 8 0 H1LBERT LEV1TZ
gilt, folgt
~, +1 (g' (fl), ~b~ +1 (g' (fl), g' ([3 + v))) = c~,,+1 (g' (fl), g (P)) = ~b~,+ l (to "g (P)).
Wegen (15) ist P # 1, deshalb ist (13) anwendbar, und man erh~ilt
~b~ +1 (co, g (P)) -- g (P + g (P). co).
Setzt man Q = P + g (P)- ca, so gilt nach (15) gk(0) < g (P) < g' (0).
Ferner gilt
g"-~ (0) = gk (0) < P + g (P).co = Q < g' (0),
weil g ' (0) eine ,-Zahl ist. Fall 2.2 / / # - 1 oder v # 0: Wit zeigen mit Induktion nach n > 1 :
qb~+l(g'(fl),g'(fl + v)) = g(Q), wobei g , - l ( g , ( f l + v) + 1) < Q < g'(fl + v + 1).
Ist diese Behauptung wahr, so gewinnen durch anwendung yon (2) die gewtinschte Beziehung (14).
Fall2.2.1. n - - l : Aus fl + 1 ~ - 1 ergibt sich g(g ' (fl + v)) = g' (fl + v), also
~b,+ 1 (g' (fl), g' (fl + v)) -- ~b,+ t (g' (fl), g (g' (fl + v))).
Ferner ist (13) anwendbar , und man erh~ilt:
q~,+l (g' (fl), g (g' (fl + v))) = g (g' (fl + v) + g (g' (fl + v))" g' (fl)).
Setzt man Q=g ' (~+v)+g(g ' ( f l+v ) ) . g ' ( f l ) , dann hat Q die erforderlichen Eigen- schaften, denn
g, ,- l(g,( f l + v) + 1) =gO (g,(fl + v) + 1) = g'(fl + v) + 1 < Q < g'(fl + v + 1).
Fall 2.2.2. n = k + 1 : Die Induktionsvoraussetzung nach n lautet f~ir k < k + 1 = n:
q~k +1 (g' (fl), g' (8 + V)) = g (P) ,
wobei
gk- l (g, (fl + v) + l ) < P < g, (fl + V + 1) (16)
ist. Es folgt
@k+l (g, (fl), g, = +1 (fl + v)) ~ +l (g' (fl), ~ bk (g' (fl), g (fl + v))) = q~ +1 (g' (fl), g (P)) .
Aus (16) ergibt sich P 4 - 1, deshalb ist (13) anwendbar , und man erh~ilt
~b~ +1 (g' (fl), g (P)) = g (P + g' (P)" g' (fl)).
Ober die FINSLERschen h6heren arithmetischen Operationen 281
Setzt man Q =P+g'(P).g'(fl), dann hat Q die erforderlichen Eigenschaften, denn aus (16) folgt
Q
gk(g,(fl+v)+ 1 ) < g ( P ) < g ' ( f l + v + 1),
und da g'(fl+v+l) eine e-Zahl ist, folgt weiter:
g ' - ' ( g ' ( ~ + v) + 1) = gk(g , (~ + v) + 1) < e + g(P) .g ' (V) < g'(fl + v + 1).
Fall 3. ~ sei eine Limeszahl:
~b~ ~ (g' (fl), g' (fl)) = Lim q5~'~ ~ (g' (fl), g' (fl)) = Lim g' (fl + 2) = g' (fl + ?). 2<~, A<~
Damit ist (14) bewiesen. Aus (14) ergibt sich nach der Definition der FINSLERschen Operationen
~b~ +z (~o-~,, g' (fl)) = g' (fl + ~) fiir alle 7 > 0, fl > - 1.
Damit is der Beweis yon Hilfsatz 2 beendet.
HILFSATZ 3. Ist ~b~(~, rl) eine FINSLERsche Operation und h(x) eine Normal- funktion mit den Eigenschaften:
a) c~,,(x, h(fl))=h(fl+x) fiir alle x > 0 , f l> - 1 , b) g(x) ist eine e-Zahl fLir aUe x > 0 ,
dann gilt:
d?~+2(~o.x,h'(fl))=h'(fl+x ) fiir alle x>_O, f l > - l .
Beweis: Wir definieren eine Funkt ion g, die die Bedingungen von Hilfsatz 2 er- fiillt. Sei g (fl) - h ( - 1 + co (1 + fl)) fiir fl > - 1. Offenbar ist g eine Normalfunktion, und fiir x>_0 ist g(x) eine e-Zahl; ferner hat man fiir x > 0 , fl>_ - 1:
dp~(co.x,g(fl)) = q~(oa.x,h(- 1 + co(1 + fl))) = h ( - 1 + o9(1 + fl) + cox) =
= h ( - l + t o ( 1 + f l + x ) ) = g ( f l + x ) ,
gem~iss Hilfsatz 2 erh~ilt man
~b~ (o~. x, g' (fl)) = g' (fl + x) ftir alle
Es ist leicht zu sehen, dass
g' (fl) = h' (fl) fiir alle
gilt. Somit haben wir
~ (m" x, h' (x)) = h' (fl + x).
x~O, f l 2 - 1 .
- l <_fl
(Q.E.D.)
282 HILBERT LEVITZ
3. Die Hauptergebnisse
Ffir x > 0 besteht der Wertbereich der Funkt ion o9(1 + x ) aus den Limeszahlen. Jeder Limeszahl ~ ordnen wir eine Zahl 0, und eine Folge {r/,} fiir 1 <_ / < 0, zu, so dass fiir alle ~, ~ = Lim r/ gilt. Ferner verlangen wir die folgenden Eigenschaften :
I<0ez
a) Ist ~=o9, sei 0,=o9 und r/, = 2 t + 3 ; b) Ist ~ = 2 + w , wobei 2 eine Limeszahl ist, sei 0 , = w und t / , = 2 + 2 t + 1; c) Ist ~ = w. 2, wobei 2 eine Limeszahl ist, sei 0, = 2 und r/, = o9.1 + 3.
SATZ 1. Sei {f~} die vorher beschriebene Folge von Ableitungen: a) Ist ~ = 2 n + 3 , l < n < w , dann gilt
~ , (re.x, f , (/~)) = f , (,8 + x) fiir aile x > 0,/~ >_ - 1.
b) Ist ~ = X + 1, wobei 2 eine Limeszahl ist, dann gilt
~b. (x, fa (fl)) = f~ (fl + x) fiir alle x _> 0, fl > - 1.
c) Ist ~ = 2 + 2 n + 1, wobei 2 eine Limeszahl und 1 < n < co ist, dann gilt
~b.(og.x, fa+ . (p) ) = f:,+.(fl + x) fiir alle x > 0, fl > - 1.
d) Ist ~ eine Limeszahl, dann gilt
dp~(f,(fl),f~(fl)) = f~(fl + x) fiJr alle x > 0, fl _> - 1.
Beweis (Nach transfiniter Induktion nach a) Wir nehmen an, dass a), b), c), d) fiir alle a ' < �9 gelten. Wir mtissen zeigen, dass a), b), c), d) auch fiir c{ gelten
a) Sei a = 2 n + 3 , l_<n<og. Fall 1. n = l :
Unsere Behauptung ist genau Hilfsatz 1. Fall2. n = k + l , k=/=0:
Hier gilt nach Induktionsvoraussetzung a):
~b2k+ 3 (co "x, f . (fl)) = fk (fl + x) far alle x > 0, fl > -- 1.
Also folgt nach Hilfsatz 2
~D2n +3 (03" x , fn (~) ) = ~2k +3 +2 (o9" x , f k +1 (fl)) ~--- A +1 (]~ "1- X) = f , (/~ + x)
fur alle x > 0 , / ~ > - 1 . b) Sei ~ = 2 + 1, wobei ;t eine Limeszahl ist.
Nach der Induktionsvoraussetzung b) gilt
q~ (f~ (/~), fa (/~)) = fa (/7 + x) ftir alle x > 0,/~ > - 1,
1Dber die FINSLERschen h6heren arithmetischen Operationen 283
also folgt nach der Definition der FINSLERschen Operattonen
ckx +1 (x, f~ (/~)) = fa (13 + x) ftir alle x > 0,/~ _> - 1.
c) Sei c t = 2 + 2 n + 1, wobei 2 eine Limeszahl und 1 _<n<ro ist: Fall I. n= l : Nach Induktionsvoraussetzung b) gilt
~x+t (x, fx (fl)) = fx (fl + x) fi~r alle x > 0, fl > - 1,
also folgt nach Hilfsatz 3
rkz+3(~o.x, f x + ~ ( ~ ) ) = f x + t ( 8 + x ) fiir alle 2 > _ 0 , 8 _ > 1 .
Fall 2. n = k + l , k # 0 : Nach induktionsvoraussetzung c) gilt
q~x+2k+~(CO.x, f x + k ( 8 ) ) = f ~ + ~ ( 8 + X ) ftir alle x___0 ,8>_- - I
also folgt nach Hilfsatz 2
(J~. + 2n +1 ((/)"X, f;. +n (8)) = ~x + 2k +3 ((D "X, f 2 +k +1 ( 8 ) )
= f x + k + ~ ( 1 3 + x ) = f x + , ( / 3 + x ) f i i ral le x > _ 0 , 1 3 > _ - l .
d) Sei 0t eine Limeszahl, dann zeigen wir durch transfinite Induktion nach x, dass d) ftir a gilt.
Fall 1. x=O:
qb: (f~ (fl), f~ (8)) = f b~ (f~ (8), f , (8)) = f~ (8) = f~ (fl + O) = f~ (fl + x).
Fal l2 . x = v + l : Die lnduktionsvoraussetzung d) nach x fiir v < v + 1 = x lautet:
~b~-(f~(8),f~(8)) = f~(8 + v) fiir alle 8 > - 1. Daraus folgt
q~: (f~ (/~), f~, (8)) = (k: +1 (f,, (/~), f~ (fl)) =
= ~, (f , (8), ~b~ (f , (fl), f , (8))) = 4 , ( f , (fl), f , (8 + v)), ferner
~b~ (f~ (8), f~ (8 + v)) = Lim ~b,, (f~ (8), f~ (8 + v)) l<Oa
Fall 2.1 8 + v = - 1, d.h. 8 = - 1, r = 0 undf~(8 + v) = ~o ftir alle 7 > 0, undf~ (8) = o~.
In diesem Falle
~b,,(f~(/~),f~(8 + v)) = ~b,,(co.fr(8 + v)) ftir irgendeine r > 0. (17)
2 8 4 HILBERT LEVITZ
Fall 2.1.1. 0t=to: Dann hat man gem/iss der Definition von r/,, r/, = 2 1 + 3 < 0 t . Nach (17)und nach
der Induktionsvoraussetzung a) nach ~, angewandt auf r/, < ~, gilt
~ , ( f . (fl), f~ (B + v)) = q~,, (to, jr, (ff + v)) =
= 2,+3(to, L ( 8 + v)) = f , ( 8 + v + 1) = f , ( 0 ) , also folgt
Lim ~,~,( f . ( f l ) , f . (8 + v)) = Lim f , (0) = f~(0) = f~(8 + v + 1) = f~(8 + x) . I < 0 ~ t < t a
Fall 2.1.2. 0 t=2+to , wobei 2 eine Limeszahl ist: Dann ist 0. = to und r/, = 2 + 2 t + 1. Nach (17) und nach der Induktionsvorausset-
zung c) nach 0~, angewandt auf r/, <~t, ist
q~,, ( f . (a), f~ (fl + v)) = tk,, (f~ (fl), fa +, (fl + v)) =
= ~z+2,+, (to, fz+,(f l + v)) = fz+,(fl + v + 1) = fz§ Daraus folgt
Lim ~b,, ( f . (/~), f~ (8 + v)) = Lim fa +, (0) = fz +,~ (0) = f~ (0) = f~ (8 + v). l < 0 ~ I < t a
Fall 2.1.3. ct=to.;t wobei ;t eine Limeszahl ist: Dann ist 0. = 2, r h = to ' t + 3. Nach (17) und nach der Induktionsvoraussetzung c) nach ct, angewandt auf r/,<~t, ist
~bn, ( f . (8), f~ (8 + v)) = q~,, (to, f ~ . , +, (,8 + v)) = ~bo,., .3 (to, f,o., +, (8 + v))
= fo , . ,+ , (fl + v + 1) = f . . , + , ( 0 ) also
Lim tkn, ( f . (8) , f~(8 + v)) = Lim f . . , + l (0) = f~,. a(0) = f . ( 8 + v + 1) = f~(p + x) . ~<0. J<;.
Fall2.2. f l + v # - l : In diesem Falle gilt f~, ( f . (8 + v)) = f . (8 + v) fiir ~' < ~t und to .f. (/~ + v) =f~ (8 + v); Falle 2.2.1. ~t=to; deshalb ist 0 .=o9 und r h = 2 1 + 3 : Nach der Induktionsvoraussetzung a) nach 0t, angewandt auf r/, < ct, gilt
~ , h ( f . ( 8 ) , f . ( 8 + v)) = (ae,+3(to'f , t(8),f ,(f~,(8 + v))) = f , ( f~( f l + v) + f . ( 8 ) ) ,
also Lim tk,, (f~ (8), f , (8 + v)) = Lim f , ( f . (8 + v) + f~ (8)). I < 0 ~ I<:tO
Aus (6) ergibt sich
Lim f , ( f~ (8 + v) + f~ (8)) = Lim f , ( f ,~(8 + v) + f~,(8)) = f,~(8 + v + 1) = I < ~ I<tO
= + v + l ) = f , ( # + x ) .
also
Lim ~b~. (f~ (fl), f~ (fl + v)) = at<8=
Aus (6) ergibt sich
tiber die FINSLERschen h6heren arithmetischen Operationen 285
Fall 2.2.2. ~--~+~o; deshalb ist 0~=t9 und r h = 2 + 2 1 + 1, wobei 2 eine Limeszahl ist:
Nach der Induktionsvoraussetzung c) nach ~, angewandt auf ~/at < ct, gilt
dp,,(A(fl),f=(fl + v)) =~ba+2at+ , (r + v))) = fa+at (f~(fl + v) + f=(fl)),
also
Lim ~b~, (f~ (fl), f~ (fl + v)) = Lim fz +, (f= (fl + v) + f= (fl)). It<0~ l<tO
Aus (6) ergibt sich
Lim A+at(f=(/~ + v) + f=(/~)) = LimA+at(fz+to(P + v) + f~(/0) = at<to at<to
= A+to(fl + v + 1) = L ( f l + v + 1) = A(f l + x) .
Fall 2.2.3. ~=to.2; deshalb ist O,=)t und rh=r wobei 2 eine Limeszahl ist: Nach der Induktionsvoraussetzung c) nach ~, angewandt auf t/at < ~, gilt
~b,, (f= (fl), f= (fl + v)) = ~bto. at +3 (co. f= (fl), fto.at +1 (f= (fl + v))) =
= fto-at +1 (f , (fl + v) + f , (fl)),
Lim fto.,+, (f~ (fl + v) + f= (fl)). z<J .
Lim fto.,+ 1 (fto. a(fl + v) + f~(fl)) = fto. z(fl + v + 1) = f~(fl + v + 1) = f~(fl + x). l < a
Fall 3. x sei eine Limeszahl: Nach der Induktionsvoraussetzung d) nach x, angewandt auf y < x, gilt
~b, x (f~ (fl), f= (fl)) = Lira ~b r_ (f= (fl), f~ (fl)) = Lim f~ (fl + y) = f~ (fl + x). y < x y < x
Damit ist der Beweis yon Satz 1. beendet.
SATZ 2. Die Gleichungen ~, (co, co)= x undfx (0)= x besitzen dieselben L6sungen, also sind speziell die kleinsten LiSsungen einander gleich.
Beweis: Zuerst behaupten wir, dass, fiir ct>0, q~,(eo, m) und f=(0) Limeszahlen sind. D araus folgt, class L6sungen der Gleichungen ~bx(a~, co)= x und fx(0)= x auch Limeszahlen sind. 1st = eine L6sung der Gleichung th=(~o, to)= x, so erh~.lt man nach Satz 1. d):
ct = ~b,(r co)= ~ ( f = ( - 1 ) , f~ ( - 1))= A ( - 1 + 1 )= f=(0),
d.h., a ist eine L~sung der Gleichung fx (0)= x.
286 H I L B E R T L E V I T Z
Wir gehen nun daran, unsere Behauptung zu beweisen: (i) f~(0) i s t fiir ct > 0 eine Limeszahl, weilf~(0) eine e-Zahl ist. (ii) Fiir ~ ( t o , to) unterscheiden wit zwei F~ille: Fall l . ~ t = v + l :
~b, (to, co) = ~b~ +1 (to, to) = Lim ~ (to, co). n < : t o
Also brauchen wir nur zu zeigen, dass {q~"(to, to)} eine wachsende Folge vom Typ co ist. Nun gilt aber nach [4, Satz 1.]
(to, to) < to)) = (to, to).
Fall 2. ~ sei eine Limeszahl:
tb,(to, to) = Lim c bx(to, to), ,,1, < ~t
und die Folge (qg~(to, to)} vom Typ ct ist wachsend wegen [4, Satz 4]. (Q.E.D.)
SATZ 3. Sei x eine L6sung der G l e i c h u n g f x ( 0 ) = x . Wenn ~, 4, ~/kleiner als x sind, so ist ~,(~, r/) kleiner als ~:.
Beweis: Zuerst w/ihlt man eine Limeszahl 2, so dass �9 < 2 < ~c ist. Sodann setzt man z =Max(C, t/).
F a l l l . 1_<r l < q : A u s f ~ ( z ) > z , [4, Siitze 5, 6, 7], und unserem Satz 1 ergibt sich
q~, (4, q) < ~b, (4, ~) -< ~, (4, fx (z)) = q~, (ft. (z), fa (Q) < ~bx (f~ (z), A (z)) =
= f~ (z + 1) < fa (~c) = f~ (f~ (0)) = f~ (0) = 1r
Fall 2. ~ = 0 oder t /< 1 : Aus [4, Satz 9] ergibt sich ~b,(~, r/)<~r (Q.E.D.)
LITERATUR
[1] BACHMANN, H., Transfinite Zahlen, Ergebnisse der Math. und ihrer Grenzgeb. Neue Folge 1, Springer, Berlin/G6ttingen/Heidelberg, 1955.
[2] -- , Vergleich und Kombination zweier Methoden von Veblen und Finsler zur L6sung des Pro- blems der ausgezeichneten Folgen von Ordnungszahlen, Comment. Math. Heir. 26 (1952), 55-62.
[3] FEFERMAN, S., Systems of Predicative analysis, J. Symbolic Logic 29 (1964), 1-30. [4] FINSLER, P., Eine transfinite Folge arithmetischer Operationen, Comment. Math. Helv. 25 (1951),
75-90. [5] SCH/3TTE, K., Predicative well-orderings, Formal Systems and Recursive Functions, edited by
F. N. Crossley and M. A. E. Dummett, North Holland, Amsterdam, 1965. [6] --, Eine Grenze fiir die Beweisbarkeit der transfiniten Induktion in der verzweigten Typenlogik,
wird erscheinen im Archly. f math. Logik und Grundlagenforschung. [7] VEBLEN, O., Continuous increasing functions of finite and transfinite ordinals, Trans. Amer. Math.
Soc. 9 (1908), 280-292.
Eingegangen den 5. Mai 1966