Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

1. A. Whitehead und B. Russell, Principia Mathematica, 2. Aufl., Cambridge 1925. Zu den Axiomen des Systems PM rechnen wir insbesondere auch: Das Unendlichkeitsaxiom (in der Form: es gibt genau abzählbar viele Individuen), das Reduzibilitäts- und das Auswahlaxiom (für alle Typen).

2. Vgl. A. Fraenkel, Zehn Vorlesungen über die Grundlegung der Mengenlehre, Wissensch. u. Hyp. Bd. XXXI. J. v. Neumann, Die Axiomatisierung der Mengenlehre. Math. Zeitschr. 27, 1928. Journ. f. reine u. angew. Math. 154 (1925), 160 (1929). Wir bemerken, daß man zu den in der angeführten Literatur gegebenen mengentheoretischen Axiomen noch die Axiome und Schlußregeln des Logikkalküls hinzufügen muß, um die Formalisierung zu vollenden. — Die nachfolgenden Überlegungen gelten auch für die in den letzten Jahren von D. Hilbert und seinen Mitarbeitern aufgestellten formalen Systeme (soweit diese bisher vorliegen). Vgl. D. Hilbert, Math. Ann. 88, Abh. aus d. math. Sem. der Univ. Hamburg I (1922), VI (1928). P. Bernays, Math. Ann. 90. J.v.Neumann, Math. Zeitschr. 26 (1927). W. Ackermann, Math. Ann. 93.

3. Dabei werden in PM nur solche Axiome als verschieden gezählt, die aus einander nicht bloß durch Typenwechsel entstehen.

4. Wir verstehen hier und im folgenden unter “Formel aus PM” immer eine ohne Abkürzungen (d. h. ohne verwendung von Definitionen) geschriebene Formel. Definitionen dienen ja nur der kürzeren Schreibweise und sind daher prinzipiell überflüssig.

5. D. h. wir bilden die Grundzeichen in eineindeutiger Weise auf natürliche Zahlen ab. (Vgl. die Durchführung auf S. 179.)

6. D. h. eine Belegung eines Abschnittes der Zahlenreihe mit natürlichen Zahlen. (Zahlen können ja nicht in räumliche Anordnung gebracht werden.)

7. m. a. W.: Das oben beschriebene Verfahren liefert ein isomorphes Bild des Systems PM im Bereich der Arithmetik und man kann alle metamathematischen Überlegungen ebenso gut an diesem isomorphen Bild vornehmen. Dies geschieht in der folgenden Beweisskizze, d. h. unter “Formel”, “Satz”, “Variable” etc. sind immer die entsprechenden Gegenstände des isomorphen Bildes zu verstehen.

8. Es wäre sehr leicht (nur etwas umständlich), diese Formel tatsächlich hinzuschreiben.

9. Etwa nach steigender Gliedersumme und bei gleicher Summe lexikographisch.

10. Durch Überstreichen wird die Negation bezeichnet.

11. Es macht wieder nicht die geringsten Schwierigkeiten, die FormelS tatsächlich hinzuschreiben.

12. Man beachte, daß “[R (q); q]” (oder was dasselbe bedeutet “[S; q]”) bloß eine metamathematische Beschreibung des unentscheidbaren Satzes ist. Doch kann man, sobald man die FormelS ermittelt hat, natürlich auch die Zahlq bestimmen und damit den unentscheidbaren Satz selbst effektiv hinschreiben.

13. Es läßt sich überhaupt jede epistemologische Antinomie zu einem derartigen Unentscheidbarkeitsbeweis verwenden.

14. Ein solcher Satz hat entgegen dem Anschein nichts Zirkelhaftes an sich, denn er behauptet zunächst die Unbeweisbarkeit einer ganz bestimmten Formel (nämlich derq-ten in der lexikographischen Anordnung bei einer bestimmten Einsetzung), und erst nachträglich (gewissermaßen zufällig) stellt sich heraus, daß diese Formel gerade die ist, in der er eelbst ausgedrückt wurde.

15. Die Hinzufügung der Peanoschen Axime ebenso wie alle anderen am System PM angebrachten Abänderungen dienen lediglich zur Vereinfachung des Beweises und sind prinzipiell entbehrlich.

16. Es wird vorausgesetzt, daß für jeden Variablentypus abzählbar viele Zeichen zur Verfügung stehen.

17. Auch inhomogene Relationen können auf diese Weise definiert werden, z. B. eine Relation zwischen Individuen und Klassen als eine Klasse aus Elementen der Form: ((x ₂), ((x ₁),x ₂)). Alle in den PM über Relationen beweisbaren Sätze sind, wie eine einfache Überlegung lehrt, auch bei dieser Behandlungsweise beweisbar.

18. xII(a) ist also auch dann eine Formel, wennx ina nicht oder nicht frei vorkommt. In diesem Fall bedeutetxII(a) natürlich dasselbe wiea.

19. Bez. dieser Definition (und analoger später vorkommender) vgl. J. Łukasiewicz und A. Tarski, Untersuchungen über den Aussagenkalkül, Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie XXIII, 1930, Cl. III.

