9
Math. Semesterber. (1993) 40: 105-113 Mathematische Semesterberichte © Springer-Verlag 1993 Reverse Mathematik und ihre Bedeutung Roman Murawski Institut fiir Mathematik, Adam-Mickiewicz-Universitlit, ul. Matejki 48/49, PL-60-769 Poznan, PoIen Eingegangen am 20.11.1992, angenommen am 30.11.1992 Zusammenfassung. Die Rolle von Axiomen und Sâtzen ist gewëhnlich so, daB Axiome benutzt werden, um Sâtze zu beweisen. In der reversen Mathematik werden Sâtze benutzt, um daraus Axiome herzuleiten. Dadurch werden die minimalen Vor- aussetzungen erkannt, unter denen die Sâtze gewonen werden kënnen. Das Programm der reversen Mathematik ist grundlagentheoretisch motiviert und bezieht sich auf die kIassische Mathematik, die sien in der Arithmetik der zweiten Stufe formalisieren Iâêt, Die Axiome sind, bis auf das voIle Komprehensionsschema, grundlagentheore- tisch unproblematisch. Es geht darum, fur zahlreiche klassische Sâtze zu untersuchen, welche Abschwâchungen des Komprehensionsschemas gerade noch ausreichend sind. 1. Einführung Das Wort "reverse Mathematik" (englisch: reverse mathematics) bezeichnet ein For- schungsprograrnm in der mathematischen Logik und Grundlagenforschung der Ma- thematik, das im Jahre 1974 von Harvey Friedman wâhrend des Internationalen Ma- thematiker Kongresses initiiert wurde. Der Name ist ein wenig irrefûhrend, deswegen spricht man manchmal von "sogenannter" reverser Mathematik. Aus dem, was spâter gesagt wird, wird die Etymologie dieses Namens klar werden. Die Ergebnisse der reversen Mathematik sind sehr interessant und das Programm entwickelt sich intensiv. Darüberhinaus haben die Resultate nicht nur technische Be- deutung fur Logik und Grundlagenforschungen, vielmehr sind sie auch fur die Philo- sophie der Mathematik sehr wichtig. Es handelt sich hier vor allem um das Hilbertsche Programm der Begründung der kIassischen Mathematik, das im Jahre 1931 von K. GOdel als nicht vôllig unrealisierbar nachgewiesen wurde. Die Resultate der rever- sen Mathematik zeigen nâmlich, daB das Prograrnm von Hilbert doch, wenn auch nur teilweise, realisiert werden kann. AuBerdem bildet die reverse Mathematik eine Brücke zwischen Logik und Grundlagen der Mathematik auf der einen Seite und der gewôhnlichen Mathematik auf der anderen. Sie zeigt, daB Logik nicht nur eine Disziplin fur sich allein ist, die keine Verbindungen zur Mathematik hat und deren Re-

Reverse Mathematik und ihre Bedeutung

Embed Size (px)

Citation preview

Page 1: Reverse Mathematik und ihre Bedeutung

Math. Semesterber. (1993) 40: 105-113Mathematische

Semesterberichte© Springer-Verlag 1993

Reverse Mathematik und ihre Bedeutung

Roman Murawski

Institut fiir Mathematik, Adam-Mickiewicz-Universitlit, ul. Matejki 48/49, PL-60-769 Poznan, PoIen

Eingegangen am 20.11.1992, angenommen am 30.11.1992

Zusammenfassung. Die Rolle von Axiomen und Sâtzen ist gewëhnlich so, daBAxiome benutzt werden, um Sâtze zu beweisen. In der reversen Mathematik werdenSâtze benutzt, um daraus Axiome herzuleiten. Dadurch werden die minimalen Vor­aussetzungen erkannt, unter denen die Sâtze gewonen werden kënnen. Das Programmder reversen Mathematik ist grundlagentheoretisch motiviert und bezieht sich auf diekIassische Mathematik, die sien in der Arithmetik der zweiten Stufe formalisierenIâêt, Die Axiome sind, bis auf das voIle Komprehensionsschema, grundlagentheore­tisch unproblematisch. Es geht darum, fur zahlreiche klassische Sâtze zu untersuchen,welche Abschwâchungen des Komprehensionsschemas gerade noch ausreichend sind.

1. Einführung

Das Wort "reverse Mathematik" (englisch: reverse mathematics) bezeichnet ein For­schungsprograrnm in der mathematischen Logik und Grundlagenforschung der Ma­thematik, das im Jahre 1974 von Harvey Friedman wâhrend des Internationalen Ma­thematiker Kongresses initiiert wurde. Der Name ist ein wenig irrefûhrend, deswegenspricht man manchmal von "sogenannter" reverser Mathematik. Aus dem, was spâtergesagt wird, wird die Etymologie dieses Namens klar werden.

