Beiträge zum Entscheidungsproblem der mathematischen Logik

Beitr~ige zum Entsehe idungsproblem der mathemat i sehen Logik.

Yon

Wilhelm Ackermann in Burgsteinf~t.

Bei den Untersuchungen fiber das Entscheidungsproblem der ersten Stufe braucht man nut die logischen Ausdrficke in Betracht zu ziehen, bei denen die All- und Seinszeichen s~mtlich unverneint am Anfang stehen. Die Folge dieser All- und Seinszeichen nennen wit nach GSdel das Prd[ix des Ausdrucks. Es hat sich nun als wichtiges Ergebnis heraus- gestellt, dal~ man von der verwirrenden Vielzabl der Pr/ifixe absehen und sich auf bestimmte Pr~ifixklassen beschriinken kann, mithin eine gewisse Normierung der logischen Ausdrficke vornehmen kann. Eine erste derartige :Normierung wurde von Th. Skolem angegeben. Skolem zeigte~), daft man sich beim ErffiUbarkeitsproblem mtr mit Prfifixen der Form

(I) (Xl) (z , ) . . . (x~) (Ey,). . . (Ey,,)

zu befassen braucht. Diese Skolemsche Normalform bildet seither den Ausgangspunkt der meisten Untersuehungen fiber das Entscheidungsproblem. Eine wesentliche Versch~ixfung des Skolemsehen Resultates wuxde von K. GSdel ~) erreieht, der nachwies, dal~ man in der Skolemschen Nomal- form m = 3 nehmen kann, daft man sich also auf Pr~fixe der Form

(II) (x,) (x~) (x3) (E y , ) . . . (Ey,)

beschr~nken kann. In etw.as anderer Ricbtung bewegen sich Unter- suehungen yon L. Kalms Kalms zeigte 3), dab sieh die Frage der Er- ftillbarkeit eines beliebigen Z~ihlausdrucks auf dieselbe Frage ffir die Z~hl- ausdrficke mit einem lar~fix der Form

(lII) (Ex,) (E ~)... (~ x~) (yl) (y~) (E z) (u,) (u~)... (~) zuriicldiihxen liil~t. Hierbei claxi iibrigens vorausgesetzt werden, ebenso wie bei der GSdelschen Normalform, clat~ nur zweistellige Pr~idikatenvariable vorkommen. L~ii~t man dreistellige Pr~idikatenvariable zu, so

l) Th. Skolem, Logisch-kombinatorische Untersuehungen usw., Vid. Skrifter, Math.-Nat. Klasse 1920, Nr. 4.

~) K. GSdel, Zum En~escheidungsprobtem dea logischen F u n k t i o n e ~ Monatsh. f. Math. mad Phys. 40 (1933).

a) L. Kalm~r, FAn :Beitrag zum Entscheidungsproblem, Acta Scient. Math. Szeged 5 (1932), S. 222--236.

420 W. Ackermann.

kommt man bei einem Pr~ifix (III) sogar mit einer einzigen derartigen Variablen aus 4).

Die Reduktion des Entscheidungsproblems auf die Form (II) ver- l/iuit in der Richtung, daft die Anzahl der Allzeichen besehr~nkt wird, bei der Zurfiek~iihrung auf die Form (III) dagegen so, dab die Seinszeichen zum Teil an den Anfang des Pr~ifixes rfieken, w~ihrend im iibrigen nur ein Seinszeichen vorkommt, dem zwei Allzeichen vorangehen. Diese Zuriickffihrungen sind deswegen bemerkenswert, da fiir die F~lle, dab keine Seinszeichen oder keine AJllzeiehen vorkommen, oder dal] s~mtliche Seins- zeichen s~mtliehen Allzeiehen vorangehen, das Entseheidungsproblem sich 15sen lieB 5). Aueh fiir Pr~fixe der Form (I) m i t m -~ 2 gelang es, die Entseheidung durch~fiihren [vgl. die Ar beiten von GSdel, Kalm~r, Schiitte6)].

Im folgenden werde ieh zun~chst eine Reduktion des Entscheidungs- problems 7) vornehmen, die in der durch (III) angedeuteten Riehtung der mSglichsten Beschr/inkung der Anzahl der Seinszeiehen und ihrer mSgliehst gfinstigen Stellung noch weiter geht. Sieht man n/imlieh ab von den er- w/~hnten Pr/ifixkJassen, fiir die das Problem gelSst ist, so w~re der e]n- fachste Pr~fixtyp (falls man die Einfachheit in der angegebenen Richtung sucht) derjenige, bei dem nur ein Seinszeiehen vorkommt~ das hinter dem ersten Allzeiehen steht. Es handelt sich also um Pr~fixe der Form

(Iv) (x) (~y) (zl) (z~)... (z~). Als n~chsteinfachsten Pr~ifixtyp wiirde man den bezeichnen, der aus (IV) dadurch entsteht, daJ] man noch ein Seinszeichen vorsetzt, also den iolgenden Typ (v) (Ex) (y) (Ez) (u , ) . . . (u~).

Im ersten Teile der Arbeit zeige ich nun, dal] man zu jeder Formel eine bestimmte andere mit einem Pr~ifix der Form (V) angeben kann, so daft die Formeln hinsichtlieh ihrer ErfiiUbarkeit (d. h. der Erfiillbarkeit in irgendeinem Bereiche iiberhaupt) gleichwertig sind. Dadureh gewinnen die Formeln vom Typ (V) und die yon dem noch einfacheren Typ (IV) ein besonderes Interesse. Im zweiten Tefle stelle ich daher Untersuchungen

4) Vgl. L. KalmAr, Zum Entscheidungsproblem der mathematisehen Logik, Verh. Int. Math. Kongr. Ziirich 1932.

~) Vgl. P. Bernays und M. SchSniinkel, Zum Entscheidungsproblem der mathematischen Logik, Math. Ann. 99 (1928).

s) K. GSdel, a. a. 0.; L. Kaim~r, ~ber die Effidlbarkeit de~rjenigen Z~hl- ausdriicke usw~, Math, Ann. 108 (1933); L. Schfitte, Untersuchungen zum Ent- s~heidu~gsproblem der mathematischen Logik, Math. Ann. 109 (1934); derselbe, ~ber die Erf~llbarkelt einer Klasse yon logischen Formeln, Math. Ann, 110 (1934).