20. x ₁=y ₁ ist, wie in PM I, * 13 durchx ₂II (x ₂(x ₁) ⊅x ₂(y ₁)) definiert zu denken (ebenso für die höheren Typen).

21. Um aus den angeschriebenen Schemata die Axiome zu erhalten, muß man also (in II, III, IV nach Ausführung der erlaubten Einsetzungen) noch 1. die Abkürzungen eliminieren, 2. die unterdrückten Klammern hinzufügen. Man beachte, daß die so entstehenden Ausdrücke “Formeln” in obigem Sinn sein müssen. (Vgl. auch die exakten Definitionen der metamathem. Begriffe S. 182 fg.)

22. e ist also entweder eine Variable oder O oder ein Zeichen der Formf...f u, wou entweder O oder eine Variable 1. Typs ist. Bez. des Begriffs “frei (gebunden) an einer Stelle vona” vgl. die in Fußnote²⁴) zitierte Arbeit I A 5.

23. Die Einsetzungsregel wird dadurch überflüssig, daß wir alle möglichen Einsetzungen bereits in den Axiomen selbst vorgenommen haben (analog bei j. v. Neumann, Zur Hilbertschen Beweistheorie, Math. Zeitschr. 26, 1927).

24. D. h. ihr Definitionsbereich ist die Klasse der nicht negativen ganzen Zahlen (bzw. dern-tupel von solchen) und ihre Werte sind nicht negative ganze Zhalen.

25. Kleine lateinische Buchstaben (ev. mit Indizes) sind im folgenden immer Variable für nicht negative ganze Zahlen (falls nicht ausdrücklich das Gegeuteil bemerkt ist).

26. Klassen rechner wir mit zu den Relationen (einstellige Relationen). Rekursive RelationenR haben natürlich die Eigenschaft, daß man für jedes spezielle Zahlen-n-tupel entscheiden kann, obR (x ₁...x _n ) gilt oder nicht.

27. Für alle inhaltlichen (insbes. auch die metamathematischen) Überlegungen wird die Hilbertsche Symbolik verwendet. Vgl. Hilbert-Ackermann, Grundzüge der theoretischen Logik, Berlin 1928.

28. Wir setzen als bekannt voraus, daß die Funktionenx+y (Addition),x, y (Multiplikation) rekursiv sind.

29. Andere Werte als 0 und 1 kanna, wie aus der Definition für α ersichtlich ist, nicht annehmen.

30. Das Zeichen ≠ wird im Sinne von “Definitionsgleichheit” verwendet, vertritt also bei Definitionen entweder=oder } (im übrigen ist die Symbolik die Hilbertsche).

31. Überall, wo in den folgenden Definitionen eines der Zeichen(x), (Ex), εx auftritt, ist es von einer Abschätzung fürx gefolgt. Diese Abschätzung dient lediglich dazu, um die rekursive Natur des definierten Begriffs (vgl. Satz IV) zu sichern. Dagegen würde sich der Umfang der definierten Begriffe durch Weglassung dieser Abschätzung meistens nicht ändern.

32. Für 0<n≦z, wennz die Anzahl der verschiedenen inx aufgehenden Primzahlen ist. Man beachte, daß fürn=z+1nPrx=0 ist!

33. m, n≦x steht für:m≦x&n≦x (ebenso für mehr als 2 Variable).

34. DieVariablen u ₁...u _n können willkürlich vorgegeben werden. Es gibt z. B. immer einr mit denfrein Variablen 17, 19, 23... usw., für welches (3) und (4) gilt.

35. Satz V beruht natürlich darauf, daß bei einer rekursiven RelationR für jedesn-tupel von Zahlen aus den Axiomen des SystemsP entscheidbar ist, ob die RelationR besteht oder nicht.

36. Daraus folgt sofort seine Geltung für jede rekursive Relation, da eine solche gleichbedeutend ist mit 0=ϕ (x ₁...x _n ), wo ϕ rekursiv ist.

37. Bei der genauen Durchführung dieses Beweises wird natürlichr nicht auf dem Umweg über die inhaltliche Deutung, sondern durch seine rein formale Beschaffenheit definiert.

38. Welches also, inhaltlich gedeutet, das Bestehen dieser Relation ausdrückt.

39. r entsteht ja aus dem rekursivenRelationszeichen q durch Ersetzen einerVariablen durch eine bestimmte Zahl (p).

40. Die Operationen Gen,Sb sind natürlich immer vertauschbar, falls sie sich auf verschiedeneVariable beziehen.

41. x istz-beweisbar, soll bedeuten:x ε Flg (κ), was nach (7) dasselbe besagt wie: Bew_κ (x).

42. Denn alle im Beweise vorkommenden Existentialbehauptungen beruhen auf Satz V, der, wie leicht zu sehen, intuitionistisch einwandfrei ist.