Die Ergebnisse der reversen Mathematik sind sehr interessant und das Programmentwickelt sich intensiv. Darüberhinaus haben die Resultate nicht nur technische Be­deutung fur Logik und Grundlagenforschungen, vielmehr sind sie auch fur die Philo­sophie der Mathematik sehr wichtig. Es handelt sich hier vor allem um das HilbertscheProgramm der Begründung der kIassischen Mathematik, das im Jahre 1931 von K.GOdel als nicht vôllig unrealisierbar nachgewiesen wurde. Die Resultate der rever­sen Mathematik zeigen nâmlich, daB das Prograrnm von Hilbert doch, wenn auchnur teilweise, realisiert werden kann. AuBerdem bildet die reverse Mathematik eineBrücke zwischen Logik und Grundlagen der Mathematik auf der einen Seite undder gewôhnlichen Mathematik auf der anderen. Sie zeigt, daB Logik nicht nur eineDisziplin fur sich allein ist, die keine Verbindungen zur Mathematik hat und deren Re-

Page 2: Reverse Mathematik und ihre Bedeutung

106 R. Murawski

sultate keine Bedeutung für einen Analytiker oder einen Topologen hatten. Sie zeigt,daB in der Logik und Grundlagenforschungen Resultate erhalten werden, die überwichtige Fragen der Topologie, Funktionalanalysis oder Algebra etwas Interessantesund Wesentliches sagen kônnen.

Das Ziel dieser Arbeit ist es, die wichtigsten Resultate der reversen Mathematikzu beschreiben und ihre Bedeutung für die Philosophie der Mathematik zu zeigen.

2. Formalisierung der Mathematik; das Programm der reversen Mathematik

Es hat sich gezeigt, daB man die Mathematik nicht nur in der Mengenlehre formali­sieren kann, vielmehr lassen sich die meisten mathematischen Disziplinen schon indem schwacheren System der Arithmetik der zweiten Stufe Ai (manchmal auch alsZ2 bezeichnet) formal entwickeln. Das wurde zum ersten Mal von D. Hilbert und P.Bernays bemerkt (vgl. [9]). H. Weyl hat in [23] gezeigt, daB wesentliche Teile dergewôhnlichen Mathematik in einem .prâdtkauven'' Teilsystem von ~ (das w-iteriertearithmetische Definierbarkeit ermôglicht) entwickelt werden konnen. Die Arithmetikder zweiten Stufe Ai ist ein System, das in einer Sprache mit zwei Sorten von Va­riablen, nâmlich Variablen für natürliche Zablen x, y, z, ... und Variablen für Mengenvon natürlichen Zahlen X, Y, Z, ... formalisiert ist. Nicht-logische Zeichen der Spra­che von Ai sind: die Zeichen der Peanoschen Arithmetik PA, d. h. 0, S, +, . und dasElementzeichen E. Die nicht-logischen Axiome von Ai sind folgende:

(1) Axiome von PA ohne das Induktionsschema,(2) (Extensionalitât) Vx(x E X ~ x E Y) - (X =Y),(3) (Induktionsaxiom) 0 E X &Vx(x E X - Sx E X) - Vx(x EX),(4) (Komprehensionsschema) 3XVx[x E X ~ <p(x, ...)],