7) Wit meinen imme~ das Eff011harkeitsproblem, wenn wir hier mad im fo~enden vom Entscheidungsproblem sprechen.

]~eitrgge zum Entscheidungsproblem der mathematischen Logik. 421

iiber die Erfiillbarkeit yon besonderen Formeln des Typs IV an. Dahei werden zum ersten Male Klassen yon Formeln untersucht werden, die je nach ihrer Gestalt schon in einem endliehen oder nut in einem unendlichen Individuenbereiche oder natiirhch iiberhaupt nicht erfiillbar sind.

I.

Im Interesse einer m6glichst einfachen Daxstellung gehe ieh yon der Kalmgrschen Normalform {III) aus, da diese der Form (V) am ngchsten steht. Wesenthch fist dies jedoch fiir den folgenden Bewefis nicht; ieh kann ebenso gut yon der Form (I) ausgehen, ohne dab dabei die speziffischen Oedanken der Kalmgrschen Umformung benutzt wiirden, lch werde daher unten kurz angeben, wit der folgende Beweis zu verallgemeinern fist, falls man direkt yon (I) ausgeht.

Man babe einen Z~thlausdruek der Form

(1) (Exl)...(Ez,,,) (y t ) (y~) (E z) (u~). ..(u,~) 9~ (x 1 . . . . , x,,~ y~, y~, z, u~ . . . . . u,, ;F, . . . . . Fz)

F~, F 2 . . . . , Fz bedeuten die vorkommenden Pr~idikatvariablcn. Ist dieser Ausdruck tiberhaupt erfiillbar, so gibt es einen Individuenbereich J und in J bestimmte Elemente a~, a~ . . . . . a,,, Pr~lilrate r . . . . , r und eine zweistellige Belegungsfunktion q0 (d. h. eine Funktion, deren Argumente mad Werte Elemente yon J sind), so daft

(2) 9~(a~, a~ . . . . . a~, y~, Y2, T(Y,, Y~), u~, . . . , u , ; (ib~ . . . . , #)~)

fiir alle in J gewiihlten Wert~ von y~, y~, u l . . . . , u n e i n e richtige Aus- sage darstetlt.

Es bedeute nun Z (x, y) im Bereiche der positiven ganzen Zahlen, den wit mit Z bezeichnen, die Funlrtion (x § y)~ q- x § m. Wit behaupten dann: Es lassen in Z sich I Pr~idikate ~ , ku~ . . . . . Tt , die die entsprechende Anzahl yon Leerstellen wie r r -- . r haben, so definieren, dal3

(3) 9~(1, 2 . . . . . m, y , , y~, Z(Y~, Y~) u, . . . . . u~; T~, . . . , ~z) fiir behebige in Z genommene Werte der y , , yo, u I . . . . , u~ eine riehtige Behanptung darstellt.

Zum Bewefise bemerken wit zun~ehst, dal~ Z (x, y) ~> m, g (x, y) ~ x und g (x, y) ~ y. Ferner ist nur dann g (x, y) -~ Z (u, v), wenn x = u

' u § ist das klar. Ist aber etwa mad y = v . Ist n~imlieh x - r y = v, so x q- y ~ u § v, so kann die Gleichung Z (x, y) = Z (u, v) nicht bestehen, da in diesem Falle

(~ + y)2 + z__> (u + v + 1) ~ § x ~ (u + v) ~ § 2(u § v) ~ (u + v) ~ § u.

Wit ordnen nun jedem Elemente yon Z ein Element yon J in eindeutiger Weise zu. Den Elementen 1, 2, . . . , m yon Zsol l a~, an, . . . , a,~ aus J entsprechen. Denjenigen Elementen yon Z, die sieh nicht als Z(x, y) damtellen lassen und die yon 1, 2, . . . . m verschieden shad, ordnen wit a~

Mathematische Annalen. 112. 28

422 W. Ackermann.

zu. Sind ferner den Etementen x und y aus Z die Elemente b und c aus J zugeordnet, so wird der ZaEI Z(X, y) das Ding 9 (b, e) aus J zugeordnet. Wegen der oben angegebenen Eigenschaften yon ~ ist diese Zuordnung eindeutig und exial]t auch alle Elemente yon Z. Die Definition der Prgdikate ~ , Ta . . . . . Tz geschieht nun folgendermallen: Es babe etwa h~z t Argumente. Es seien xt, xt . . . . . xt irgendwelche Elemente aus Z, b~, b 2 . . . . . bt die zugeordneteu Elemeate aus J . ]_)ann soll immer sein

%,(x, , % . . . . . x~) ~ q~ (b,, b~, . . . , b~). getzt ist

~[(1, 2 . . . . . m, y,, y~, Z(Y,, Y2), u, . . . . , u , ; Tx, ~ 2 , - - - , T,)

fiir beliebige Werte der y~, Y2, ut, . . . , u~ richtig; denn nach Definition der k v ist dieser Ausdruck wahrheitsgleich mit

92(a,, a2, . . . , a=, b~, b~, ~(bx, b~), c x . . . . . cr,; q)l, --., ~ ) ,

wenn bt, b~, c~, . . . , c~ die den y~, Y2, u, . . . . . u , zugeordneten Dinge bezeichnen. Unsere obige Behauptung is$ somit erwlesen.

