Erstveröffentlichung Mi 16. April 2008; inhaltliche Überarbeitung Mo 13.10.2014
Die Entwicklung der Beweistheorie kann natürlich unterteilt werden in: die Vorgeschichte des Beweisbegriffs in der alten Logik und Mathematik; die Entdeckung von Frege, dass mathematische Beweise und nicht nur die Sätze der Mathematik in einem logischen System dargestellt werden können (und sollten); Hilberts alte axiomatische Beweistheorie; Versagen der Ziele Hilberts durch Gödels Unvollständigkeitssätze; Gentzens Schaffung der beiden Haupttypen logischer Systeme der zeitgenössischen Beweistheorie, der natürlichen Deduktion und der sequentiellen Berechnung (siehe den Eintrag zum automatisierten Denken); Anwendungen und Erweiterungen der natürlichen Deduktion und der sequentiellen Berechnung bis hin zur rechnerischen Interpretation der natürlichen Deduktion und ihrer Verbindungen zur Informatik.
Die Beweistheorie kann als das Studium der allgemeinen Struktur mathematischer Beweise und von Argumenten mit demonstrativer Kraft beschrieben werden, wie sie in der Logik anzutreffen sind. Die Idee solcher demonstrativen Argumente, dh solche, deren Schlussfolgerung notwendigerweise aus den getroffenen Annahmen folgt, ist in Aristoteles 'Analytica Posteriora von zentraler Bedeutung: Eine deduktive Wissenschaft ist um eine Reihe von Grundkonzepten organisiert, von denen angenommen wird, dass sie ohne weitere Erklärung verstanden werden, und um eine Reihe von grundlegenden Wahrheiten oder Axiomen, die sofort als wahr angesehen werden. Definierte Konzepte und Theoreme werden auf diese beiden reduziert, letztere durch Beweise. Aristoteles 'Beweisbericht als demonstratives Argument passt sehr gut zur Struktur der alten Geometrie, wie sie in Euklid axiomatisiert wurde. Die spezifische Form von Aristoteles 'Logik, die Theorie des Syllogismus, hat stattdessen, so scheint es,Fast nichts mit Beweisen in der euklidischen Geometrie zu tun. Diese Beweise blieben mehr als zweitausend Jahre lang intuitiv.
Vor der Arbeit von Frege im Jahr 1879 scheint niemand behauptet zu haben, dass es eine vollständige Reihe von Beweisprinzipien geben könnte, wie Frege es ausdrückte, als er dies in seiner symbolischen Sprache schrieb:
alles, was für eine korrekte Folgerung notwendig ist, wird vollständig ausgedrückt, aber was nicht notwendig ist, wird im Allgemeinen nicht angegeben; nichts bleibt zu raten. (Begriffsschrift, S. 3)
(Man könnte behaupten, dass Boole eine Ausnahme in Bezug auf die klassische Aussagenlogik darstellt.) Freges Fortschritt war entscheidend für die Entwicklung der Logik und der Grundlagenforschung. Der Kontrast zu den Alten ist groß: Aristoteles gab ein Muster für die Kombination von Argumenten an, aber die Idee eines endlichen geschlossenen Regelwerks war philosophisch jenseits der Träume von irgendjemandem vor Frege, mit der möglichen Ausnahme von Leibniz.
Wie wir heute wissen, sind Freges Beweisprinzipien für die klassische Prädikatenlogik vollständig.
Um 1890 gab Giuseppe Peano eine Formalisierung der logischen Folgerung mit dem Ziel, formale Beweise in der Arithmetik darzustellen. Seine wegweisende Arbeit Arithmetices principia, nova methodo exposita, ursprünglich in lateinischer Sprache verfasst, ist in der englischen Übersetzung in der Sammlung From Frege to Gödel (1967) enthalten, die Jean van Heijenoort herausgegeben hat. Leider erkannte der Herausgeber nicht, was Peano mit formalen Schlussfolgerungen tat, und die Ansicht verbreitete sich, dass Peano nur die Sprache der Logik und der Arithmetik formalisierte, nicht ihre Beweisprinzipien. Wenn Peanos Beweise auch nur mit ein wenig Sorgfalt gelesen werden, stellt sich heraus, dass es sich um rein formale Ableitungen handelt, die zwei Prinzipien verwenden:
Axiome implizieren ihre Instanzen. Solche Implikationen können als Zeilen in Beweisen geschrieben werden.
Eine Implikation und ihre Vorgeschichte implizieren zusammen die Konsequenz.
Peano ist sehr darauf bedacht, in jeder Zeile seiner Ableitungen den formalen Grund für das Schreiben der Zeile aufzulisten.
Russell griff Freges Logik auf, verwendete jedoch die Notation und die formalen Beweisregeln von Peano in einem Artikel von 1906 mit dem Titel "The Theory of Implication". Seine formale Maschinerie ist genau die gleiche wie die von Peano. In späteren Arbeiten änderte Russell das axiomatische System und das von Principia Mathematica (Whitehead und Russell 1910–13) wurde zum Standard. Russells philosophische Idee, und hier folgte er Frege, war, dass die Axiome grundlegende logische Wahrheiten ausdrücken und andere logische Wahrheiten aus diesen durch Modus Ponens und universelle Verallgemeinerung abgeleitet werden, die beiden Prinzipien, die Frege identifiziert hatte. Die Mathematik sollte auf die Logik reduziert werden, damit ihre Beweise im gleichen axiomatischen Muster präsentiert werden.
Freges und Peano-Russells Ansatz zur Logik wurde allgemein akzeptiert, insbesondere durch den Einfluss von Hilbert und seinen Mitarbeitern in den 1920er Jahren. Im 19. Jahrhundert war Frege eine Randfigur, und die algebraische Herangehensweise an die Logik, wie bei Boole und insbesondere bei Ernst Schröder, war die dominierende. Es ist klar, dass es in dieser Tradition ein gutes Verständnis der Prinzipien der Prädikatenlogik gab, denn wie hätte es sonst einen Löwenheim-Skolem-Satz geben können? Skolem erfuhr von Freges Logik durch Principia Mathematica erst, nachdem er den Satz in seiner Arbeit von 1920 ausgearbeitet hatte. Der erste Abschnitt dieser Arbeit, der aufgrund der englischen Übersetzung in Van Heijenoorts From Frege to Gödel weithin gelesen wurde, markiert das Ende der Algebra Tradition der Logik, die stillschweigend mit der Gittertheorie verschmolz. Andere Abschnitte der Arbeit enthalten einen bemerkenswerten Beginn der Analyse von Beweisen in der Gittertheorie und in der projektiven Geometrie: Skolem betrachtete die Axiome einer mathematischen Theorie aus rein kombinatorischer und formaler Sicht als Mittel zur Herstellung von Ableitungen einer Formel aus gegebener Form Formeln als Annahmen verwendet. Anfang der neunziger Jahre wurde herausgefunden, dass der Teil zur Gittertheorie die Lösung eines Entscheidungsproblems enthält, das als Wortproblem für frei erzeugte Gitter bezeichnet wird und dessen bekannte Lösung aus dem Jahr 1988 stammt! Skolems Terminologie und Notation in der Gittertheorie sind die von Schröder, und das ist ein Teil des Grundes, warum seine Arbeit eine verpasste Gelegenheit für die Beweistheorie war. Skolem betrachtete die Axiome einer mathematischen Theorie aus rein kombinatorischer und formaler Sicht als Mittel zur Herstellung von Ableitungen einer Formel aus gegebenen Formeln, die als Annahmen verwendet wurden. Anfang der neunziger Jahre wurde herausgefunden, dass der Teil zur Gittertheorie die Lösung eines Entscheidungsproblems enthält, das als Wortproblem für frei erzeugte Gitter bezeichnet wird und dessen bekannte Lösung aus dem Jahr 1988 stammt! Skolems Terminologie und Notation in der Gittertheorie sind die von Schröder, und das ist ein Teil des Grundes, warum seine Arbeit eine verpasste Gelegenheit für die Beweistheorie war. Skolem betrachtete die Axiome einer mathematischen Theorie aus rein kombinatorischer und formaler Sicht als Mittel zur Herstellung von Ableitungen einer Formel aus gegebenen Formeln, die als Annahmen verwendet wurden. Anfang der neunziger Jahre wurde herausgefunden, dass der Teil zur Gittertheorie die Lösung eines Entscheidungsproblems enthält, das als Wortproblem für frei erzeugte Gitter bezeichnet wird und dessen bekannte Lösung aus dem Jahr 1988 stammt! Skolems Terminologie und Notation in der Gittertheorie sind die von Schröder, und das ist ein Teil des Grundes, warum seine Arbeit eine verpasste Gelegenheit für die Beweistheorie war.nannte das Wort Problem für frei erzeugte Gitter, deren bekannte Lösung aus dem Jahr 1988 stammte! Skolems Terminologie und Notation in der Gittertheorie sind die von Schröder, und das ist ein Teil des Grundes, warum seine Arbeit eine verpasste Gelegenheit für die Beweistheorie war.nannte das Wort Problem für frei erzeugte Gitter, deren bekannte Lösung aus dem Jahr 1988 stammte! Skolems Terminologie und Notation in der Gittertheorie sind die von Schröder, und das ist ein Teil des Grundes, warum seine Arbeit eine verpasste Gelegenheit für die Beweistheorie war.
2. Hilberts alte axiomatische Beweistheorie
Hilberts Buch Grundlagen der Geometrie von 1899 bildete die Grundlage für die zentralen Grundprobleme der Mathematik der frühen Jahrzehnte des 20. Jahrhunderts. Wir können diese Probleme wie folgt auflisten:
Die Formalisierung einer mathematischen Theorie. Dies beinhaltet eine Auswahl seiner grundlegenden Objekte und Beziehungen sowie eine Auswahl der Axiome.
Ein Beweis für die Konsistenz der Axiome.
Die Frage der gegenseitigen Unabhängigkeit und Vollständigkeit der Axiome.
Das Entscheidungsproblem: Gibt es eine Methode zur Beantwortung von Fragen, die innerhalb der Theorie aufgeworfen werden könnten?
In Bezug auf Hilberts Geometrie blieb die versuchte Formalisierung hinter dem Ideal zurück, das sie hervorgebracht hatte. Hilbert fand ein viel wichtigeres Gebiet, auf das seine „Metamathematik“angewendet werden sollte, nämlich Arithmetik und Analyse. Die Grundlage war eine Untersuchung der vier Grundprobleme in axiomatischen Formulierungen der reinen Logik. Die Aussagenlogik wurde somit formalisiert, als konsistent und vollständig und entscheidbar befunden. Die ersten Ergebnisse zur Prädikatenlogik stammen aus dem Jahr 1915, als Leopold Löwenheim seine Version des später zum Löwenheim-Skolem-Theorem für Prädikatenlogik gewordenen Satzes gab (siehe Eintrag zur klassischen Logik). Er löste auch Sonderfälle des Entscheidungsproblems. Diese Entwicklung war unabhängig von der Frege-Russell-Tradition und basierte stattdessen auf dem algebraischen Ansatz der Logik von Ernst Schröder. Um 1920,Der axiomatische Ansatz des „Hilbert-Stils“, wie er oft genannt wird, war allen bekannt und dominierte die logische Szene. Der algebraische Ansatz verschmolz fast ohne Vorankündigung mit der Gittertheorie. Bis 1928 wurde in Hilbert und Ackermanns Grundzüge der theoretischen Logik ein axiomatisches formales System für die Prädikatenlogik zusammen mit dem Problem ihrer Vollständigkeit vorgestellt. Letzteres wurde 1929 von Gödel gelöst und ein Jahr später veröffentlicht (Gödel 1930). Das vierte Grundproblem, das Entscheidungsproblem für die Prädikatenlogik, wurde 1936 in einem kurzen Artikel der Kirche als Folge von Gödels Unvollständigkeitssatz als negativ gelöst gezeigt.s Grundzüge der theoretischen Logik, ein axiomatisches formales System für Prädikatenlogik, wurde zusammen mit dem Problem seiner Vollständigkeit vorgestellt. Letzteres wurde 1929 von Gödel gelöst und ein Jahr später veröffentlicht (Gödel 1930). Das vierte Grundproblem, das Entscheidungsproblem für die Prädikatenlogik, wurde 1936 in einem kurzen Artikel der Kirche als Folge von Gödels Unvollständigkeitssatz als negativ gelöst gezeigt.s Grundzüge der theoretischen Logik, ein axiomatisches formales System für Prädikatenlogik, wurde zusammen mit dem Problem seiner Vollständigkeit vorgestellt. Letzteres wurde 1929 von Gödel gelöst und ein Jahr später veröffentlicht (Gödel 1930). Das vierte Grundproblem, das Entscheidungsproblem für die Prädikatenlogik, wurde 1936 in einem kurzen Artikel der Kirche als Folge von Gödels Unvollständigkeitssatz als negativ gelöst gezeigt.
Hilbert und seine Schule, mit Bernays, Ackermann und von Neumann an erster Stelle sowie dem jungen Herbrand in Frankreich, verfolgten Ende der 1920er Jahre das metamathematische Studium der Arithmetik. Hilbert entwickelte eine Methode zur Untersuchung von Konsistenzproblemen, die als Epsilon-Substitutionsmethode bezeichnet wird, um mit den Quantifizierern umzugehen. Er war der Ansicht, dass indirekte Schlussfolgerungen mit Quantifizierern in Fällen mit unendlich vielen Objekten der entscheidende Punkt für Konsistenznachweise waren und eine Begründung benötigten. Wenn die Annahme, dass alle natürlichen Zahlen die Eigenschaft P haben, zu einer Unmöglichkeit führt, kann auf die Existenz einer Zahl mit der entgegengesetzten Eigenschaft nicht P geschlossen werden. Das zentrale Problem bestand daher darin, die Verwendung der klassischen Logik in mathematischen Beweisen zu rechtfertigen, in erster Linie in arithmetischen. Gegen Ende der 1920er Jahre war Ackermann einer Lösung sehr nahe und in der Hilbert-Schule herrschte Optimismus. Dann geschah natürlich das Unerwartete, als Gödel die Unmöglichkeit einer vollständigen Formalisierung der Elementararithmetik und, wie bald interpretiert wurde, die Unmöglichkeit bewies, die Konsistenz der Arithmetik mit endlichen Mitteln zu beweisen, die einzigen, die von „absolut zuverlässig“beurteilt wurden Hilbert.
3. Die Unbeweisbarkeit der Konsistenz
Nachdem Gödel im September 1930 die Unvollständigkeit der Arithmetik veröffentlicht hatte, stellte von Neumann fest, dass die Konsistenz der Arithmetik zu den unbeweisbaren Aussagen von Gödel gehören würde. Leider hatte Gödel die gleiche Entdeckung gemacht, so dass von Neumann seinen Beweis nie veröffentlichte. Er vermutete jedoch in Übereinstimmung mit Gödel die Unbeweisbarkeit der Konsistenz der Arithmetik und damit der Mathematik als Ganzes in einem absoluten Sinne. Von Neumann war die Schlüsselfigur bei der Rezeption von Gödels Ergebnissen: Er unterbrach im Herbst 1930 in Berlin seine Vorlesungen über Hilberts Beweistheorie, um die neuen Entdeckungen zu erklären. Diese Ereignisse erregten unter den Mathematikern eine enorme Aufregung, wie Carl Hempels Zeugnis bezeugt:
Ich habe dort einen Kurs bei von Neumann besucht, der sich mit Hilberts Versuch befasste, die Konsistenz der klassischen Mathematik mit endlichen Mitteln zu beweisen. Ich erinnere mich, dass von Neumann mitten im Kurs an einem Tag kam und bekannt gab, dass er gerade eine Arbeit von… Kurt Gödel erhalten hatte, der zeigte, dass die Ziele, die Hilbert im Sinn hatte und auf denen ich Hilberts Kurs in Göttingen gehört hatte, nicht konnten überhaupt erreicht werden. Von Neumann ließ daher die Verfolgung dieses Themas fallen und widmete den Rest des Kurses der Präsentation von Gödels Ergebnissen. Der Befund rief eine enorme Aufregung hervor. (Hempel 2000, S. 13)
In den Jahren 1932 bis 1933 fanden Gödel und Gentzen unabhängig voneinander eine Übersetzung von der klassischen Peano-Arithmetik zur intuitionistischen Heyting-Arithmetik. Insbesondere zeigt es, dass ein Widerspruch, der im ersteren nachweisbar ist, im letzteren nachweisbar ist. Dann würde die Konsistenz der intuitionistischen Arithmetik auch die Konsistenz der klassischen Arithmetik garantieren. Dieses Ergebnis war überraschend: Wie bereits erwähnt, hatte Hilbert gedacht, dass die „transfiniten“indirekten Existenzbeweise der Teil der Arithmetik sein würden, der gegen Widersprüche gesichert werden muss. Nach dem Ergebnis von Gödel und Gentzen enthielt die bereits intuitionistische Arithmetik Prinzipien, die über das endgültige Denken hinausgingen. Ein Brief, den Gentzen am 25. Februar 1933 an Heyting schrieb, fasst die Situation wie folgt zusammen:
Ein Konsistenznachweis mit endlichen Mitteln ist… bisher nicht gelungen, so dass dieses ursprüngliche Ziel von Hilbert nicht erreicht wurde. Wenn man andererseits die intuitionistische Position als sichere Basis an sich zugibt, dh als konsistente, ist die Konsistenz der klassischen Arithmetik durch mein Ergebnis gesichert. Wenn man Hilberts Anforderungen erfüllen wollte, blieb die Aufgabe, intuitionistische Arithmetik konsistent zu zeigen. Dies ist jedoch selbst mit dem formalen Apparat der klassischen Arithmetik auf der Grundlage von Gödels Ergebnis in Kombination mit meinem Beweis nicht möglich. Trotzdem neige ich dazu zu glauben, dass ein Konsistenznachweis für intuitionistische Arithmetik aus einer noch offensichtlicheren Position möglich und auch wünschenswert ist. (Menzler-Trott 2007, S. 38)
Das letztgenannte war das Ziel, das sich Gentzen Anfang 1932 gesetzt hatte, als er in einem Brief an seinen alten Lehrer Hellmuth Kneser schrieb:
Ich habe es mir zur Aufgabe gemacht, einen Beweis für die Konsistenz der logischen Deduktion in der Arithmetik zu finden. Die Aufgabe wird durch die Formalisierung der logischen Deduktion zu einem rein mathematischen Problem. Der Konsistenznachweis wurde bisher nur für Sonderfälle durchgeführt, beispielsweise die Arithmetik der ganzen Zahlen ohne die Regel der vollständigen Induktion. Ich möchte an dieser Stelle weiter vorgehen und zumindest die Arithmetik mit vollständiger Induktion klären. Ich arbeite seit fast einem Jahr daran und hoffe, bald fertig zu werden, und würde diese Arbeit dann als meine Dissertation (mit Prof. Bernays) präsentieren. (Menzler-Trott 2007, S. 31)
4. Natürlicher Abzug und sequentielle Berechnung
Bei der Verfolgung seines Konsistenzprogramms stellte Gentzen als erste Aufgabe die Analyse der rein logischen Deduktion auf, die später auf Arithmetik und Analyse ausgedehnt werden sollte. In seiner Dissertation (1934–1935) stellt Gentzen fest, dass er es sich zur Aufgabe gemacht hat, mathematische Beweise so zu analysieren, wie sie in der Praxis vorkommen. Die erste Beobachtung ist, dass tatsächliche Beweise nicht auf Axiomen basieren, die in einer logischen Sprache ausgedrückt werden, wie in Hilberts axiomatischer Beweistheorie. Das typischste Merkmal ist stattdessen, dass Theoreme ihre Behauptungen unter bestimmten Annahmen aufstellen. Die Annahmen werden in Teile analysiert und die Schlussfolgerung wird auch in Teile analysiert, bis sich diese beiden Analysen treffen und ein Beweis synthetisiert werden kann. Die letztere Analyse erfolgt nach den von Gentzen als Einführungsregeln bezeichneten Regeln: Sie bieten ausreichende Bedingungen, um einen Satz einer bestimmten Form abzuleiten. Beispielsweise,Um eine Konjunktion A & B abzuleiten, ist es ausreichend, die Konjunktionen A und B getrennt abzuleiten. Die Schlussfolgerung wird formal wie in der Regel gegeben
AB
&ICH
A & B.
Annahmen werden stattdessen durch Eliminierungsregeln in ihre Komponenten analysiert, die im Großen und Ganzen unmittelbare Konsequenzen der Annahmen haben. Beispielsweise kann eine als Annahme verwendete Konjunktion wie in den Regeln in ihre Bestandteile zerlegt werden
A & B.
& E 1
EIN
A & B.
& E 2
B.
Gentzen entwickelte und studierte 1932 das System des natürlichen Abzugs und war bis September 1932 zu einem heute üblichen Kalkül des natürlichen Abzugs (kurz ND) gelangt. Zu diesem Zeitpunkt hatte er bemerkt, dass, wenn auf eine Einführung, beispielsweise eine Ableitung von A & B von A und B getrennt, die entsprechende Eliminierung folgt, beispielsweise eine Ableitung von A, die Formel A & B ein lokales Maximum darstellt, a “Hügel “, der beseitigt werden kann. Er nannte solche Hügel auch „Umwege“, und was jetzt als Umwegumwandlung bezeichnet wird, entfernt solche unnötigen Paare von Einführungs- / Eliminierungsschritten. Das Ergebnis der Schritte der "Normalisierung" ist eine Ableitung in "normaler Form".
Die Implikation ist vielleicht typischer für ND als die Konjunktion: Um A ⊃ B abzuleiten, nimmt man vorübergehend A an und versucht dann, B abzuleiten. Gelingt dies, wird die vorübergehende Annahme geschlossen oder „entladen“, wenn die Schlussfolgerung zu A ⊃ B gezogen wird, wie in der schematischen Ableitung
[EIN]
⋮
B.
⊃I
A ⊃ B.
In der anderen Richtung kann A ⊃ B eliminiert werden, wenn eine Ableitung von A gefunden wurde, denn dann kann B geschlossen werden:
A ⊃ BA
⊃E
B.
Wenn auf Regel ⊃I ⊃E folgt, gibt es eine Nichtnormalität, die durch eine Umleitungsumwandlung beseitigt wird: Eine Ableitung von B (und was danach folgt) wird konstruiert, indem die Ableitung der Nebenprämisse A der Eliminierungsregel genommen wird und die Ableitung von B aus der Annahme A in der Einleitung. Diese beiden Teile werden zu einer Ableitung von B kombiniert, die nicht die Umleitungsformel A ⊃ B hat. In Gentzens These werden alle Annahmen letztendlich durch implizite Einführungen geschlossen, aber heutzutage betrachtet man auch Ableitungen, die eine Sammlung von Formeln hinterlassen, als offene Annahmen.
Wenn man die Regeln der Konjunktion und Implikation betrachtet, stellt man fest, dass die Prämissen (die Formeln unmittelbar über der Inferenzlinie) Unterformeln der Schlussfolgerung in den I-Regeln sind, während es in den E-Regeln umgekehrt ist. Gentzen bemerkte, dass bei normalen Ableitungen diese Eigenschaft einzelner Schritte von der gesamten Ableitung in dem Sinne vererbt wird, dass alle Formeln Unterformeln der Schlussfolgerung sind. Dieses Ergebnis ergab als Nebenprodukt eine Entscheidungsmethode für die intuitionistische Aussagenlogik. Eine weitere Folge war ein syntaktischer Beweis der Konsistenz: Wenn ein Widerspruch beweisbar ist, ist alles beweisbar, aber eine Atomformel hat beispielsweise keinen Beweis: Wenn sie einen Beweis hat, hat sie einen normalen Beweis, aber es gelten keine E-Regeln für a Atomformel, und keine I-Regel schließt es auch.
Gentzens Idee war es, die natürliche Deduktion durch Hinzufügen einer Regel, die dem Prinzip der vollständigen Induktion entspricht, auf ein arithmetisches System auszudehnen. Die Konsistenz würde sich dann aus der Normalisierung der Ableitungen und der Subformeleigenschaft ergeben. Anfang 1933 erkannte Gentzen, dass diese Beweisstrategie nicht durchgehen würde: Die Induktionsregel ist schematisch und hat unendlich viele Instanzen, ohne an die Komplexität der Induktionsformeln gebunden zu sein. Es wäre unmöglich, diese Formeln im Voraus einzuschränken, daher kann keine Subformeleigenschaft gelten. Nach diesem Misserfolg nahm Gentzen die Übersetzung von klassischer zu intuitionistischer Arithmetik wörtlich aus seinem Manuskript der frühen Dissertation und reichte sie im März 1933 als Papier ein, zog das Papier jedoch zurück, nachdem er von Gödels Veröffentlichung des Ergebnisses erfahren hatte.
Gentzen schrieb, dass er keinen Normalisierungssatz für ein klassisches ND-System beweisen konnte. Er erfand daher einen anderen logischen Kalkül, den er Sequenzkalkul nannte, und machte ihn zum zentralen Thema seiner Arbeit. Der Name des Kalküls ergibt sich aus der Darstellung von Annahmen einer Ableitung als Liste. Das als Substantiv verwendete Wort „sequent“ist ein Vorschlag von Kleene in seiner Einführung in die Metamathematik (1952: 441), die in vielen Sprachen in Form von rein erfundenen Wörtern aufgegriffen wurde.
Sequent Calculus, kurz SC, kann als formale Darstellung der Ableitbarkeitsrelation in der natürlichen Deduktion angesehen werden. Eine Sequenz besteht aus einer Liste Γ von Formeln, einem Pfeil (in Gentzen wurden später auch andere Marker verwendet) und einer Formel als Schlussfolgerung. Die Liste gibt die Annahmen an, von denen die Schlussfolgerung in einer Ableitung abhängt, in einer lokalen Notation, wo sie in ND in den Blättern eines Ableitungsbaums gefunden werden. Gentzen verallgemeinerte auch Sequenzen, so dass sie anstelle einer Schlussfolgerung eine Liste möglicher Fälle nach dem Pfeil haben. Diese Neuheit führte zur ersten zufriedenstellenden Formulierung eines Beweissystems für die klassische Logik. Gentzens SC-Regeln für Konjunktion und Implikation lauten durch Kommas, die Elemente in Listen trennen:
Verbindung
Γ → Δ, A Γ → Δ, B.
R &
Γ → Δ, A & B.
A, Γ → Δ
L & 1
A & B, Γ → Δ
B, Γ → Δ
L & 2
A & B, Γ → Δ
Implikation
A, Γ → Δ, B.
R⊃
Γ → Δ, A ⊃ B.
Γ → Θ, AB, Δ → Λ
L⊃
A ⊃ B, Γ, Δ → Θ, Λ
Dies ist nicht der Ort, um die Details von ND und SC zu erklären (siehe jedoch den Eintrag zum automatisierten Denken). Gentzen formulierte letzteres mit LK, so dass es einen intuitionistischen Kalkül mit der Bezeichnung LJ als Sonderfall gab, in dem die Schlussfolgerung eine Liste von höchstens einem Fall ist. Er bewies dann das Analogon des Normalisierungssatzes für den klassischen Kalkül, den Kalkül und den sorgfältig formulierten Beweis, so dass das Ergebnis für den intuitionistischen Kalkül ein Sonderfall des Ergebnisses für den klassischen Kalkül war. In LJ und LK steht L für „logistisch“, ein Begriff, mit dem Gentzen sich auf die axiomatischen Logikkalküle von Frege, Russell, Hilbert und Bernays bezieht. In solchen Kalkülen ist jede Zeile in einer Ableitung für sich korrekt, dh eine logische Wahrheit, woher der Begriff stammt. Die Buchstaben K und J stammen aus den deutschen Wörtern klassisch und intuitionistisch.(Letzteres sollte also Großbuchstaben "I" sein, ältere Deutsche verwenden jedoch Großbuchstaben "J" für Großbuchstaben "I".)
Gentzen nannte das Analogon der Normalisierung mit dem einfallslosen Namen Hauptsatz „Hauptsatz“. Die heutige Standardterminologie lautet „Cut Elimination Theorem“. Alle logischen Regeln von SC haben die Subformeleigenschaft in einem sehr unmittelbaren Sinne: Jede Formel in einer Prämisse ist eine Formel oder Subformel in der Schlussfolgerung. Die Regel zum Kombinieren von Ableitungen, analog zu der oben für den Fall von Umleitungsumwandlungen in ND erläuterten, wird als "Schneiden" bezeichnet. Darin erscheint eine Formel A als Fall in einer ersten Prämisse und als Annahme in einer zweiten Prämisse. Zusammenfassend ist diese Formel verschwunden und die Annahmen der beiden Prämissen sind zusammengefasst:
Γ → AA, Δ → C.
Schnitt
Γ, Δ → C.
Daher ist cut die einzige Regel, die eine Formel in einer Ableitung „verschwinden“lässt. Gentzen hat gezeigt, dass Instanzen der Schnittregel aus Ableitungen eliminiert werden können, indem sie nach oben permutiert werden, bis sie Punkte erreichen, an denen die Ableitung beginnt. In ND sind die Ausgangspunkte Annahmen, in SC sind sie „Anfangssequenzen“der Form A → A, in denen die Annahmeformel A gleichzeitig die Schlussfolgerung ist. Ein Schnitt mit einer Folge wie einer Prämisse hat die andere Prämisse gleich der Schlussfolgerung und kann daher gelöscht werden.
Nach dem Nachweis der Schnitteliminierung hatte Gentzen keine Verwendung für den Normalisierungsnachweis für die intuitionistische natürliche Ableitung. Er gab Bernays die erste handschriftliche Version seiner These mit dem detaillierten Normalisierungsnachweis (entspricht etwa 13 gedruckten Seiten), aber dieser scheint nie bemerkt zu haben, was er in seinen Händen hatte. Der Beweis unter den Arbeiten von Bernays in Zürich wurde vom vorliegenden Autor im Februar 2005 entdeckt und ist jetzt in englischer Übersetzung verfügbar (Gentzen 1933 [2008]).
5. Die Konsistenz von Arithmetik und Analyse
Nach seiner Diplomarbeit über ND und SC für reine Logik setzte Gentzen seinen Plan fort, die Konsistenz der Arithmetik zu beweisen. Das Ergebnis war im Dezember 1934 fertig. Was dieser allererste Beweis war, ist nicht im Detail bekannt. Ein Brief an Bernays aus dem Jahr 1938 zeigt jedoch, dass der Beweis, den Gentzen bis zum Sommer 1935 niederschrieb, nicht dieser ursprüngliche, sondern ein zweiter Beweis war (siehe Menzler-Trott 2001, 79). Dieser zweite Beweis wurde von Bernays und Gödel kritisiert, die ihn während ihrer Atlantikreise nach Princeton im September 1935 diskutierten die Formalisierung der Arithmetik. Schreiben Sie dann jede Regelinstanz so, dass die Prämissen und Schlussfolgerungen die links aufgeführten offenen Annahmen haben.mit einem Pfeil, der die Schlussfolgerung trennt, also als Sequenz. Diese Variante von ND heißt jetzt ND im SC-Stil. Betrachten Sie eine Folge Γ →C. Wenn seine Schlussfolgerung eine Atomformel ist, ist es eine Gleichung zwischen Zahlen. Im schlimmsten Fall ist es falsch, also betrachten Sie die Liste der Annahmen. Wenn eine Annahme eine Konjunktion ist, ersetzen Sie sie durch eine Konjunktion Ihrer Wahl, wenn es sich um eine universelle Quantifizierung handelt, durch eine Instanz. Wenn es sich um eine Negation ¬ A handelt, ersetzen Sie die Schlussfolgerung durch A. Wenn in irgendeinem Stadium dieses „Reduktionsprozesses“die Schlussfolgerung einer Sequenz eine zusammengesetzte Formel ist, müssen Sie eine Konjunktion oder einen Fall einer universellen Quantifizierung als mögliche Schlussfolgerung betrachten. Im Falle der Negation ¬ A als Schlussfolgerung bewegen Sie A zum Annahme-Teil und ersetzen Sie die Schlussfolgerung durch 0 = 1. Gentzen zeigt, dass auf diese Weise unter der Annahme, dass die fragliche Folge ableitbar ist, entweder eine wahre Gleichung gefunden wird als Schlussfolgerung oder eine falsche Gleichung als Annahme. So,Es gibt keine ableitbaren Sequenzen, bei denen alle Annahmen wahr und die Schlussfolgerung falsch sind.
Gödel und Bernays war unklar, was der Beweis voraussetzte; Sie dachten, es würde angenommen, was in der intuitionistischen Mathematik als Fan-Theorem bekannt ist, aber das war falsch. Die Beendigung des Gentzen-Reduktionsverfahrens kann stattdessen durch Induktion an fundierten Bäumen („Balkeninduktion“) nachgewiesen werden, ein Prinzip, das von Gentzen aus intuitiven Gründen angewendet wurde. Das Ergebnis der Kritik war jedenfalls, dass Gentzen den Beweis ohne weiteres in einen dritten Beweis umwandelte, der das inzwischen berühmte Prinzip der transfiniten Induktion bis zur ersten Epsilon-Zahl verwendet. Diese Induktion wurde durch eine Codierung dargestellt, die Dezimalzahlen verwendete. Das konkrete Ergebnis der Änderungen für Gentzens 1936 veröffentlichtes Papier war jedoch nicht gut: Der logische Kalkül wurde auf halbem Weg in einem Artikel von etwa siebzig Seiten geändert, der sehr schwer zu lesen war. Daher gab Gentzen 1938 einen weiteren, nach heutiger Zählung vierten Beweis für die Konsistenz der Arithmetik (im Bernays-Archiv der ETH Zürich), diesmal basierend auf der klassischen Folgekalkül LK von 1933. Wie bereits erwähnt, weist die Korrespondenz mit Bernays darauf hin Damit kehrte er zu der Beweismethode zurück, die 1934 zum Erfolg geführt hatte. Die Verwendung der transfiniten Induktion wird in der Arbeit von 1938 durch eine Ordnungsnotation deutlich sichtbar gemacht. Solche Induktionsprinzipien zu Cantors „zweiter Zahlenklasse“werden in Hilberts 1925er Vorlesung „Über das Unendliche“(1926), auf die Gentzen Bezug nahm, ausführlich erörtert.diesmal basierend auf dem klassischen sequentiellen Kalkül LK von 1933. Wie bereits erwähnt, weist die Korrespondenz mit Bernays darauf hin, dass er damit zu der Beweismethode zurückkehrte, die 1934 zum Erfolg geführt hatte. Die Verwendung der transfiniten Induktion wird in der Arbeit von 1938 durch eine Ordnungsnotation. Solche Induktionsprinzipien zu Cantors „zweiter Zahlenklasse“werden in Hilberts 1925er Vorlesung „Über das Unendliche“(1926), auf die Gentzen Bezug nahm, ausführlich erörtert.diesmal basierend auf dem klassischen sequentiellen Kalkül LK von 1933. Wie bereits erwähnt, weist die Korrespondenz mit Bernays darauf hin, dass er damit zu der Beweismethode zurückkehrte, die 1934 zum Erfolg geführt hatte. Die Verwendung der transfiniten Induktion wird in der Arbeit von 1938 durch eine Ordnungsnotation. Solche Induktionsprinzipien zu Cantors „zweiter Zahlenklasse“werden in Hilberts 1925er Vorlesung „Über das Unendliche“(1926), auf die Gentzen Bezug nahm, ausführlich erörtert.s Vorlesung „Über das Unendliche“von 1925 („Über das Unendliche“, veröffentlicht 1926), auf die sich Gentzen bezog.s Vorlesung „Über das Unendliche“von 1925 („Über das Unendliche“, veröffentlicht 1926), auf die sich Gentzen bezog.
Man hätte gedacht, dass das das war, aber Gentzen hatte Grund, in seinem letzten 1943 veröffentlichten, aber vor dem Krieg 1939 verfassten Artikel noch einen vierten Beweis für die Konsistenz der Arithmetik vorzulegen. Er erweiterte die Peano-Arithmetik durch transfinite Ordnungszahlen und machte die Das transfinite Induktionsprinzip ist Teil dieses erweiterten Kalküls. Dann zeigte er direkt, dass die transfinite Induktion bis zur ersten Epsilonzahl ε 0 im System exprimierbar, aber nicht nachweisbar ist. Gödels Unvollständigkeitssatz wird also auf ganz andere Weise bewiesen. Die Idee des Beweises lautet kurz gesagt wie folgt: Zunächst wird festgelegt, was es bedeutet, die transfinite Induktion auf eine bestimmte Ordnungszahl im System abzuleiten. Zweitens Ordnungszahlen unter ε 0sind Ableitungen zugeordnet. Diese werden als "Werte" bezeichnet. Es wird dann gezeigt, dass, wenn die transfinite Induktion zu einer Ordnungszahl ableitbar ist, diese Ordnungszahl nicht größer als der Wert der Ableitung sein kann. Daher ist eine transfinite Induktion zu & epsi; 0 nicht ableitbar.
Da das Induktionsprinzip in gewöhnlicher Arithmetik ausgedrückt, aber nicht bewiesen werden kann, wird eine Formel gefunden, die in Peano-Arithmetik nicht beweisbar ist. Eine einfache Konsequenz von Gentzens Version des Unvollständigkeitssatzes ist die Konsistenz der Peano-Arithmetik, da in einem inkonsistenten System alles beweisbar wäre. Im Gegensatz zu Gödels "künstlicher" unbeweisbarer Formel, die durch Codierung des arithmetisierten Beweisprädikats erhalten wurde, ist Gentzens transfinites Induktionsprinzip ein Prinzip der "gewöhnlichen" Mathematik.
Gentzens letzter Beweis bestimmte die „beweistheoretische Ordnungszahl“der Peano-Arithmetik, nämlich diejenige, die zum Nachweis der Konsistenz erforderlich ist, mit der Eigenschaft, dass nichts weniger ausreichen würde. Die Arbeit markierte den Beginn der ordinalen Beweistheorie. Es war ohne Zweifel die bemerkenswerteste grundlegende Errungenschaft in der Arithmetik nach Gödels Unvollständigkeitssätzen, ist aber noch weitgehend unbekannt - man kann viele Bücher über Gödels Sätze finden, in denen Gentzen nicht einmal erwähnt wird.
Gödel hatte anscheinend nicht daran gedacht, durch die Verwendung nicht-finitärer, aber immer noch konstruktiver Prinzipien einen Konsistenzbeweis für die Arithmetik zu liefern. In den späten dreißiger Jahren, zumindest ab 1938, entwickelte er als Antwort auf Gentzens Beweis seine eigene spezielle Interpretation der intuitionistischen Logik und Arithmetik, die als Dialectica-Interpretation bekannt wurde. Es verwendet berechenbare Funktionale, um die Beweise der intuitionistischen Arithmetik zu interpretieren. Gödel veröffentlichte die Interpretation erst 1958, obwohl er sie 1941 in Vorträgen vorgestellt hatte. Es ist nicht bekannt, ob er die Angelegenheit erörterte, als er Gentzen im Dezember 1939 traf.
Auf Wunsch von Bernays reproduzierte Ackermann 1940 Gentzens Beweis in Bezug auf Hilberts Epsilon-Kalkül. Ackermanns Arbeit war der Ausgangspunkt für Kreisels Interpretation der Arithmetik „ohne Gegenbeispiel“von 1951. Es war eine Überraschung, als die Veröffentlichung von Gödels gesammelten Papieren 1938 seinen „Zilsel-Vortrag“in Wien ans Licht brachte: Dort skizziert er diese Interpretation als Neuformulierung von Gentzens Beweis von 1935. (Die Angelegenheit wird in Tait (2005) ausführlich erörtert, der selbst in den 1960er Jahren an der Interpretation ohne Gegenbeispiel und ihrer Ausweitung auf die Analyse gearbeitet hatte.)
Die nächste offensichtliche Aufgabe in der Beweistheorie bestand nach dem Beweis der Konsistenz der Arithmetik darin, die Konsistenz der Analyse, dh der Theorie der reellen Zahlen, zu beweisen. Gentzen arbeitete in dieser Richtung, wurde dann aber im Herbst 1939 zum Militärdienst versetzt. (Er beobachtete und berichtete über Typ, Anzahl und Richtung der Flugzeuge, die über der Stadt Braunschweig flogen, bis er von einem Nerv getroffen wurde Zusammenbruch Anfang 1942.) Ab 1943 nahm er die Analyse weiter auf, aber die dem Thema innewohnenden Schwierigkeiten waren groß, ebenso wie die praktischen Schwierigkeiten des Lebens, die durch den Krieg verursacht wurden. Die Analyse sollte als ein System der Arithmetik zweiter Ordnung formuliert werden, was bedeutet, dass die Quantifizierung über zahlentheoretische Prädikate oder äquivalent über Mengen natürlicher Zahlen ausgedehnt wird. Die Zahlentheorie zweiter Ordnung wird in Gentzens letztem Aufsatz verwendet:veröffentlicht im Jahr 1943, in dem kurz gezeigt wird, dass das Prinzip der transfiniten Induktion bis zu ε0 ist in der Zahlentheorie zweiter Ordnung ableitbar.
Mehr als ein halbes Jahrhundert ist vergangen, ohne dass ein konstruktiver Beweis für die Konsistenz der vollständigen Arithmetik zweiter Ordnung in Sicht war. Zu den frühen Pionieren auf diesem Gebiet gehörten Kurt Schütte und Gaisi Takeuti. Ersteres schuf 1951 einen unendlichen sequentiellen Kalkül, um Konsistenzbeweise übersichtlich darzustellen, letzteres verwendete stattdessen einen traditionelleren Gentzen-Kalkül (siehe Takeuti 1987).
In der aktuellen Forschung zur Beweistheorie der Arithmetik zweiter Ordnung untersucht man sogenannte Subsysteme der Arithmetik zweiter Ordnung. Die stärksten Ergebnisse von heute sind in einem sehr kurzen Überblick die folgenden: Lassen Sie X über zahlentheoretischen Prädikaten liegen. Eine Formel wie X (x) besagt, dass x die durch X ausgedrückte Eigenschaft hat. Wir können jetzt Logik erster und zweiter Ordnung verwenden, um zusammengesetzte Formeln wie ∀ X (X x ∨ ¬ X x) zu bilden. Die Sammlung natürlicher Zahlen, für die eine solche Formel mit einem universellen Quantifizierer zweiter Ordnung gilt, wird als Π11-Menge bezeichnet (in diesem Fall die Gesamtheit der natürlichen Zahlen). Allgemeiner hat ein Verständnisaxiom die Form ∃ X ∀ x (X x ↔ B (x)). Wenn die Formel B keine Quantifizierer zweiter Ordnung hat, gibt das Axiom das sogenannte arithmetische Verständnis oder ACA an. Wenn B die Form ∀ Y ∃ ZC (x) ohne andere Quantifizierer zweiter Ordnung haben kann, wird der Sonderfall des Π12-Verständnisses erhalten. Toshiyasu Arai und Michael Rathjen haben Mitte der neunziger Jahre Konsistenzbeweise für ein Subsystem der Arithmetik zweiter Ordnung mit Π12-Verständnis vorgelegt. (Siehe Rathjen 1995 für diese Entwicklungen).
6. Spätere Entwicklungen beim natürlichen Abzug
Zu der Zeit, als Gentzen sein System der natürlichen Deduktion ausarbeitete, entwickelte Stanislaw Jaskowski auch ein logisches System für das Denken mit Annahmen. Formeln in Ableitungen sind in einer linearen Abfolge angeordnet, aber Jaskowskis Arbeit von 1934 blieb fragmentarisch und ohne wesentliche Ergebnisse wie eine Subformeleigenschaft. Die lineare Variante der natürlichen Deduktion wird in vielen pädagogischen Darstellungen der Elementarlogik (manchmal auch als „Fitch-Systeme“bezeichnet) verfolgt. Gentzen fand Jaskowskis Werk im Juni 1936, als beide in Münster waren, und betrachtete seine lineare Anordnung der Formeln als eine Verbesserung, eine "Befreiung von der Zwangsjacke der Baumform", in eine, die "die Linearität des Denkens" widerspiegelt (die erstere aus unveröffentlichte Notizen, letztere aus Gentzens These).
Das System der natürlichen Deduktion blieb etwa dreißig Jahre lang weitgehend ruhen, bis die These von Dag Prawitz von 1965, Natürliche Deduktion: Eine beweistheoretische Studie, veröffentlicht wurde. Die Reihenfolge, in der Prawitz den Normalisierungssatz vorstellte, unterschied sich von der in Gentzens frühem Manuskript. Prawitz gab zunächst einen Normalisierungssatz und eine Subformeleigenschaft für ein System der natürlichen Deduktion für die klassische Logik an. Dieses System enthält keine Disjunktion oder Existenz. In einer zweiten Phase betrachtete er die intuitionistische natürliche Ableitung für die vollständige Sprache der Prädikatenlogik und reduzierte ihre Normalisierung auf die Streichung von Umleitungskonvertibilitäten wie im Fragment der klassischen Logik. Als Gentzens Normalisierungsnachweis 2005 ans Licht kam, sagte Prawitz im Gespräch mit dem gegenwärtigen Autor, dass es klar sei, dass Gentzen das Ergebnis kenne.weil die Bemerkungen in der gedruckten These so suggestiv sind.
In den späten 1960er Jahren wurde eine starke Normalisierung zu einem Problem: Prawitz bewies 1971 anhand früherer Arbeiten von William Tait und Jean-Yves Girard, dass Nicht-Normalitäten in einer Ableitung in beliebiger Reihenfolge konvertiert werden können, mit einem abschließenden Normalisierungsprozess und einem einzigartigen normale Ableitung als Ergebnis. Gentzen scheint letzteres nicht bemerkt zu haben, scheint aber eher das Gegenteil gedacht zu haben, indem diese Eigenschaft zur Beseitigung von Schnitten in der sequentiellen Analysis versagt hat.
Etwa zur gleichen Zeit, als eine starke Normalisierung untersucht wurde, entstand die Curry-Howard-Korrespondenz. Curry hatte in seinen Arbeiten zur kombinatorischen Logik Ende der 1950er Jahre die Analogie zwischen der Beseitigung von Implikationen bei der natürlichen Deduktion und der funktionalen Anwendung beobachtet (Curry und Feys 1958). Die Idee war so alt wie die intuitionistische Logik: Durch die „BHK-Erklärung“der Konnektive und Quantifizierer (für Brouwer-Heyting-Kolmogorov) drücken die Formen der Sätze in der intuitionistischen Logik Vorschriften aus, wie diese Sätze zu beweisen sind: eine Konjunktion A & B wird bewiesen, indem A und B getrennt bewiesen werden, eine Disjunktion A ∨ B durch Beweisen von A und B und eine Implikation A ⊃ B, indem gezeigt wird, wie ein Beweis von A in einen Beweis von B umgewandelt werden kann, und so weiter. Diese Erklärungen kommen den Einführungsregeln des natürlichen Abzugs sehr nahe.aber es bleibt unbekannt, wie sie sich auf Gentzens Gedanken auswirkten.
Die Curry-Howard-Korrespondenz aus einem Artikel von William Howard aus dem Jahr 1969, der jedoch erst 1980 veröffentlicht wurde, basiert auf dem Prinzip „Formeln als Typen“oder in einem anderen Jargon auf dem Prinzip „Sätze als Mengen“. Ein Satz wird als Beweis angesehen. Die Wahrheit eines Satzes entspricht der Nichtleere der Menge. Beweise von A ⊃ B sind nun Funktionen von (Beweisen von) A bis (Beweisen von) B und A ⊃ B selbst die Menge solcher Funktionen. Wenn also f: A ⊃ B und a: A ist, ergibt die funktionale Anwendung f (a): B. Das Gegenteil, das der Einführung einer Implikation entspricht, wird durch das Prinzip der funktionalen Abstraktion des λ-Kalküls der Alonzo-Kirche erfasst.
Die Curry-Howard-Korrespondenz hat die intuitionistische natürliche Deduktion zu einem Teil des Lehrplans für Informatik gemacht: Sie bietet eine rechnerische Semantik für die intuitionistische Logik, in der Berechnungen und die Ausführung von Programmen im Allgemeinen durch Normalisierung erfolgen. Ein Beweis für eine Implikation A ⊃ B ist beispielsweise ein Programm, das Daten vom Typ A in eine Ausgabe vom Typ B konvertiert. Die Konstruktion eines Objekts (Beweis, Funktion, Programm) f vom Typ A ⊃ B endet mit einer Abstraktion. Wenn ein Objekt a vom Typ A als Argument in f eingespeist wird, ist der resultierende Ausdruck nicht normal, sondern hat eine Form, die einer Einführung entspricht, gefolgt von einer Eliminierung. Die Normalisierung entspricht nun der Ausführung des Programms f. Die Verwendung intuitionistischer Logik ist an keine intuitionistische Philosophie der Mathematik gebunden. Dies ist jedoch nur eine systematische Garantie für die Beendigung der Ausführung von Computerprogrammen.
Gentzens Doktorarbeit war die Geburtsstunde der strukturellen Beweistheorie im Gegensatz zur alten axiomatischen Beweistheorie von Hilbert. Einen bemerkenswerten Schritt in der Entwicklung von Systemen der sequentiellen Analysis machte Oiva Ketonen in seiner Doktorarbeit von 1944. Ketonen, ein Student der Mathematik und Philosophie in Helsinki, ging 1938 nach Göttingen, um die Beweistheorie zu studieren, wobei Gentzen am nächsten war für einen Studenten hatte dieser jemals. Die Verbindung scheint von Ketonens Philosophieprofessor Eino Kaila hergestellt worden zu sein, der Gentzen 1936 in Münster kennengelernt hatte. Ketonen erinnerte sich später daran, dass Gentzen „ein sympathischer junger Mann mit wenigen Worten“war, der ihm eine Einführung in die beweistheoretischen Systeme und Ergebnisse gab. Ketonen 'Die bekannteste Entdeckung ist eine sequentielle Berechnung für die klassische Aussagenlogik, deren logische Regeln alle invertierbar sind. Dies bedeutet, dass immer dann, wenn eine Sequenz eine Form hat, die mit der Schlussfolgerung einer logischen Regel übereinstimmt, die entsprechenden Prämissen eindeutig aus der gegebenen Sequenz definiert werden und die Regel sind auch ableitbar. Das Gegenteil ist sofort der Fall (wenden Sie einfach die Regel an). Die Regeln L & und L⊃ werden beispielsweise in geändert
A, B, Γ → Δ
L &
A & B, Γ → Δ
Γ → Δ, AB, Γ → Δ
L⊃
A ⊃ B, Γ → Δ
Es gibt nur eine linke Regel für die Konjunktion (und doppelt nur eine rechte Regel für die Disjunktion). Die linke Implikationsregel hat sogenannte „gemeinsame Kontexte“: Die Annahmen und Fälle in der Schlussfolgerung, mit Ausnahme der Formel mit dem Konnektiv, werden in beiden Prämissen identisch wiederholt. Ketonens Idee war es, ein System der Beweissuche zu definieren: Man geht von einer gegebenen Folge aus, die abgeleitet werden soll, wählt eine Formel darin und schreibt die Prämissen einer Regel, die die gegebene Folge abschließen kann. Durch die Invertierbarkeit wird die Frage der Ableitbarkeit durch eine oder zwei äquivalente Fragen der Ableitbarkeit bei einfacheren Sequenzen ersetzt. Die neuen Regeln werden benötigt, um eindeutig definierte Prämissen bei einer solchen "Root-First" -Zerlegung sicherzustellen.
Ketonens Beweis der Invertierbarkeit der logischen Regeln seines sequentiellen Kalküls verwendete die strukturelle Schnittregel. Später gaben Kurt Schütte (1950) und Haskell Curry (1963) direkte Beweise für die Invertierbarkeit, letztere mit dem expliziten Ergebnis, dass die Inversionen höhenerhaltend sind: Wenn eine gegebene Sequenz in höchstens n Schritten ableitbar ist, können die Prämissen in einer Regel, die dies kann schlussfolgern, dass sequent auch eine Ableitung in höchstens n Schritten haben.
Wie viel von Ketonens Arbeiten aus Vorschlägen von Gentzen stammt, ist unbekannt, da keine Korrespondenz gefunden wurde. Ketonen schreibt im Vorwort seiner Dissertation: „Dr. G. Gentzen aus Göttingen hat mich auf den Problembereich dieser Arbeit hingewiesen. “Die These war Ketonens einziges Originalwerk in der Logik, das durch eine lange Rezension, die Bernays 1945 für das Journal of Symbolic Logic darüber schrieb, vor dem Vergessen bewahrt wurde.
Eine Person, die Ketonens Kalkül Ende der 1940er Jahre kannte, war Evert Beth. Als Beth 1955, 1955, seinen bekannten Tableau-Kalkül vorstellte, scheint er den Ursprung des Tableau-Kalküls als Neuformulierung des Ketonen-Kalküls vergessen zu haben, bezieht sich aber stattdessen auf Kleenes einflussreiche Einführung in die Metamathematik von 1952. Kleene hatte genommen Ketonens Kalkül aus der Bernays-Rezension und behandelte auch den intuitionistischen sequentiellen Kalkül, bei dem die Invertierbarkeit eingeschränkter ist als beim klassischen Kalkül. Mit Kleenes Buch wurden Gentzens Sequenzkalküle allgemein bekannt und zugänglich.
Kleenes Arbeit der frühen 1950er Jahre war auch Vorreiter einer bemerkenswerten Entwicklung in der sequentiellen Analysis, nämlich der heute mit G3c und G3i bezeichneten „kontraktionsfreien“klassischen und intuitionistischen Kalküle. Diese Kalküle haben die Eigenschaft, dass keine der ursprünglichen „Strukturregeln“von Gentzen benötigt werden. Die Regel der "Schwächung" erlaubt das Hinzufügen überflüssiger Fälle und Annahmen, und die Regel der "Kontraktion" das Löschen einer Kopie einer Formel, wenn zwei in einer Liste vorhanden waren, wie in
Schwächung
Kontraktion
Γ → Δ
Wk
A, Γ → Δ
A, A, Γ → Δ
Ctr
A, Γ → Δ
Analoge Regeln erlauben eine Schwächung und Kontraktion der rechten, aufeinanderfolgenden Teile von Sequenzen. Die Schwächung wird zu einer eliminierbaren Regel, indem anfängliche Sequenzen die Form A, Γ → Δ, A anstelle von Gentzens A → A haben. Eine Kontraktion wird ebenfalls durch eine geeignete Formulierung der Regeln beseitigt. Der Import besteht darin, dass bei der Root-First-Proof-Suche keine Regeln angewendet werden müssen, die zu einer Verdoppelung einer Formel in einer Prämisse führen würden. Ohne dieses Ergebnis würde eine Nichtbeendigung der Beweissuche nicht folgen.
Der klassische Kalkül hat die oben erwähnte Eigenschaft der höhenerhaltenden Invertierbarkeit seiner logischen Regeln. Albert Dragalin verfeinerte Ende der 1970er Jahre den Kalkül zu einem Kalkül, in dem die Strukturregeln darüber hinaus „höhenerhaltend zulässig“sind, was bedeutet, dass die Schlussfolgerung immer dann, wenn die Prämisse einer solchen Regel ableitbar ist, ohne die Regel und höchstens mit derselben ableitbar ist Größe (maximale Anzahl von Regelinstanzen in einem Ableitungszweig) der Ableitung. Diese Eigenschaft hat tiefgreifende Auswirkungen auf die Eliminierung von Schnitten: Beim Permutieren von Schnitten musste Gentzen die ursprünglichen Kontexte (die Γ und Δ) durch Schwächungen und Kontraktionen wiederherstellen. Mit der höhenerhaltenden Zulässigkeit dieser Regeln nimmt die Größe einer Ableitung nicht zu, wenn die Regeln angewendet werden. Dragalin gab auch einen intuitionistischen multisukzedenten Kalkül mit der gleichen Art der Zulässigkeit der Strukturregeln. Troelstra schließlich gab im Lehrbuch Basic Proof Theory (2000, erste Ausgabe 1996) einen einzigen nachfolgenden intuitionistischen Kalkül mit höhenerhaltender Zulässigkeit von Schwächung und Kontraktion. Die kontraktionsfreien sequentiellen Kalküle sind leistungsstarke Werkzeuge zur Analyse formaler Ableitungen. Viele schwierige Forschungsergebnisse in der Logik werden nur zu Übungen durch die Kontrolle über die Struktur der Beweise, die die G3-Kalküle zulassen. Die kontraktionsfreien sequentiellen Kalküle sind leistungsstarke Werkzeuge zur Analyse formaler Ableitungen. Viele schwierige Forschungsergebnisse in der Logik werden nur zu Übungen durch die Kontrolle über die Struktur der Beweise, die die G3-Kalküle zulassen. Die kontraktionsfreien sequentiellen Kalküle sind leistungsstarke Werkzeuge zur Analyse formaler Ableitungen. Viele schwierige Forschungsergebnisse in der Logik werden nur zu Übungen durch die Kontrolle über die Struktur der Beweise, die die G3-Kalküle zulassen.
Die früheste Anwendung der sequentiellen Analysis in der Mathematik war in der Beweistheorie der Arithmetik, in Gentzens These und in entscheidender Weise im Beweis der Konsistenz der Arithmetik von 1938. Troelstra erwähnt Ketonens Arbeit als
eine frühe Analyse von schnittfreien Beweisen in Gentzen-Steinen mit Axiomen; aber er betrachtet die Form von schnittfreien Ableitungen im reinen Kalkül, wo Axiome im Vorgänger der abgeleiteten Sequenzen vorhanden sind. (Troelstra und Schwichtenberg 2000: 142)
Die Axiome, die Ketonen betrachtet, sind solche der projektiven und affinen Geometrie, die erstere stammt aus Skolems 1920er Papier, das im ersten Abschnitt oben diskutiert wurde. Ketonen wollte Skolems formale Beweisregeln innerhalb der sequentiellen Berechnung formulieren. Ketonens Arbeit war jedoch größtenteils nur durch die Überprüfung durch Bernays bekannt, und nur der logische Teil der sequentiellen Berechnung wurde dort ausführlich erläutert.
Eine zweite Möglichkeit, den Sequenzkalkül anzuwenden, besteht darin, Sequenzen, die mit Ableitungszweigen beginnen, zusätzlich zu den Anfangssequenzen auch die Form → A haben zu lassen, in der A ein Axiom oder eine Instanz eines universellen Axioms ist. Mit Gentzens „erweitertem Hauptsatz“können nun Ableitungsschnitte permutiert werden, bis eine ihrer Prämissen ein Axiom ist, aber diese Kürzungen der Axiome bleiben bestehen. Eine andere, neuere Methode besteht darin, Axiome in zusätzliche Regeln umzuwandeln, die zu den logischen Regeln der sequentiellen Berechnung hinzugefügt werden, wobei die vollständige Eliminierung beibehalten wird (wie in Negri und von Plato 2001, Kapitel 6, und in Troelstra und Schwichtenbergs 2000, Kapitel 4.7 erläutert)..
8. Die Ziele der Beweistheorie
Inwieweit hat die Beweistheorie ihre ursprünglichen Ziele erreicht? Für Hilbert waren die Ziele eine vollständige Klärung der grundlegenden Probleme durch endliche Konsistenznachweise usw., bei denen die Beweistheorie fehlschlug. Hilbert war in seinem Programm nicht daran interessiert, mathematische Beweise an sich zu studieren, sondern nur die zentralen Grundprobleme zu klären (und sie dann zu vergessen). Eine kürzlich gefundene Notiz von Hilbert gibt ein anderes Bild: Die Notiz besagt, dass Hilbert als 24. und letztes Problem in seine berühmte Pariser Liste offener mathematischer Probleme von 1900 die Entwicklung einer „Theorie der Beweismethoden in der Mathematik“aufnehmen wollte. Dies war, bevor sein metamathematisches Programm zur Entwicklung einer Beweistheorie aufkam.
Für Gentzen bestand das Ziel neben dem von Hilbert darin, die Struktur mathematischer Beweise zu verstehen. Dieses Programm war in Bezug auf reine Logik und Arithmetik ein voller Erfolg. Insbesondere die Methoden der sequentiellen Berechnung ermöglichen die Analyse von Beweisen mit tiefgreifenden Ergebnissen. Das große Ziel der Beweistheorie, ein Beweis für die Konsistenz der Analyse wie in Hilberts zweitem Pariser Problem, wurde nicht verwirklicht, wird aber auch nicht ausgeschlossen.
Ein gewisses Verständnis des Begriffs des Beweises ist für jeden Mathematiker erforderlich, wenn auch nicht für etwas anderes, dann zumindest für die Übertragbarkeit mathematischer Ergebnisse: Die Veröffentlichung beruht auf dem Verständnis, dass Beweise so explizit gemacht werden können, dass sie routinemäßig auf ihre Richtigkeit überprüft werden können. Die Beweistheorie ist jedoch bisher kein praktisches Werkzeug für den arbeitenden Mathematiker geworden; Die Anwendungen in der Mathematik waren eher Einzelfälle. Neuere Arbeiten zur Formalisierung mathematischer Beweise mit computergestützten Systemen, sogenannte Proof-Editoren, könnten dieses Bild allmählich ändern.
Die Beweistheorie hat neue Ziele außerhalb der traditionellen Mathematik geschaffen, insbesondere im Zusammenhang mit der Informatik. Themen wie die Überprüfung der Richtigkeit von Computerprogrammen sind ein Ergebnis der Beweistheorie. Natürliche Ableitungen haben zur Curry-Howard-Korrespondenz und zu Verbindungen mit der funktionalen Programmierung geführt, und in Systemen der automatischen Beweissuche wird häufig eine sequentielle Berechnung verwendet, wie in der logischen Programmierung.
Literaturverzeichnis
Texte zur Beweistheorie
Buss, Sam (Hrsg.), 1998, Handbook of Proof Theory, Amsterdam: Elsevier.
Negri, S. und J. von Plato, 2001, Structural Proof Theory, Cambridge: Cambridge University Press.
von Plato, J., 2013, Elemente des logischen Denkens, Cambridge: Cambridge University Press.
Troelstra, A. und H. Schwichtenberg, 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2. Auflage.
Originalwerke und ihre Nachdrucke
Ackermann, W. 1940, „Zur Widerspruchsfreiheit der Zahlentheorie“, Mathematische Annalen, 117: 162–194.
Beth, E., 1955, Semantische Konsequenz und formale Ableitbarkeit (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe stinkt, deel 18, Nr. 13), Amsterdam: Nordholland.
Church, A., 1936, „Eine Anmerkung zum Entscheidungsproblem“, Journal of Symbolic Logic, 1: 40–41.
Curry, H. und Feys, R., 1958. Combinatory Logic. (Studium der Logik und der Grundlagen der Mathematik, Band I), 1. Auflage, Amsterdam: Nordholland.
Curry, H., 1963, Grundlagen der mathematischen Logik, New York: McGraw-Hill; Nachdruck New York: Dover, 1977.
Dragalin, A., 1988, Mathematischer Intuitionismus: Einführung in die Beweistheorie, Providence, RI: American Mathematical Society.
Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen, Ph. D. Diplomarbeit, Universität Göttingen. Veröffentlicht in Gentzen 1969: 68–131.
Gentzen, G., 1938, „Neue Fassung des Breitspruchsfreiheitsbeweises für die reine Zahlentheorie“, Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19–44. Übersetzt in Gentzen 1969: 252–286.
Gentzen, G., 1943, „Beweisbarkeit und Unbeweisbarkeit von Anfangszeiten der transfiniten Induktion in der reinen Zahlentheorie“, Mathematische Annalen, 119: 252–286. Übersetzt in Gentzen 1969: 287–308.
Gentzen, G., 1969, The Collected Papers von Gerhard Gentzen, hrsg. M. Szabo, Amsterdam: Nordholland.
Gentzen, G., 2008, „Die Normalisierung von Ableitungen“, The Bulletin of Symbolic Logic, 14 (1): 245–257.
Gödel, K., 1930, „Die Vollständigkeit der Axiome des logischen Funktionenkalküls“, Monatshefte für Mathematik und Physik, 37: 349–360.
Gödel, K., 1958, „Dialektica, 12: 280–287.
Gödel. K., 1986–2003, Collected Papers (Bände IV), S. Feferman et al. (Hrsg.), Oxford: Oxford University Press.
van Heijenoort, J., 1967, Von Frege nach Gödel, Cambridge, MA: Harvard University Press.
Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: BG Teubner.
Hilbert, D., 1926, „Über das Unendliche“, Mathematische Annalen, 95: 161–190. [Vortrag gehalten in Münster, 4. Juni 1925.]
Hilbert, D. und Ackermann, W., 1928, Grundzüge der theoretischen Logik, Berlin: Springer.
Hilbert, D., 1931, „Die Grundlegung der elementaren Zahlenlehre“, Mathematische Annalen, 104: 484–494.
Howard, W., 1980 [1969], "Der Begriff der Konstruktion als Formeln als Typen", in J. Seldin und J. Hindley (Hrsg.), To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, London, New York: Academic Press, S. 480–490.
Jaskowski, S., 1934, „Über die Regeln der Vermutung in der formalen Logik“, S. McCall (Hrsg.), Polish Logic 1920–1939, Oxford: Clarendon Press, 1967, S. 232–258.
Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae Scientiarum Fennicae (Ser. AI 23), Helsinki.
Kleene, S., 1952, Einführung in die Metamathematik, Amsterdam: Nordholland.
Kreisel, G., 1951, „Zur Interpretation nicht-finitistischer Beweise: Teil I“, The Journal of Symbolic Logic, 16 (4): 241–267.
Menzler-Trott, E., 2001, Gentzens Problem, Berlin: Birkhäuser Verlag.
Menzler-Trott, E., 2007, Logics verlorenes Genie: Leben und Werk von Gerhard Gentzen, Providence, RI: American Mathematical Society.
Prawitz, D., 1965, Natural Deduction: Eine beweistheoretische Studie, Stockholm: Almqvist & Wiksell; Nachdruck New York: Dover (mit neuem Vorwort), 2006.
–––, 1971, „Ideen und Ergebnisse in der Beweistheorie“, in J. Fenstad (Hrsg.), Proceedings of the Second Scandinavian Logic Symposium, Amsterdam: Nordholland, S. 235–308.
Rathjen, M., 1995, „Jüngste Fortschritte in der Ordnungsanalyse; Π 12 -CA und verwandte Systeme “, The Bulletin of Symbolic Logic, 1 (4): 468–485.
Schütte, K., 1950, „Schlussweisen-Kalküle der Prädikatenlogik“, Mathematische Annalen, 122: 47–65.
–––, 1951, „Beweistheoretische Sammlung der unendlichen Induktion in der Zahlentheorie“, Mathematische Annalen, 122: 369–389.
Skolem, T., 1920, "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze, nebst einem Theorem über dichte Mengen", übersetzt und nachgedruckt in Selected Works in Logic, JE Fenstad (Hrsg.), Oslo, Universitetsforlaget, 1970, S. 103–136:
Whitehead, AN und B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.
Sekundärliteratur
Bernays, P., 1945, „Review: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul“, The Journal of Symbolic Logic, 10 (4): 127–130.
–––, 1965, „Betrachtungen zum festgelegten-kalkul“, in Beiträge zur Logik und Methodik zu Ehren von JM Bochenski, Amsterdam: Nordholland, S. 1–44.
–––, 1979, „Über den ursprünglichen Gentzen-Konsistenznachweis für die Zahlentheorie“, in J. Myhill et al. (Hrsg.), Intuitionismus und Beweistheorie, Amsterdam: Nordholland, S. 409–417.
Feferman, S., 2000, "Highlights in Proof Theory", in V. Hendricks et al. (Hrsg.) 2000, 11–31.
Hempel, C., 2000, "Eine intellektuelle Autobiographie." In Science, Explanation and Rationality, hrsg. J. Fetzer, S. 3-35.
Hendricks, V., et al. (Hrsg.), 2000, Beweislehre: Geschichte und philosophische Bedeutung, Dordrecht: Kluwer.
Mancosu, P., 1999, „Zwischen Berlin und Wien: Die unmittelbare Rezeption von Gödels Unvollständigkeitssätzen“, History and Philosophy of Logic, 20: 33–45.
von Plato, J., 2007, „Im Schatten des Löwenheim-Skolem-Theorems: frühe kombinatorische Analysen mathematischer Beweise“, The Bulletin of Symbolic Logic, 13 (2): 189–225.
–––, 2007, „Von Hilberts Programm zu Gentzens Programm“, im Anhang, Menzler-Trott 2007.
–––, 2009, „Gentzens Logik“, im Handbuch der Geschichte und Philosophie der Logik (Band 5), Amsterdam: Elsevier.
–––, 2012, „Gentzens Beweissysteme: Nebenprodukte in einem genialen Programm“, The Bulletin of Symbolic Logic, 18 (3): 313–367.
Smorynski, C., 2007, „Hilberts Programm“, im Anhang, Menzler-Trott 2007.
Tait, W., 2005, „Gödels Neuformulierung von Gentzens erstem Konsistenzbeweis für die Arithmetik: die Interpretation ohne Gegenbeispiel“, The Bulletin of Symbolic Logic, 11 (2): 225–238.
Troelstra, A. und Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2. Auflage.
Akademische Werkzeuge
Sep Mann Symbol
Wie man diesen Eintrag zitiert.
Sep Mann Symbol
Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
Inpho-Symbol
Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
Phil Papers Ikone
Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.
Andere Internetquellen
[Bitte kontaktieren Sie den Autor mit Vorschlägen.]