wobei <p(x, ...) eine beliebige Formel der Sprache L(Ai) von Ai ist, die noch andereZablen- oder Mengenvariablen als Parametern enthalten kann und die die Variable Xnient als freie Variable enthâlt, Modelle von Ai sind Strukturen der Form (œt,.%'),wobei œt ein Modell von PA und .%' eine Familie von Teilmengen von M (= dasUniversum des Modells œt) sind'. Wir bemerken noch, daB für das Standardmodell910 von PA die Struktur (lJlo,9I'(N)) ein Modell von Ai ist. Aber das ist nicht sofür Nicht-Standardmodelle, Wenn œt ein Nicht-Standardmodell von PA ist, dann ist(œt,9I'(M)) kein Modell von Ai.

Die Arithmetik der zweiten Stufe A2 ist ein schënes System, das viele Schwie­rigkeiten, die mit der Mengenlehre verbunden sind, zu vermeiden ermëglicht. Wirmeinen hier z.B. paradoxe Folgen des Auswablaxioms oder Probleme mit der Ak­zeptabilitât der konkreten einzelnen Axiome. Auf der anderen Seite ist dieses Systemstark genug, um in ibm viele wichtige Sâtze der klassischen Mathematik beweisen zukënnen. Es gibt aber einen Defekt - und zwar erlaubt das wichtige Schema der Kom­prehension auch sog. imprâdikative Deûnitionen". Es zeigt sich aber, daB in vielenFâllen auch verschiedene Fragmente von Ai ausreichen, d.h. spezielle Formen desKomprehensionsschemas genügen.

lm Jahre 1974 wâhrend des Internationalen Mathematiker Kongresses formulierteH. Friedman ein Forschungsprogramm, das heute reverse Mathematik genannt wird.

1 Informationen über ModeUe von ~- kann man z.B. in [3], [12] und [13] finden.2 Es sei erwâhnt, daB H. Poincaré gerade imprlidikative Definitionen für QueUe und Ursache aller

Paradoxe in der Mathematik gehalten hat.

Page 3: Reverse Mathematik und ihre Bedeutung

Reverse Mathematik und ihre Bedeutung 107

Das Ziel dieses Programms war die Untersuchung der Rolle des Existenzaxioms, d.h.des Axioms der Komprehension, in der gewëhnlichen Mathematik. Das Hauptproblemwar: Sei ein bestimmter Satz 7 der gewëhnlichen Mathematik gegeben. Was furExistenzaxiome sind für den Beweis von 7 notwendig? Dieses Programmhat sich alssehr fruchtbar erwiesen und führte zu vielen interessanten Ergebnissen",

Die Methode, die in der reversen Mathematik verwendet wird, lâêt sich fol­gendermaBen charakterisieren: Wenn ein bestimmter Satz 7 in einem bestimm­ten Teilsystem S(7) von A:; bewiesen werden kann, so fragt man, ob S(7) dasschwâchste System mit dieser Eigenschaft ist? Man kann diese Frage positiv be­antworten, wenn man in einem schwâcheren Teilsystem T von A:; (sodaB T nonf- 7), daB 7 zu dem Komprehensionsaxiom von S(7) âquivalent ist, d.h. T f­[7 +-+ Komprehensionsaxiom von S(7)]. Der nichttriviale Teil dieser Àquivalenz istnatürlich: 7 ---+ Komprehensionsaxiom von S(7). Man beweist also hier Axiome (ge­nauer gesagt einige Formen des Komprehensionsaxioms) auf Grund von Sâtzen (dergewôhnlichen Mathematik). Das erklârt auch die Etymologie des Namens "reverseMathematik": lm Gegensatz zu .mormaïer" Mathematik, wo man Sâtze aus Axiomenbeweist, werden hier Axiome aus Sâtzen deduziert.

3. Wichtigste Resultate der reversen Mathematik

Untersuchungen, die im Rahmen des von H. Friedman vorgeschlagenen Forschungs­programs der reversen Mathematik geführt worden sind, haben zur Formulierungverschiedener Teilsysteme der Arithmetik der zweiten Stufe geführt", Insbesonderehat man folgende Systeme untersucht: RCAo, WKLo, ACAo, ATRo, III - CA. Wirwerden hier nur die ersten drei Theorien beschreiben.

Zuerst aber wollen wir eine Hierarchie der Formeln der Sprache L(A:;) derArithmetik der zweiten Stufe A:; einführen. Wir sagen, daB eine Formel <p vonL(A:;) arithmetisch ist genau dann, wenn sie keine Quantoren enthâlt, die Men­genvariablen binden. ..:1g bezeichnet die Klasse derjenigen arithmetischen Formeln,die nur beschrânkte Quantoren enthalten, d.h, Quantoren von der Form \:Ix < y,3x < y. Formeln von der Klasse E? sind diejenigen Formeln, die von der Form3XI ... xn 'ljJ(x 1, ... ,Xn , YI, .. ·,yÙ WO 'ljJ E ..:1g, sind und Formeln von der Klasse II?sind Negationen der Formeln von der Klasse E?

Das System RCAo ist eine Theorie, die in der Sprache L(A:;) formalisiert istund deren nicht-logische Axiome sind: (i) PA- (d.h. die Axiome der PeanoschenArithmetik ohne das Induktionsschema), (ii) Induktionsschema für Formelnder KlasseE?, d.h.

<p(O) & \:Ix[<p(x) ---+ <p(Sx)] ---+ \:Ix<p(x) ,

wobei <p eine E? Formel ist, (iii) (rekursives Komprehensionsaxiom)

\:Ix[<p(x) +-+ 'ljJ(x)] ---+ 3X\:Ix(x E X +-+ <p(x)) ,

wobei ip von der Klasse E? und 'ljJ von der Klasse II? sind. [Das Axiom (iii), das aufEnglisch "recursive comprehension axiom" genannt wird, erklârt auch die Abkürzung

3 Es wurde sogar behauptet, daê die Foigen der Resultate der reverse Mathematik "make much of whatwas written in the past on the philosophy of mathematics, obsolete" (vgl. [5]).

4 Die beste Beschreibung der Resultate der reversen Mathematik kann man im Buch [20] finden. Sieheauch [17] und [181;

Page 4: Reverse Mathematik und ihre Bedeutung

lOS R. Murawski

RCAo.] Man kann zeigen, daB (lJto,Rec), wobei Rec die Famille aller rekursivenMengen von natürlichen Zahlen bezeichnet, ein Modell des Systems RCAo ist.

Das System WKLo ist RCAo vermehrt um das schwache Kônigsche Lemma (aufEnglisch: weak Konig's lemma - daraus wird der Name WKLo abgeleitet), DiesesLemma behauptet, daB jeder unendliche binâre Baum einen unendlichen Weg hat(diese Behauptung HiBt sich mit einer Kodierung in der Sprache L(A2) formulieren).Die Theorie WKLo ist stârker als RCAo - das folgt aus der Tatsache, daB (lJto,Rec)kein Modell von WKLo ist.

Die Theorie ACAo ist PA-plus Induktionsaxiom plus arithmetische Komprehen­sion (d.h, Komprehensionsschema fur alle arithmetische Formeln, die auch Mengen­Parameter enthalten kënnen). Dieses System ist stârker als WKLo.

Die oben beschriebenen Teilsysteme der Arithmetik A2 haben sich als angemessenbzgl. verschiedener Teile der klassischen Mathematik erwiesen. In RCAo kann manz.B. reelle Zahlen konstruieren, den Begriff der Konvergenz einer Folge, den Begriffder stetigen Funktion und der integrierbaren Funktion usw. definieren und positiveResultate der rekursiven Analysis und der rekursiven Aigebra beweisen. Insbesonderekônnen die folgenden Sâtze in RCAo bewiesen werden:

(1) Jeder abzâhlbare Kôrper hat eine algebraisch abgeschlossene Hülle.(2) Jeder abzâhlbare geordnete Kërper hat einen reell abgeschlossenen Erweite-

rungskôrper,(3) Der Zwischenwertsatz.

Die Theorie WKLo ist schon ziemlich stark. In ihr kënnen die folgenden Sâtze be­wiesen werden:

(1) Der Heine-Borlesche Überdeckungssatz.(2) JOOe stetige Funktion auf [0,1] ist gleichmâêig stetig.(3) JOOe stetige Funktion auf [0,1] ist beschrânkt.(4) JOOe stetige Funktion auf [0,1] hat ein Supremum.(5) JOOe gfeichmâûig stetige Funktion auf [0,1], die ein Supremum hat, nimmt das

Supremum an.(6) Der Hahn-Banachsche Satz.(7) Der Cauchy-Peanosche Satz über Existenz der Lësungen der gewëhnlichen Dif­

ferentialgleichungen.(8) Jeder abzâhlbare kommutative Ring hat ein Primideal.(9) JOOer abzâhlbare formal reelle Kërper kann geordnet werden.

(l0) JOOer abzâhlbare formal reelle Kërper hat einen reellen Erweiterungskërper.(11) Der Gëdelsche Vollstândigkeitssatz fur den Prâdikatenkalkül,

Wenn umgekehrt Seiner von den oben angeführten Sâtzen ist, dann ist das SystemRCAo plus S zu dem System WKLo âquivalent, d.h. fur jeden Satz cp, kann cp in RCAoplus S bewiesen werden genau dann, wenn cp in WKLo bewiesen werden kann.

Dm die Stârke des Systems ACAo zu zeigen, nennen wir einige Sâtze, die in ACAobewiesen werden kônnen:

(1) Der Bolzano-Weierstrass'sche Satz.(2) Jede Cauchy'sche Folge von reellen Zahlen ist konvergent.(3) Jede beschrânkte Folge von reellen Zahlen hat ein Supremum.(4) Jede beschrânkte wachsende Folge von reellen Zahlen ist konvergent.(5) Der Arzela-Ascolische Satz.(6) Jeder abzâhlbare Vektorraum hat eine Basis.(7) Jeder abzâhlbare kommutative Ring hat ein maximales Ideal.,

Page 5: Reverse Mathematik und ihre Bedeutung

Reverse Mathematik und ihre Bedeutung 109

(8) Jede abzâhlbare Abelsche Gruppe hat eine eindeutig bestimmte teilbare abge­schlossene Hülle.

Und wieder gilt umgekehrt: Sei Seiner von den oben genannten Sâtzen, dann sinddie Theorien RCAo plus Sund ACAo âquivalent,

4. Bedeutung der Resultate der reversen Mathematik

Wir fragen jetzt nach der Bedeutung der Resultate der reversen Mathematik.

Wir bemerken vor allem, daB das Friedmansche Programm der reversen Mathe­matik ein reduktionistisches Programm ist. Man will die ganze gewôhnliche (unfor­malisierte) klassische Mathematik auf die formaie Theorie Aï (oder ihre Teilsysteme)reduzieren und auf diese Weise eine feste Basis fur Mathematik finden. In den konkre­ten Resultaten der reversen Mathematik wurde gezeigt, wieviel von der Arithmetikder zweiten Stufe Aï in der Tat nëtig ist, um bestimmte Sâtze der gewôhnlichenklassischen Mathematik beweisen zu kônnen, Und es ist wirklich interessant, daBbestimmte Fragmente des Systems Aï vollstândig adâquat bzgl. gewisser Teile dergewôhnlichen mathematischen Forschungspraxis sind.

Es gibt aber einige Differenzen. Wenn man die klassische Mathematik in derArithmetik Aï formalisiert, so sind die Beweise der Eindeutigkeit meistens schwe­rer und komplizierter als die Beweise der Existenz, wâhrend es in der gewôhnlichenmathematischen Praxis umgekehrt ist: die Eindeutigkeit ist dort meistens eine trivialeKonsequenz der Existenz. Es gibt ferner auch keine direkte Beziehung zwischen derKomplexitât des klassischen Beweises eines Satzes und der Stufe in der Hierarchieder Teilsysteme von Aï, in der die formalisierte Version des Satzes bewiesen wer­den kann. AIs ein Beispiei kann man hier den Satz erwâhnen, der behauptet, daBjede Abelsche- Gruppe eine Torsions-Untergruppe hat. Dieser Satz ist trivial in derklassischen Aigebra, aber RCAo plus diese Behauptung und die Theorie ACAo sindâquivalent, d.h. diese Behauptung kann nicht z.B. in WKLo bewiesen werden.

Nehmen wir an, daBman einen Satz T in der Zermelo-Fraenkelschen Mengenlehremit dem Auswablaxiom ZFC beweisen kann. Eine natürliche Frage, die man oft stellt,ist dann: kënnte man Tauch elementar beweisen? Die reverse Mathematik kannuns auch hier helfen. Wenn T in der Hierarchie der Teilsysteme von Aï auf einerStufe hôher als RCAo klassifiziert werden muB, dann Iautet die Antwort: NEIN, einabstrakter, infinitistischer Beweis ist notwendig und unentbehrlich.

Die Resultate der reversen Mathematik haben auch direkt mathematische FoI­gen. Nennen wir hier nur ein Beispiel. Wie schon oben angedeutet wurde, kannman im System WKLo den Cauchy-Peanoschen Satz über die Existenz der Lësungender gewëhnlichen Differentialgleichungen beweisen. Auf der anderen Seite bildet dieStruktur (lJlo,Rec) kein Modell dieser Theorie. Aiso gibt es eine Differentialgleichungyi = f(x, y), wo f eine rekursive stetige Funktion ist, die keine rekursive Lôsung hat.

Wir bemerken noch, daB es mathematische Sâtze gibt, die nicht in die Friedman­sche Hierarchie der Teilsysteme von Aï eingestuft werden kënnen. AIs ein Beispielkann man hier den Hilbertschen Basissatz erwâhnen (vgl. [19]). Er behauptet, daB furjeden Kôrper K und fur jede natürliche Zabl n, aIle Ideale im Ring der PolynomeK[Xl, ... , x n ] endlich erzeugt werden kënnen. Dieser Satz ist beweisbar in ACAo,aber RCAo plus drr Hilbertsche Basissatz ist zu keinem bekannten Teilsystem der

Page 6: Reverse Mathematik und ihre Bedeutung

110 R. Murawski

Arithmetik der zweiten Stufe âquivalent". Es gibt auch Sâtze, die in der MengenlehreZFC bewiesen werden kënnen, die aber unbeweisbar in der Arithmetik Ai sind.

Die wichtigste philosophische und methodologische Bedeutung der reversen Ma­thematik ist mit dem Hilbertschen Programm der Begründung der klassischen Mathe­matik verbunden. Wir erinnern daran", daB Hilbert zwischen finitistischer und infi­nitistischer Mathematik unterschied (vgl. [8]). Die finitistische Mathematik ist - lautHilbert - unproblematisch und braucht keine Begriindung. Sie hat mit sogenanntenrealen (finiten) Aussagen zu tun, die vollstândig sinnvoll sind, weil sie sich nur aufkonkrete Objekte berufen und über solche Objekte sprechen. Die infinitistische Mathe­matik hat andererseits mit sogenannten idealen Aussagen zu tun, die eine Berufungauf aktuelle Unendlichkeit enthalten. Hilbert glaubte, daB jeder wahre finitistischeSatz einen finitistischen Beweis habe, daB also infinitistische Objekte und Methodennur eine Hilfsrolle spielen, daB sie es ermëglichen Beweise zu kürzen und einfacherund eleganter zu machen. Aber jeder solche Beweis kënnte durch einen finitistischenBeweis ersetzt werden. Mehr noch, ein nicht konstruktiver Existenzbeweis solI durcheinen konstruktiven ersetzt werden kënnen.

Leider hat Hilbert die Schlüsselbegriffe seines Programms nicht prâzis definiert.Deswegen sind verschiedene Interpretationen der Begriffe môglich (vgl. z.B. [15] woeine Übersicht gegeben ist). Wir werden hier die Taitsche Interpretation annehmen(vgl. [22]). Aiso nehmen wir an, daB das Hilbertsche Finitistische von dem formalenSystem PRA, der primitiv rekursiven Arithmetik (auch Skolemsche Arithmetik ge­nant), erfaBt wird. Das ist eine Theorie der ersten Stufe mit folgenden nicht-logischenZeichen: °(Null), 8 (Nachfolger) und einem Funktionszeichen fur jede primitiv re­kursive Funktion. Die nicht-Iogischen Axiome sind: einige triviale Axiome, die dieTerme 0, 80, 880,... und den Nachfolger 8 beschreiben, Definitionsgleichungen derprimitiv rekursiven Funktionen und das Induktionsschema für Formeln ohne Quan­toren. Diese Theorie ist stark genug, um alle elementaren SchluBfolgerungen übernatürliche Zahlen und endliche Zeichenfolgen darin formalisieren zu kënnen. Einereale Aussage wird bei uns eine Formel der Klasse II? bedeuten, d.h. eine Formelvon der Form Vxcp(x, ...), wobei cp nur beschrânkte Quantoren enthalten kann.

Die infinitistische Mathematik sol1te natürlich nur mit Hilfe der finitistischen Me­thoden begriindet werden - nur sie kônnten Sicherheit geben. Hilbert hat vorgeschla­gen die (infinitistische) Mathematik auf der Basis der finitistischen Mathematik viaBeweistheorie zu sichem. Sein Hauptziel war zu zeigen, daB Beweise von Resulta­ten in dem realen (finitistischen) Teil der Mathematik, die ideale Elemente enthalten,immer richtige Resultate geben. Man kann hier zwei Aspekte unterscheiden: das Wi­derspruchsfreiheitsproblem und das Problem der Konservativitât. Das erste Problembesteht darin, daB man mit Hilfe der finitistischen Methoden zeigt, daB die infinitisti­sche Mathematik widerspruchsfrei ist. Um das zweite Problem zu lôsen, sollte manzeigen, daB die infinitistische Mathematik konservativ über finitistische Mathematikbzgl. realer Aussagen ist, d.h. daBjeder reale Satz, der im infinitistischen Teil der Ma-

5 Bezeichnen wir mit WO(Dt) die Behauptung, daB die Ordinalzahl Dt eine wohlgeordnete Menge ist.Dann kann man in der Theorie RCAo zeigen, daBWO(W W

) mit dem Hilbertschen Basissatz âquivalentist. Aber der Satz WO(W W

) ist unvergleichbar mit WKLo. Auf der anderen Seite fiir jede bestirnrntenatürliche Zabl n kann man in RCAo beweisen, daBder Hilbertsche Satz dem Satz WO(w n ) âquivalentist. Mehr noch, die Behauptung WO(wn ) kann im System RCAo bewiesen werden. Wir haben alsohier eine Analogie mit der w-Unvollstiindigkeit der Peanoschen Arithrnetik, die von Gëdel gezeigtwurde (vgl. [6], siehe auch z.B. [11]).

6 Genauere Beschreibungen des Hilbertschen Programms kann man in verschiedenen Aufsâtzen undBüchern finden.jvgl. z.B. [4] oder [15].

Page 7: Reverse Mathematik und ihre Bedeutung

Reverse Mathematik und ihre Bedeutung 111

thematik bewiesen werden kann, auch im finitistischen Teil bewiesen werden kann.Darüberhinaus soIlte man auch zeigen, daB es eine finitistische Methode gibt, die eineTransformation der infinitistischen BeweisevonrealenSâtzenin finitistische Beweisedieser Sâtze ermëgltcht. Wir bemerken noch, daB diese beiden Aspekte miteinanderverbunden sind (das wurde von G. Kreisel gezeigt - vgl. z.B. [21], S. 858-860).

Hilbert hat auch ein Verfahren zur Verwirklichung seines Programms vorgeschla­gen. Nach ihm so11te man vor allem die Mathematik formalisieren, d.h. die infinitisti­sche Mathematik als ein groBes formales System rekonstruieren. Der zweite Schrittdes Verfahrens so11 aus dem Beweisder Widerspruchsfreiheit und Konservativitât derMathematik bestehen. Weil Formeln des Systems der formalisierten Mathematik ein­fach Zeichenfolgen sind, kann man sie mit Hilfe der finitistischen Mittel betrachtenund auf diese Weise schlieBlich die gewünschten finitistischen Beweise der Wider­spruchsfreiheit und der Konservativitat finden.

Man sollte hier anmerken, daB fur Hilbert die Formalisierung der Mathematiknur ein Mittel, ein Instrument war, mit dem er die klassische Mathematik begründenwoIlte. Er reduzierte nicht - wie Brouwer ihm vorwarf- die ganze Mathematik aufein formales System. Mathematik war fur Hilbert natürlich mehr und etwas anderes,als das bloBe Spiel mit Zeichen.

Hilbert und seine Schüler erzielten einige Erfolge in der Verwirklichung diesesProgramms. Insbesondere W. Ackermann hat mit Hilfeder finitistischen Methoden dieWiderspruchsfreiheit eines Fragments der Arithmetik der natürlichen Zahlen gezeigt(vgl. [1], [2]).

Aber dann kam das Jahr 1931 und die Resultate von K. Gôdel, die die Un­vollstândigkeit der Arithmetik und aller ihrer Erweiterungen zeigten (vgl. [6]). Dererste und der zweite Gëdelsche Satz haben bewiesen, daB das Hilbertsche Programmnicht voIl realisiert werden kann. Sie zeigen, daB man die ganze Mathematik nichtin einem formalisierten System, das auf der Basis des Prâdikatenkalküls aufgebautist, erfassen kann; mehr noch, man kann sogar in einem solchen System nient aIleSâtze über natürliche Zahlen erfassen. Der zweite Gëdelsche Satz zeigte, daB keineformale Theorie, die die Arithmetik der natürlichen Zahlen enthâlt, ihre eigene Wi­derspruchsfreiheit beweisen kann,und daB also in einemWiderspruchsfreiheitsbeweiseiner solchen Theorie stârkere Mittel benutzt werden müssen als diejenigen, die inder betrachteten Theorie vorhanden sind.

Die Gôdelschen Resultate wurden spâternoch veraIlgemeinert und verstârkt". Ins­besondere J. Paris, L. Harrington und L. Kirby haben Beispiele von Satzen gegeben,die wahr aber unentscheidbar in dem formalen System der Peanoschen Arithmetikder natürlichen Zahlen sind und die einen kombinatorlschen" oder sogar zahlentheo­retischen? Inhalthaben.DieseErgebnisse haben deutlich gezeigt, daB das HilbertscheProgramm insgesamt unrealisierbar ist; mehr noch, es ist nient nur fur die ganzeklassische Mathematik unrealisierbar, schon im Falle der Arithmetik der natürlichenZahlen ist eine Realisierung nicht môglich.

In dieser Situation kënnte man fragen: wenn die ganze infinitistische Mathematiknicht finitistisch begründet werden kann, für welche ihrer Teile ist es doch mëglich?Mit anderen Worten: wieviel vonder infinitistischen Mathematik kannin einemforma­len System, das konservativ über der finitistischen Mathematik ist, entwickelt werden?Und auf diese Weise kommen wir zur reversen Mathematik!

7 Diese Untersuchungen sind z.B, in [14] beschrieben8 Das ist der Satz von Paris und Harrington; vgl. [16].9 Das ist der Satz von Kirby und Paris; vgl. [10].

Page 8: Reverse Mathematik und ihre Bedeutung

112 R. Murawski

Am Anfang der achtziger Jahre haben L. Harrington (in Berkeley) und Z. Ra­tajczyk (in Warschau) einen Satz über Konservativitât der Theorie WKLo bewiesen(keiner von ihnen hat den Satz verëffentlicht, den Beweis kann man in [20] finden).

Satz. Sei (œt,..%') ein abzûhlbares Modell der Theorie RCAo und A E ..%'. Dann gibtes eine Familie rv ç @(M) sodajJ A E rv und (œt, rv) ein Modell der TheorieWKLo ist.

Dieser Satz hat eine wichtige syntaktische Konsequenz. Erinnem wir daran, daBni Formeln diejenigen Formeln der Sprache L(A2) sind, die die Form 'r/XIfJ haben,wobei lfJ arithmetisch ist.

Korollar. Die Theorie WKLo ist konservativ über RCAo bzgl. der nf Satze. d.h. jeder!If Satz; der in WKLo bewiesen werden kann, kann schon in RCAo bewiesenwerden.

H. Friedman hat (mit Hilfe modelltheoretischer Mittel) bewiesen, daB die TheorieWKLo konservativ über PRA bzgl. !If Satze ist, wobei rti Formeln von der Form'r/x3ylfJ sind, wobei lfJ nur beschrânkte Quantoren enthaIten kann. W. Sieg hat diesesResultat noch verbessert und eine primitiv rekursive Transformation der Beweise der!If Sâtze in WKLo in Beweise in PRA gegeben.

Alle diese Resultate und die Tatsache, daB die Theorie WKLo sehr stark ist (wasvon der reversen Mathematik gezeigt wurde und was wir oben angedeutet haben)führen zu der folgenden Behauptung: ein grojJer und wichtiger Teil der klassischen(injinitistischen) Mathematik kann jinitistisch reduziert (und begrundet) werden. Unddas zeigt, daB das Hilbertsche Programm - zwar nur teilweise, aber doch dort vollrealisiert werden kann!

Wir weisen darauf hin, daB die Klasse der rti Formeln, fur die die Sâtze vonFriedman und Sieg gelten, ziemlich umfangreich ist - z.B. kënnen viele Sâtze derZahlentheorie aIs nf Formeln ausgedriickt werden. Also kônnen viele zahlentheore­tische Sâtze, -dle in WKLo bewiesen werden kônnen, auch in PRA, also finitistisch,bewiesen (und begründet) werden.

In WKLo kann man den Begriff des komplexen Kurvenintegrals formalisieren.Also kann man jeden !If Satz der Zahlentheorie, der mit Hilfe der Kurvenintegra­tion bewiesen werden kann, auch elementar (d.h. in der Theorie PRA) beweisen!Mehr noch, man kann effektiv (wenigstens theoretisch) einen elementaren Beweiskonstruieren.

Um noch ein Beispiel zu geben, weisen wir darauf hin, daB der Artinsche Satz,der die Lësung des 17. Hilbertschen Problems (vgl. [7]) ist, aIs eine !If Formelgeschrieben werden kann'". AuBerdem kônnen alle Resultate der Theorie der reellabgeschlossenen Kôrper, die man im Beweis des Artinschen Satzes braucht, in derTheorie WKLo bewiesen werden. Somit kommt man zu dem Resultat, daB man denArtinschen Satz in der Skolemschen Arithmetik PRA beweisen kann, daB aIso derSatz einen elementaren Beweis hat.

Wir glauben, daB Hilbert zufrieden gewesen wâre, wenn er solche Resultate ge­sehen hâtte!

10 Hilbert fragte in seinem 17. Problem, "ob nicht jede definite Form [beliebig vie1er Verânderlichenmit reellen Koeffizienten] ais Quotient von Summen von Formenquadraten dargestellt werden kann"(vgI. [7]). Eine Form nennt man definit wenn sie "für keine reellen Werte der Verânderlichen negativausfâllt", lm J~ 1926 hat Artin diese Frage positiv beantwortet.

Page 9: Reverse Mathematik und ihre Bedeutung

Reverse Mathematik und ihre Bedeutung

Literatur

113

[1] Ackermann, W.: Begründung des tertium non datur mittels der Hilbertschen Theorie der Wider­spruchsfreiheit. Math. Ann. 93, 1-36 (1924-25)

[2] Ackermann, W.: Zur Widerspruchsfreiheit der Zahlentheorie, Math. Ann. 117, 162-194 (1940)[3] Apt, K.R., Marek, W.: Second order arithmetic and related topies. Ann. Math. Logic 6, 177-239

(1974)[4] Detlefsen, M.: Hilbert's program. An essay on mathematical instrumentalism, Dordrecht, Boston: D.

Reidel 1986[5] Drake, ER.: On the foundations of mathematics in 1987. In: Ebbinghaus, H.-D. et al. (eds.) Logic

Colloquium'87. Amsterdam: Elsevier 1989[6] Gôdel, K.: Über formaI unentscheidbare Sâtze der 'Principia Mathematica' und verwandter Systeme.

I. Monatsh. Math. Phys. 38, 173-198 (1931)[7] Hilbert, D.: Mathematische Probleme. Arch. Math. Phys. 1,44-64,213-237 (1901). Auch in: Hilbert,

D.: Gesammelte Abhandlungen, Bd. 3. Berlin: Springer 1935[8] Hilbert, D.: Über das Unendliche. Math. Ann. 95, 161-190 (1926)[9] Hilbert, D., Bernays, P.: Grundlagen der Mathematik. Berlin: Springer Bd. 1 1934, Bd. II 1939

[10] Kirby, L., Paris, J.: Accessible independence results for Peano arithmetic. Bull, Lond. Math. Soc. 14,285-293 (1982)

[11] Mendelson, E.: Introduction to mathematicallogic. Princeton, NJ: D. Van Nostrand 1970[12] Murawski, R.: On expandability of models of Peano arithmetic, I-III. Stud. Logica 35, 409--419,

421-431 (1976); 36, 181-188 (1977)[13] Murawski, R: Expandability of models of arithmetic. In: Wechsung, G. (Hrsg.) Proceedings of Frege

Conference 1984. Berlin: Akademie-Verlag 1984[l4] Murawski, R: Generalizations and strengthenings of Gôdel's incompleteness theorem, In: Srzednicki,

J. (ed.) Initiatives in logic. Dordrecht, Boston: Martinus Nijhoff 1987[l5] Murawski, R: Hilbert's program: incompleteness theorems vs. partial realizations. In: Wolenski, J.

(ed.) Philosophicallogic in Poland. Dordrecht: Kluwer 1993[l6] Paris, J., Harrington, L.: A mathematical incompleteness in Peano arithmetic. In: Barwise, J. (ed.)

Handbook of mathematicallogie. Amsterdam: North-Holland 1977[l7] Simpson, S.G.: Friedman's research on subsystems of second order arithmetic. In: Harrington, L., et

al. (eds.) Harvey Friedman research in the foundations of mathematics. Amsterdam: North-Holland1985

[18] Simpson, S.G.: Subsystems of Z2 and reverse mathematics. In: Takeuti, G. (00.) Proof theory. Am-sterdam: North-Holland 1987

[19] Simpson, S.G.: Ordinal numbers and the Hilbert's basis theorem, J. Symb. Logic 53, 961-974 (1988)[20] Simpson, S.G.: Subsystems of second order arithmetic. (In Vorbereitung)[21] Smoryïiski, C.: The incompleteness theorems. In: Barwise, J. (00.) Handbook of mathematica1logic.

Amsterdam: North-Holland 1977[22] Tait, W.W.: Finitism. J. Philos. 78, 524-546 (1981)[23] Weyl, H.: Das Kontinuum. Leipzig: Veit 1918