Wir ftihren nun folgende Abkfirzungen ein: !~ (x; F, G sei definlert als

(y) (z) (u) (v) (w) [F (y, z) G (y, x, z) & ~' (y, z) F (u, v) G (w, y, u) a (w, z, v)];

E (x; F, G, H) sei einc Abkiirzung fiir

(y) (z) (u) (v) (w) [H (y, x, y) & ~ (y , z) G(w, u, v) H (w, y, u) H (w, z, v)];

endlich ~ (x; F, G, H, M; . . . . , Mz) eine solche fiir

(y) (z) (u , ) . . . (u~) (v~) . . . (v~) (w) (s) (t) [~ (z, u~) ~ (u~, u~) . . . ~ (u~_~ , u~)

G( y, z, t)H(t, t, s) G( s, y, w)G( w, u,,, u 1)9I (x, u.~,..., u,~, y, z, u~, v~,..., v~; M,,...,Mt)].

ttierbei sollen F, G, H, M x , . . . , Mz freie Pr~idikatenvariable bedeuten. Wit bilden nun

(4) (Ex)[(y)(Ez)F(y,z) &~(x;F,G)&(s F , G , H ) & ~ ( x ; F , G , H , M , ..... M~)].

Diesen Ausdruck (4) kann man so umformen, dab die All- und Seins- zeichen zu Beglnn der Formel stehen. Bei passender Umformtmg erh~ilt man dann einen Ausdruck mit einem 1)r~ifix der Form (V). K6nnen wir nun zeigen, dab (1) und (4) in bezug auf Erfiillbarkeit gleichwertig sind, so ist bewie.qen, dab man die Form (V) als Normalform fiir die logischen Ausdrticke nehmen kann.

Es sei (1) in irgendeinem Bereiche J erfiillbar. Wie wit vorher gezeigt hatten, lassen sich dann die T t , ~ . . . . , ku~ in Z so w~hlen, dab (3) richtig ist. Bezeichnen wir nun das Pr~dikat y ~- x,-/- 1 mit qb(x,y), z ~ - x + y mit F ( x , y , z ) , z - ~ x . y mit O ( x , y , z ) , so geniigt zur Er- fiilltmg yon (4) im Bereiche Z jedenfaUs, da$

(y) (~z) �9 (y, z) & ~ (~; r F) & ~ (~; ~ , F, O) & ~3 (~; ~, F, O, ~ , . . . , ~'~)

Beitrgge zum Entscheidungsprob]em der mathematischen Logik. 423

riehtig ist. ~ (1; q~, F, O, ~ , . . . , ~z) lautet ausgeschrieben

(y) (z) (Ul)... (u~) (v,)... (v~) (w) (s) (0 [(us ~= 1 + 1) (u s =~ us + 1)... (u~ + u~ - i ~,- 1) ( t~y§247 ~ ..... u,,,y,z,u~,v 1 .... ,v~; T 1 ..... Tz)].

In diesem Ausdruck kann man die Ungleichheiten gem~i~ der logischen Identitiit (x) [(x ~ u) 2 (x)] --~ 9~ (u) eliminieren, und erhiilt

( y ) ( z ) ( v , ) . . . ( v , ) 2 ( 1 , 2 , . . . , m , y , z , ( y -~ z)~ + y - t -m ,v~ , . . . ,v~; ~1 . . . . , ~z),

d. h. gerade den richtigen Ausdruck (3). ~ (1; ~, /~, O) war eine Ab- kiirzung fiir

(y) (z) (u) (v) (w) [y = y . 1 & (z =~ y + 1) (v ~: w ~- u) (u ~- w. y) (v = w-z)].

l~ach Fortschaffung der Ungleichheiten erh~lt man den ~quivalenten Ausdruck

( y ) ( w ) ( y = y . l & w - l - w . y = w ( y + l)),

also eine Identit~t. ~B (1; ~b, F ) schreibt sich ohne Gebrauch yon Ab- kiirzungen als

(y) (z) (u) (v)(w) [(z ~= y § 1) (z = y § 1) & (z:~ y + 1)(v ~ : u ~ 1)(u ~- w + y) (v ---- w -- z)].

Dieser Ausdruck l~l~t sich vereinfachen zu

(y) (z) (w) [(z -T Y + l ) ( z = y - - 1 ) & ( w + Y ) ~ - I = w - - (y -r l)],

steIlt also ebenfalls eine Identit~t dar. Da auch ( y ) (Ez ) ( z = y + 1) richtig ist, so ist der Ausdruck (4) auf die angegebene Weise in Z erfiillbar.

Es sei nun umgekehrt der Ausdruck (4) in einem Bereiche K erfiillbar. Fiir diesen Bereich existieren dann Pr/idikate r O, T~ . . . . , Tz, eine Belegungsfunktion /~ und ein Element a, so da~

(5) (y) r (y,/~y) &!B (a; ~b, F) &E (a; r F, O) & ~ ( a ; ~ , / ~ , O, ~1 . . . . , Tz)

der Fall ist. Wiz kSnnen dann auch eine Erfii]lung im Bereiche Z der positiven ganzen Zahlen konstruieren, indem wlr ~ihnlich wie frtiher jeder Zahl aus Z eindeutig ein Element aus K zuordnen. Diese Zuordnung geschieht in der Weise, dab man den ZaMen 1, 2, 3 . . . . der Reihe nach a,/~ a,/~ #a, . . . entsprechen ~l~t. Die effiillenden Pr'~likate r ~ ... . ~ werden wie fziiher definiert, indem z . B . I " (x ,y , z ) dann und nur dann richtig sein soil, wenn /~(a, b, c) zutrifft, wobei a, b, c die x, y, z zugeordneten Elemente yon K sind. Die zu Z gehSrige, /~ entsprechende Belegungsfunktion i s t / / , wobei #' x = x ~ 1. Entspreehen sich x and b, so auch ~ ' x und # b. Es ist dana l~lar, da[~

( 6 ) ( y ) r y )&!B(1 ; r & ~ ( 1 ; r ~ , . . . , ~ )

richtig ist. Wegen (x) ~ ' (x, x ~- 1) gilt (x) (y) ( r (x, y) --> r (x, y)), wenn ~b" (x, y) das Pr~idikat y = x-{- 1 bedeutet. Da andererseits in (6), ab-

28*

424

gesehen vom ersten bestandteil vorkommt,

~3(1; r F ' ) &

richtig. ~3 (1 ; ~" , F ' )

W. Ackermann.

Konjunktionsgliede, ~" nut als negierter Grund- so ist auch

(1; ~" , F' , o') & ~(1 ; r v ' , ~ , ~v; . . . . , ~;)

liil~t sieh vereinfaehen zu

(y) (u) (w) [F ' (y , 1, y + 1) &/~' (w, y, u ) / " (w, y + 1, u + 1).

Daraus ergibt sich (x) (y) ( z ) / " (x, y, x + y). Bezeichnen wir m i t / " ' (x, y, z) das Pr~dikat z = x + y, so gilt demnach (x) (y) (z) ( I ' " (x , y , z) ~ I " (x, y, z)). D a / ~ ' in ~ ( 1 ; r 1 6 2 T~, . . . , T~) nur negiert vorkommt, hat man welter E (1;r O') & ~ ( 1 ; r O', ~ . . . . , ~[).

(1; r / ' " , O') lii~t sich sohreiben als

(y) (w) (u) [0 ' (y, 1, y) & O' (w, y, u) O' (w, y + 1, w + u)].

Hiervon ist ( x ) ( y ) ( z ) O ' ( x , y , x . y ) oder ( x ) ( y ) ( z ) [ O " ( x , y , z ) -+ O ' ( x , y , z ) ]

eine Folge, wobei O" (x, y, z) das Pr~dikat z = x . y bedeutet. Welter ergibt sich entsprechend wie oben

~) ( 1 ; r ~ ; , . . . , 7~;).

Dieser letzte Ausdruck ist gleichwertig mit

(y) (z) ( % ) . . . (v~) 9/(1, 2 . . . . . m , y , z, (y + z) ~ + y + m, T ; , . . . , ~ ; ) .

Eine Folgerung hiervon ist

( B x O . . . ( F _ , x ~ ) ( y ) ( z ) ( E u ) ( v , ) . . . (v ,) !~I(x, . . . . , x,~, y , z, u, v~ . . . . , v,,;

Der Ausdruck (t) is~ also ebenfalls erfiillbar. Damit haben wit gezeigt, dal~ die Ausdriicke (1) und (4) hinsichtlieh

der Erfiillbarkeit gleichwertig sind. Wir wollen nun kurz andeuten, wie man vorzugehen hat, wenn man statt yon der Kalms Normalform (III) v o n d e r Skolemsohen Normalform ausgeht.

Die Erfiillbarkeit eines Ausdrucks

(x~) (x=) . . . (x,,,) ( R y , ) . . . ( B y e ) 92 (x~ . . . . . x ,~, y , , . . . , y , ; F , , . . . , Ft )

besagt, da6 in einem Individuenbereich J n m-stellige Belegungsfunktionen ~01, ~e 2 . . . . . ~ u n d l Pr/idikate q51, r . . . . , Ct existieren, so dall

~ ( z , , x , , . . . , z , , , ~ , ( z , , . . . , z , , ) , . . . , q~,(xl . . . . . x~); r ~ )

immer richtig ist. Wit konstruieren nun wieder eine Erfiillung im Be- reiche der positiven ganzen ZaMen. An die Stelle der einen fa'fiheren Fuuktion Z treten bier ~ Funk~onen Z~, ~ , --- , 7.,, die definiert sind dutch

Z~(x: . . . . . x~) =

n [(x, + . . . + z , , ) ~ + (~, + . . . + z ~ _ , ) ~ - 1 + . . . + (x, - x , ) 2 + z d + i .

Es ist dann g~(x~, . . . , x,,) gr6i~er als jedes seiner Argumente; femer gilt nat dann

Z~ (Zl . . . . . x=) = gk (Y, . . . . . Y~,),

Beitr~,ge zum Entscheidungsproblem tier mathematisehen Logik. 425

wenn i ~--k und die l~eihe der x mit der Reihe der y iibereinstirnmt. Es wird dann wieder eine Zuordnung der Elemente yon Z zu den Ele- menten yon J hergestellt. Dem Element 1 yon Z entspricht dabei ein willkiirlieh gew~ihltes Element a 1 von J . Im iibrigen ist das Verfahren entsprechend wie frfiher. Es lassen sich also wieder Pr~idikate T~, T 2, . . . . T t definieren, so dal]

~(x~ . . . . . :~.,, z,(z~,. . . , x,~), . . . , x , , ( x , . . . . . x~); T~ . . . . . Tz)

richtig ist. Da die Funktionen Z~ sieh dutch Ineinanderschachtelung yon Summe und Produkt gewiunen lassen, kann man dann wieder einen gleichwertigen Ziihlausdruck mit einem Prefix der Form (V) konstruieren.

Wir haben damit gezeigt, dab jeder Z~hlausdruck hinsichtlich seiner Erfiillbarkeit gleichwertig ist mit einem anderen der Form

( E x ) ( y ) ( E z ) ( u , ) . . . (u,~) 9.I(x, y , z, u t , - . - , u~; Ga, . . . , G,).

Wie sich aus dem Beweise unmlttelbar ergibt, brauchen wir in vor- stehender Formel nieht die allgemelnsten ~I (z, y, z, u~ . . . . . u,; G~, . . . , G~) zu betrachten, sondern k5nnen uns auf Zfihlausdriicke der Form

(7) ( y ) ( E z ) F ( y , z ) & (Ex)(u~) . . . (u, 0 9.I(z, u 1 . . . . . u,~; F , G , . . . . . Gt)

beschr~inken. Diese Form (7) ist flit die Behandlung der Ausdriieke meist bequemer. Beim Auftreten der Pr~ifixe ( IV) i s t eine ~iJlnliche Speziali- aierung gestattet. Wit haben nur nStig, Ausdriieke der Form

(8) ( x ) ( E y ) F ( x , y ) & ( z t ) . . . ( z , 3 2 ( z ~ , . . . , z , ~ ; F,G~ . . . . . Gz)

in Betraeht zu ziehen. ]]at man n~imlich einen Z~ihlausdruck

(9) (x) (E y) (z,) . . . (z,) ~ (x, y, z, . . . . . z,; a~, . . . , Gz),

so ist

( l o ) (x) ( E y) iv (x, y) & (x) (y) (zO . . . (z~) ~ (z, y ) ~ (x, y, z, . . . . . ~ ; G,, . . . , a~)

hinsichtlieh seiner Erfiillbarkeit mit (9) gleichwertig. Denn es ist zunaehst ffir beliebige F, G~, . . . , G~ (9) eine Konsequenz yon (10), so daft die Er- fiillbarkeit yon (10) die yon (9) einseMiel~t. Ist andererseits (9) erfiillt, mad fassen wit F (x, y) ats eine hbkiirzung fiix

(z,) (z0 . . . (z~) ~ (x, y, z~ . . . . . z~; G~ . . . . . G~)

auf, so erkennen wir, dab auch (10) erfiillt ist. (10) hat aber die Form (8).

II .

Es sollen jetzt die einfachsten FEUe yon Formeln yore Typ (8) auf ihre Effitllbarkeit untersnaht werden. Wir befas~en uns bei dieser Unter- suehung in erstem I,~nie mit der Frage naeh den notwendigen und hin- reiehenden Bedingungen dafiir, da~ die betreffenden Formeln sehon in einem endliehen Individuenbereiehe sieh erftillen lassen. Einfache Unter-

4:26 W. Ackermann.

f~ille von (8) ergeben sieh dadurch, dab man annimmt, dab _~ die einzige vorkommende Pr~likatvariable ist. Es handelt sich also urn Formeln VOIll Wyp

(11) (x) ( E y ) F ( x , y) & (z~) . . . (z,,) ~.[ (zl, . . . , z=; F).

Bei (11) interessiert uns nur der Fall n ~ 3. Der Fall n ~ 2 wurde durch die in Anmerktmg s) genannten Arbeiten mit erledigt. Es zeigte sieh dabei, dab nut solche Ausdriicke auftreten, die iiberhaupt nieht oder schon in einem endfichen Individuenbereiehe erffillbar sind. Fiir den Fall n ~> 3 liegt dagegen, wie wit schon im voraus bemerken, alles anders.

Wir stellen zun/ichst einen Hilfssatz auf, dessea Richtigkeit sich zwar nnmittelbar ergibt; der aber trotzdem sehr niitzlich ist.

l= [ i l f s sa t z I: Ist der Ausdruck (11) in einem Bo.eiche dutch ein Pr~dikat r o./iillt und 9ibt es eine Teilmenge M dieses Bereiches, so daft es zu jedem Element x aus M ein y aus M mit q5 (x, y) gibt, so ist (ll) dutch r auch in M er/iillt.

Fiir das folgende erweist es sich als zweckm~ifig, wenn wit der Formel (l l) eine ge~isse symmetrische Gestalt geben. Wit bflden zu- n/ichst alle mSgfichen Ausdriicke, die aus 9~(u~ . . . . . u, ; F) dadureh ent- stehen, dal] wit die u in ganz beliebiger Weise dutch Variable aus der Reihe zl, . . . , z~ ersetzen, wobei die Reihenfolge gleichgiiltig ist und Wieder- holungen vorkommen diirfen. Alle so entstehenden Ausdriicke werden dann dutch & verbunden. Wit bezeichnen diese Konjunktion mit ~ (zl . . . . . z,; F). Offenbar gilt

(z , ) . . . ( z , ) ~ ( z l . . . . . z , ; F ) ~ {z,) . . . ( z , ) ~ ( z , , . . . , z , ; P ) .

Ferner ~ l t (z~ . . . . . z,; F) ~ ~ (z~, . . . , z,~; F),

wo die i ~ , . . . , i~ beliebige Werte aus dem Bereich 1, 2 . . . . . n bedeuten mSgen. Statt {11)wollen wit nun in Zukunft den gleichwertigen Ausdruck

02) (x) (Ey) F (z, y) & (z , ) . . . (z.) ~ (z, . . . . . z.; ~) betrachten.

Die Frage nach den Bedingungen fiir die Erfiillbarkeit von (12) in einem endlichen Individuenbereiehe wird uns nun dutch den folgenden Satz beantwortet.

S a t z I: g i n Aus&'uck der Form (12) ist dann und nur dann in einem endlichen Bereiche er/iillbar, ]aUs o. schan in einem Bo.eiche mit do" Individuenzahl n + 1 o"]iillbar ist.

B e w e i s : Es sei J der kleinste endliche Bereich, in dem (12) erftillbar ist. ~b sei ein zu J gehSriges erfiillendes Pr~dikat. Unter einem r yon Elementen woUen wit eine enclliche Anzahl aa, a~ . . . . , a~ yon Elementen aus J verstehen, so dab immer r a, ~ ~) und au~erdem

Beitr~ge zum Entscheidungsproblem der mathematischen Logik. 427

r al) der Fall ist. Ein Zyklus kann auch aus einem einzigen Elemente a~ bestehen, wenn n~mlich r (a~, al) der Fall ist. Ein derartiger r existiert immer in J. Wir kSnnen n~mlich, da ja (x) (E y) q~ (x, y) der Fall ist, von einem beliebigen Elemente b 1 yon J ausgehend, weitere Elemente b2, b 3, . . . finden, so dab immer r b,+l) der Fall ist. Wegen der Endlichkeit des Bereiches J kommen wit dann nach endlich vielen Schritten zu einem Element b,, so da$ ein i mit ~b (b,, bi) existiert (i ~< l). Die Elemente b . . . . . ~ b, bilden dann einen r

Es mSgen also die Eiemente al, a 2 . . . . . ak einen r bilden. Nach tIilfssatz I i s t (12) im Bereiche (al, a~ . . . . , ak) dutch r eIfiillt. Da J der kleinste Bereich ist, in dem Erfiillung mSglich ist, so enth~lt die Reihe a , , a~ . . . . . ak alle Elemente von J und zwar jedes m~r einma]. Aus demselben Grunde ist immer ~ (a~, a j), aul~er wenn j = i ,+ 1 oder i = k und j = 1. (Anderenfalls g~be es ja einen kleineren r

Ist nun k ~< n'A- 1, so bedarf unser Satz I keines weiteren Beweises. Wir diirfen also voraussetzen, da$ k > n + 1. Wit bilden einen neuen Bereich aus den Elementen al, a .~, . . . , a,,+~. In diesem Bereich wird ein Pr~likat T so definiert, dal~ fiir alle i T ( a ~ , a , + l ) und T ( a , + ~ , a l ) richtig ist, wiihrend im iibrigen W ( a , a3) der Fall sein soll. Nun war !~ ( a l , . . . , a~; ~b) richtig wegen tier Erfiillbarkeit von (12) durch ~b im Bereiche a~, a2, . . . , a~. ~B (al . . . . . a~; ~ ) ist ebenfalls richtig, da ja, soweit nut a~, a 2 . . . . . a . in Frage kommt, T mit r iibereinstimmt.

~B(a,+1 . . . . . a=+l, a I . . . . . az-1; T)

ist ferner bei beliebig gew~ihltem i richtig. Dieser Ausdruck ist n~mlich wahrheitsgleieh mit ~B ( a p . . . , a.; T), da ja fiir ~ keines der Elemente a~, a ~ , . . . , a,,+~, die man sieh zyklisch angeordnet denken kann, so dall sich a~ wieder an a~+~ anschliel~t, ausgezeiehnet ist. Wegen der auf Seite 426 erw~hnten Eigenschaften von !B ergibt sich weiter, dal~ iiberhaupt (z~) . . . (z,~) ~ (zl . . . . . z,~; ~ ) riehtig ist. Mit anderen Worten: (12) w~re schon in einem Bereich mit n + 1 Elementen erfiillt. Das schlieSt einen Widerspruch ein, da ja J der kleinste Bereich sein sollte, der noch Er- fiillung zul~iSt. Der Fall k > n + 1 kommt also nicht in Betraeht. Damit ist Satz I bewiesen.

Nachdem wir ein Kriterium dafiir angegeben haben, wann eine Formel vom Typ (12) sich in einem endlichen Bereiche erfiillen ]~il~t, suchen wit bei den Formelm die diesem Kriterium nichV geniigen~ nach der Beant- wortung der Frage, ob wenigstens Erftillbarkeit in einem unendlichen Individuenbereiche besteht.

Wir legen irgendeinen Z/4Mausdruck der Form (12) zugrunde und wollen, yon diesem ausgehend, zun~chst einen weiteren Z~alausdruck kon-

428 W. Ackermann.

struieren. Wit bezeichnen mit FI ' iv (z~, zk) die Disjunktion aller Aussagen

F (z~,z~), bei denen 1 ~_~i,k ~ n ; k ~ i + 2 . Da n ~ 3, ist die angegebene Disjunk~ion immer bedeutungsvoll. ~ (z~, z~, . . . , z~; F) sei eine Abkiirzmag fiir die Konjunktion

iv (zl, zl) &_~ (z,, z~)_~ (z~, z,) & . . . & ~ ( z , z~) ~ (z~, z~) . . . _~ (z~_ , , z~) ~ (z~, zl).

Wir bilden den folgenden Z;4hlausdruck

(13) (x) ( E y ) F ( x , y ) & (zl) . . . (z,~) [~B(z 1 . . . . , z , ; F ) & ~ (z, . . . . . z,~;F)

& ~ ( z , , z~)~(z~ , z9 . . . ~(z~_~, z,) H ' iv (z~, z~)]. i , k ~ 1

Es gilt dann der H i l f s s a t z II : Ist ein Ausdruck de~" Form (13) iiberhaupt er]iillbar,

so nur in einem unendliehen Individuenbereich. B e w e i s : Nehmen wir an, (13) sei in einem endlichen Individuen-

bereiche erfiillbax. Es existiert dann eln kleinster" Bereich dieser Art, den wit J nennen woUen. Das erfiillende P#idikat sei r Die Anzahl der Elemente v o n J sei l. Nach Satz I i s t l _ _ < n + l . Aus den (Tber- legtmgen, die wit beim Beweise yon Satz I angestellt haben, ergibt sich, dal~ wit den Elementen yon J eine derartige Anordnmag a~, a~ . . . . , at geben kSnnen, so daft a~, a~ . . . . , a~ einen ~b-Zyklus darstellt.

a) Es sei l ~ n. Dieser Fall ist aicht mSglich. Da n~mlich (z,) (z2) . . . (z~) ~(z , . . . . . z~; r der Fall ist, so miiBte sein

~b (a,, a2) r (a~, a3) . . . ~b (at- i , a~) ~b (az, al),

was mit dem Bestehen eines r fiir al , a~ . . . . , at unvereinbar ist. b) Es se i l ~ n + 1. Da a~, a~ . . . . . an + ~ einen r bilden, gilt

r (ax, ag) & ~5 (at, as) & . . . & ~b (a~_ 1, a,) & / / ' r (a,, a~). z~ k ~ l

Es kSnnte also

(zl) (~ ) . . . (z,) (~(z , , z~) ~ - (~ , z~) . . . ~-(z~_l , ~ ) / I ' r (~,, ~)) Z, k ~ l

nicht richtig, mad damit (13) nicht dutch r erfiillt sein. Dieser Fall ist also ebenfalls unm6glich.

t t i l f s s a t z I I I : Ist ein Ausdruck der Form (12) nur in einem unendlichen Individuenbereiche er[iillbar, so ist der zugehgrige Ausdruck (13) (d. h. derjenige mit demselben fS) eben/alls er]iiUbar.

Beweis : (12) sei in einem unendlichen Individuenbereiche J dutch r erfiillbar. Da (12) in keinem endlichen Bereiche erfiillbar sein soil, darf es nach Hilfssatz I keine Reihe yon Elementen aus J z,, z., . . . . . z~ geben, so daft

O(z~, z~) & . . . & O(z~_~, zt) & r zl)


der Fall ist. (zl)... (z~) ~ ( z l , . . . , zn; ~) ist also jedenfalJs richtig. Giibe es ferner eine Reihe yon Elementen zl, z 2 , . . . , zs, so dal~

r (zl, zz) & q) (z 2, z~) & . . . & q) (zn- 1, z~) und auBerdem /7 ' q) (z~, zk) der Fall G k ~ 1

ist, so hiitte man ~/Y (z~, z~) fiir k ~ i + 2, ferner wegen ~(zl , z2, . . . , z~; r iiberhaupt ~ (z~, z,) (1 ~_ i, k ~: n), ausgenommen der Fall k = i + 1. Man kSnnte dann genau wie beim Beweise von Satz I ein weiteres Element z,, + ~ hinzufiigen und in dem Bereich (zl, zz, . . . , z= + 1) ein Pr~likat 7 v, wie friiher angegeben, definieren, so dab (12) in diesem Bereieh erfiill~ ist, im Widerspruch zu unserer Voraussetzung. Daher ist auch

n

(z,) (z~) . . . (z,) r (z, , z2) . . . r ( z~_~ , z,) / 7 ' r (z,, ~)

der Fall.

H i l f s s a t z IV: D/e notwe~dige und hinreichende Bedi, gung da]iir, daft (12) nut in einem unendlichen Individuenbereiche er]iillbar ist, ist die Er- ]iiUbarkeit yon (13).