43. Die Existenz widerspruchsfreier und nicht ω-widerspruchsfreier κ ist damit natürlich nur unter der Voraussetzung bewiesen, daß es überhaupt widerspruchsfreie κ gibt (d. h. daßP widerspruchsfrei ist).

44. Der Beweis von Voraussetzung 1. gestaltet sich hier sogar einfacher als im Falle des SystemsP, da es nur eine Art von Grundvariablen gibt (bzw. zwei bei J. v. Neumann).

45. Vgl. Problem III in D. Hilberts Vortrag: Probleme der Grundlegung der Mathematik. Math. Ann. 102.

46. Der wahre Grund für die Unvollständigkeit, welche allen formalen. Systemen der Mathematik anhaftet, liegt, wie im II. Teil dieser Abhandlung gezeigt werden wird, darin, daß die Bildung immer höherer Typen sich ins Transfinite fortsetzen läßt. (Vgl. D. Hilbert, Über das Unendliche, Math. Ann. 95, S. 184), während in jedem formalen System höchstens abzählbar viele vorhanden sind. Man kann nämlich zeigen, daß die hier aufgestellten unentscheidbaren Sätze durch Adjunktion passender höherer Typen (z. B. des Typus ω zum SystemP) immer entscheidbar werden. Analoges gilt auch für das Axiomensystem der Mengenlehre.

47. Die Null wird hier und im folgenden immer mit zu den natürlichen Zahlen gerechnet.

48. Das Definiens eines solchen Begriffes muß sich also allein mittels der angeführten Zeichen, Variablen für natürlichen Zahlenx, y,... und den Zeichen 0, 1 aufbauen (Funktions- und Mengenvariable dürfen nicht vorkommen). (In den Präfixen darf stattx natürlich auch jede andere Zahlvariable stehen.)

49. f bedeutet hier eine Variable, deren Wertbereich die Folgen natürl. Zahlen sind. Mitf _k wird dask+1-te Glied einer Folgef bezeichnet (mitf _o das erste).

50. Das sind diejenigen ω-widerspruchsfreien Systeme, welche ausP durch Hinzufügung einer rekursiv definierbaren Klasse von Axiomen entstehen.

51. Vgl. Hilbert-Ackermann, Grundzüge der theoretischen Logik. Im SystemP sind unter Formeln des engeren Funktionenkalküls diejenigen zu verstehen, welche aus den Formeln des engeren Funktionenkalküls der PM durch die auf S. 176 angedeutete Ersetzung der Relationen durch Klassen höheren Typs entstehen.

52. In meiner Arbeit: Die Vollständigkeit der Axiome des logischen funktionenkalküls, Monatsh. f. Math. u. Phys. XXXVII, 2, habe ich gezeigt, daß jede Formel des engeren Funktionenkalküls entweder als allgemeingültig nachweisbar ist oder ein Gegenbeispiel existiert; die Existenz dieses Gegenbeispiels ist aber nach Satz IX nicht immer nachweisbar (in den angeführten formalen Systemen).

53. D. Hilbert und W. Ackermann rechnen in dem eben zitierten Buch das Zeichen=nicht zum engeren Funktionenkalkül. Es gibt aber zu jeder Formel, in der das Zeichen=vorkommt, eine solche ohne dieses Zeichen, die mit der ursprünglichen gleichzeitig erfüllbar ist (vgl. die in Fußnote⁵⁵) zitierte Arbeit).

54. Und zwar soll der Definitionsbereich immer der ganze Individuenbereich sein.

55. Variable dritter Art dürfen dabei an allen Leerstellen für Individuenvariable stehen, z. B.:y=φ(x), F(x, φ(y)), G[ψ(x, φ(y)), x] usw.

56. D. h. die Konjunktion bildet.

57. Aus Satz X folgt z.B., daß das Fermatsche und das Goldbachsche Problem lösbar wären, wenn man das Entscheidungsproblem des e.F. gelöst hätte.

58. Satz IX gilt natürlich auch für das Axiomensystem der Mengenlehre und dessen Erweiterungen durch rekursiv definierbare ω-widerspruchsfreie Klassen von Axiomen, da es ja auch in diesen Systemen unentscheidbare Sätze der Form(x)F(x) (F rekursiv) gibt.

59. χ ist widerspruchsfrei (abgekürzt als Wid (χ)) wird folgendermaßen definiert: Wid(χ)≡(Ex) [Form (x)&Bew_κ(x)].

60. Dies folgt, wenn man für χ die leere Klasse vonFormeln einsetzt.

61. r hängt natürlich (ebenso wiep) von κ ab.

62. Von der Definition für “rekursiv” auf Seite 179 bis zum Beweis von Satz VI inkl.

63. Daß aus (23) auf die Richtigkeit vonw Imp (17 Genr) geschlossen werden kann, beruht einfach darauf, daß der unentscheidbare Satz 17 Genr, wie gleich zu Anfang bemerkt, seine eigene Unbeweisbarkeit behauptet.

64. Vgl. J. v. Neumann, Zur Hilbertschen Beweistheorie, Math. Zeitschr. 26, 1927.

Download references