Der Beweis er~bt sich unmittelbar aus tIilfssatz II und I I I unter Beriicksiehtigtmg des Umst~ndes, da[~ die Erftillbarkeit yon (13) die des sehw~icheren Ausdrucks (12) naeh sich zieht.

GemiiB Hi]fssatz IV kSnnen wir uns welter auf die Untersuchung der Erfiillbarkeit der Formeln vom Typ (13) beschr~nken.

Die Ausdriieke (13) haben die Form (8), also die Gestalt

(x) (Ey) E (x, y) & (u~) (%) . . . (u~) ~I (z, ul, . . . , us; av, Ol, . . . , Gz).

Fiir diese Ausdrfieke (8) gilt folgendes: Lassen sie sich iiberhaupt erfiillen, so auch im Bereich Z der positiven ganzen Zahlen, und zwar so, dab es in diesem Bereieh Prgdikate ~b, k~, . . . , 7tz gibt, so dal3

(x) ,/) (x, x + 1) & (u,) . . . (us) ~ (1, u, . . . . . u , ; q), T1 . . . . , T,)

riehtig ist. Zum Beweise braueht man nut die Uberlegungen, die wir auf Seite 423 fiix die Ausd_riicke der Form (4) aufgestellt hatten, entsprechend zu wiederholen.

Es sei nun 03) in irgendeinem Bereiche erfiillbar. Nach dem vorigen gibt es dann ein-in Z definiertes Pr~dikat, so daI3

(14) (~) r (x, x + 1) & (zl) . . . (z.) [ ~ (z, . . . . , z , ; r s

& ~ ( z , , . . . , z , ; ~ ) & ~ ( z , , z~) . . . ~ ( z , _ l , ~ . ) / / ' r z~)] i , k ~ l

in Z eine riehtige Behauptung darstellt. Aus (x) r (x, x + 1) und ttilfs- satz I in Verbindung mit der Tatsaehe, dM$ (13) in keinem endlichen Bereiehe erfiillt sein kann, ergibt sieh, da[~ r (x, y) falseh ist, falls y ~_ x.

W. Ackermann.

Es war schon friiher gesagt, dab wit uns nut um den Fall n ~ 3 zu kiimmem braucheu. Es sei nun gerade n = 3. (14) lautet dann

(x.) r (z, z + 1) & (zl) (z2) (z~) [~ (z,, z~, z~; r & ~ (z~, ~ , z~; ~)

& r (z 1, z~) r (z 2, zD r (z,, z3)]. Aus

(z) �9 (z, x + 1) & (z,) (z0 (z3) [~ (z~, z0 ~ (z2, z3) r (zi, z~)]

in Verbindung mit den obengenannten Eigenschaften yon r ergibt sieh, dal~ r (x, y) mit x < y identisch ist. Da natiirlich auch ~ (z,, z~, z3; < ) der Fall ist, so ist im Falle n = 3 der Ausdruck (13) dann mad nur dann erfiillbar, wenn (15) (z,) (z.2) (%) f~ (za, z 2, z3; < )

im Bereiche der positiven ganzen Zahlen eine riehtige Behauptung darsteUt. Die Entscheidbarkeit yon (15) stellt aber ein in der Literatur bereits ge- 1Sates Problem dar. Z.B. l~iSt sich nach Presburger s) jeder Ausdruck der ersten Stufe entscheiden, d e r n u r die individuellen Pr~idikate der GrSller- kleinerbeziehung, der Addition und Kongruenzen nach einem konkreten Zahlenmodul enth~It. Der F a U n = 3 ist damit vollst~tndig erledigt.

In ~ihnlicher, wenn auch nicht so einfacher Weise liil~t sich der Fall n = 4 behandeln. Es sei r (x, y) eine Abkiirzung flit z < y, r (x, y) eine solche fiir x < y & y ~ z -4- 1 (rood 2). Die notwendige und hinreichende Bedingung fiir die Effiillbarkeit yon (13) ist dann die Richtig- keit yon (16) (zl) (z2) (zz) (z,) ~B (z,, z2, zz, z,; r V (z,) (z~) (z3) (z,) ~ (z,, z~, z3,z,; r

im Bereiche der positiven ganzen Zahlen. Da$ die Bedingung hinreichend ist, ergibt sich daraus, dab

und ~1 (z~, z~) r (z,, z4) r (z2, z,)]

(~) (~) (z0 (z,) [~ (z~, z~, z~, z,; r ~ r (z,, z~) r (z2, z~) ~ (z~, z,) r (z,, z~) r (z,, z,) ~ (z~, z,)]

beide riehtig sin& Es bleibt die Notwendigkeit der Bedingung zu zeigen. Sei r ein Pr~dikat, so dal3 (14) richtig wird. Wit unterscheiden dann drei Falle:

a) Es gebe vier Zahlen a , , a , , a~, a 4, so dal3 ~b (ai, "a,) immer richtig ist flit i, k =- 1, 2, 3, 4; i < k. Wie sich aus den friiheren Bemerkungen fiber r ergibt, ist dann a, < a~ < a~ < a,. Ferner gilt �9 (ai, a,) iiir i >_~ k. Nehmeu wit nun irgendwelche Zahlen zl, z2, z~, z~ (z, < z 2 < z= < z,),

s) M. Pre~b~ger, Ober die Vollst~ndigkeit einea gewisaen Systems der Arith- metik ganzer Zablen usw., Comptes Rendus du premier Congr~s des Math. des Pays Slaves, Warschau 1930.


so ist ~B (zl, z 2, z 8 , z4; ~1) offenbar gleichwertig mit ~ (a~, as, as, a4; ~), also richtig. Aus der Seite 426 erwghnten Symmetrieeigenschaft yon ~B ergibt sich, da~ iiberhaupt (zl) (z2) (z~) (z 4) ~B (zl, z2, z~, z,; r der Fall ist. Im Falle a) ist also die Behauptung bewiesen.

b) Es gebe vier Zahlen a~, as, a~, a, , so da$

r (a,, as) & ~b (as, a3) & ~ (as, a4) & ~ (a~, a~) & r (a,, a,) & ~ (as, a,) der Fall ist. Es ist dann wieder a ~ < a s < a ~ < a ~ und �9 (a~,ak) flit i :> k. Wir behaupten dann, dab (zl) (z~) (z~) (z4) ~ (z~, :.,, z3, z,; r richtig ist. Der Beweis braucht wieder nut fOr solche z gefiihrt zu werden, fiir die z~ < z 2 < z~ < z,. Es sei irgend eine konkrete derartige Reihe z~, z 2, z~, z~ gegeben. Wit ordnen den z~, z~, z~, z, der Reihe nach Dinge aus der Reihe a~, a 2, a~, a, zu. Dem z~ wircl a~ zugeordnet. Sei dem z i schon a~ zugeordnet. Ist z~ ~ 1 ~ zi + 1 (rood 2), so wird zt- ~ ak. 1 zugeordnet. Is t z~+~ ~ zi (rood 2), so wird z~+~ a~ zugeordnet. Die so erhaltene, den z~, zs, z~, z~ zugeordnete Reihe der a sei a,~, a~.~, a,~, al, (i~ ~ i s <~ i s ~_~ i4)- Aus der Natur des PrRdikates r ergibt sich, dal] q~,_ (z,~, z ,) ~ r (a~,~, a~,~). Daher ist auch

(z~, z~, z~, z,; r ~ ~ (ah, a,~, a,~, a~; q~).

Mithin ist ~B (z,, z , , z~, z,; r richtig.

c) Es sei weder a) noch b) der Fall. Die AusschlieSung von a) bedeutet die Richtigkeit von

(17) (z~) (z~) (z.) (z,) �9 (z~, z~) 4~ (z~, z~) ~ (z~, z,) ,~ (z,, z~) �9 (z,, z,) �9 (z~, z,), die Ausschliel]ung von b) die Richtigkeit von

08) (z,) (zs) (z~) (z,) ~ (z,, z~) ~ (z.~, %) ~ (z~, z,) r (z,, z~) 6 (~,, ~,) r (z~, z,). Gemii~ Formel (14) ist augerdem noeh

(19) (z~) (z~) (z.~) (z,) ~ (z , , z~) ~ (z~, z~) r (z~, z,) r (z,, zz) r (z,, z,) ~b (z~, z,)

der Fall. Aus (18) und (19) ergibt sich, da] auch

(20) (z~) (z~) (z~) (z,) ~ (z,, z~) ~ (z~, z~) ~ (z~, z,) r (z,, z~) r (z~, z,) besteht. Die Eigenschaften von r die in vorstehenden Formeln zum Ausdruck kommen, lassen sich auch in der folgenden Form aussprechen:

A. Seien a, b, c drei Zahlen, so da~ ~b (a,b) & O ( b , c ) & ~ ( a , c ) r~chtig ist. Gibt es dann eine weitere Zahl d, so da~ r (c, d) richtig ist, so ist auch r (b, d) richtig.

B e w e i s : A ist eine unmittelbare Folge yon (20). B. Seien a, b, c drei Zahlen, so dal~ r & r & r

richtig ist. Gibt es dann weitere Zahlen d und e, so da~ r (c, d) & r (d, e) richtig ist, so ist r (c, e) falsch.

B e w e i s : GemRl~ Bedingung A ist ~5(b, d) richtig. W~re nun auch ~5 (c, e) richtig, so wieder nach BM;ngung A, diesmal angewandt auf a, b, c

432 W. Ackermann, Beitr~ge zum Eatecheidungsproblem der mathematischen Logik.

und e0 auch ~ (b, e). b, c, d, e warden dann, in (17) ffir zl, z~, z~, z 4 ein- gesetzt, diese Formel zu einer falschen machen. Daher kann �9 (c, e) nicht riehtig sein.

C. Seien a, b, c, d vier Zahlen, so dab ~b (a, b) & �9 (b, c) & q~ (c, d) richtig ist. Dann ist entweder q~ (a, c) oder ~5 (b, d) oder q~ (a, d) falsch.

B e w e i s : C driickt dasselbe aus wie (17). Es fragt sich nan, ob ein Pr~idikat ~, das den vorstehenden Bedin-

gungen A, B, C geniigt, und ffir das (14) richtig ist, tiberhaupt m6glich ist. Von der Bedingung (14) wollen wir dabei nut benutzen, da~ (x) ~ (x, x + 1) der Fall ist.

Es gibt zun~chst Zahlen a, b, c, so da~ r (a, b) & q~ (b, c) & ~ (a, c) der Fall ist. Wegen (x) ~b (x, x -~ 1) und Bedingung C ist n~mlich von den Aussagen ~ (1, 3), r (1, 4), q~ (2, 4) mindestens eine falsch. Ist r (1, 3) ialsch oder �9 (2, 4) fatsch, so haben wit die drei Zahlen in 1, 2, 3, bzw. 2, 3, 4 gefunden. Is t tb(1 ,3)& q~(2,4) richtig, so sind 1 ,3 ,4 die gesuchten Zab2en. Wit betrachtea nun die Reihe a, b, c, c -t- 1, c + 2, c--', 3 . . . . . Da q~(a,c) falsch ist, so ergibt sich unter Beriicksichtigung von (x) q~ (x, x ~ 1) und wiederholter Anwendung yon B, da f die Aussagen r (c, c ~ 2), r (c ~ 2, c ~ 4), q~ (c ~- 4, c -t- 6) . . . . alle falsch sind. Gemiif Bedingung A sind nun die Aussagen r (b, c ,-]- 1), q) (c -I- 1, c ~- 3), q~ (c -i- 3, c + 5) . . . . alle richtig. Wendet man nun B aui a, b, c, c ~ 1, c-t- 3 an, so erkennt man, d a f r (c, c d- 3) falsch ist. Ebenso sind r (c ~- 2, c + 5), r c d - 7 ) . . . . falsch. Wenden wir auf c~ ' 4, c + 5 , c ~ 7 , c - ] -9 die Bedingung A an, so sehen wit, dat~ ~b (c + 5, c ~ 9) richtig sein mull. Wenden wir andererseits aaf c ~ 2, c d- 3, c -b 5. c ~ 7, c -~ 9 die Bedingung B an, so ergibt sich, daft r 1 6 2 c ~ 9 ) falsch sein muff. Das ist einWider- spruch. Im Falle c) kann es also kein Pr~idikat r geben. Damit ist das Entscheidungskriterium, das wit fiir n -----4 aufgestellt h~tten, als zu Recht bestehend erwiesen.

Dutch die vorstdt~den tJberle~ungen ist das Entscheidungsproblem flit die Ausdriieke (11) vollstandig gel6st, sobald n ~ 4. Entweder sind n~nlich die Ausdrficke (11) schon in einem endtichen Bereiche e f f~ba r . Ob das der Fall ist, wird durch Satz I entschieden. Ausdriicke (11), die nicht dem in Satz I angegebenen Kriterium geniigen, sind entweder iiberhaupt nicht oder nur in einem unendlichen Individuenbereiche erftillbar. Diese Alternative braucht dann nut flit die Ausdriicke (13) untersucht zu werden. Fiir den Fall n ~ 4 lief sich, wie wit sahen, die Entscheidung zwischen beiden M6glichkeiten treffen. Eine Ausdelmung der Untersuchungen auf den Fall n :> 4 ist mir auch flit n : 5 bisher nicht gehmgen.

(Eingegsngen am 25. 7. 1935. )

Documents

Beiträge zum Entscheidungsproblem der mathematischen Logik