De Ontwikkeling Van Bewijstheorie

2023 Auteur: Noah Black | [email protected]. Laatst gewijzigd: 2023-11-26 16:11

Toegang navigatie

• Inhoud van het item
• Bibliografie
• Academische hulpmiddelen
• Vrienden PDF-voorbeeld
• Info over auteur en citaat
• Terug naar boven

De ontwikkeling van bewijstheorie

Voor het eerst gepubliceerd op woensdag 16 april 2008; inhoudelijke herziening ma 13 okt 2014

De ontwikkeling van de bewijstheorie kan natuurlijk worden onderverdeeld in: de prehistorie van het begrip bewijs in de oude logica en wiskunde; de ontdekking van Frege dat wiskundige bewijzen, en niet alleen de stellingen van de wiskunde, kunnen (en moeten) worden weergegeven in een logisch systeem; Hilbert's oude axiomatische bewijstheorie; mislukking van de doelstellingen van Hilbert door Gödel's onvolledigheidsstellingen; Gentzen's creatie van de twee hoofdtypen logische systemen van hedendaagse bewijstheorie, natuurlijke deductie en opeenvolgende calculus (zie de vermelding over geautomatiseerd redeneren); toepassingen en uitbreidingen van natuurlijke aftrek en opeenvolgende calculus, tot aan de computationele interpretatie van natuurlijke aftrek en zijn verbindingen met informatica.

• 1. Prehistorie van het begrip bewijs
• 2. Hilbert's oude axiomatische bewijstheorie
• 3. De onbewijsbaarheid van consistentie
• 4. Natuurlijke aftrek en opeenvolgende calculus
• 5. De consistentie van rekenen en analyse
• 6. Latere ontwikkelingen in natuurlijke aftrek
• 7. Sequent Calculus: latere ontwikkelingen / toepassingen
• 8. De doelstellingen van de bewijstheorie

• Bibliografie

  • Teksten over de proefleer
  • Originele werken en hun reproducties
  • Secundaire literatuur
• Academische hulpmiddelen
• Andere internetbronnen
• Gerelateerde vermeldingen

1. Prehistorie van het begrip bewijs

Bewijstheorie kan worden beschreven als de studie van de algemene structuur van wiskundige bewijzen en van argumenten met demonstratieve kracht zoals die in de logica worden aangetroffen. Het idee van dergelijke demonstratieve argumenten, di degene waarvan de conclusie noodzakelijkerwijs voortvloeit uit de gemaakte veronderstellingen, staat centraal in Aristoteles 'Analytica Posteriora: een deductieve wetenschap is georganiseerd rond een aantal basisconcepten waarvan wordt aangenomen dat ze worden begrepen zonder verdere uitleg, en een aantal van fundamentele waarheden of axioma's die onmiddellijk als waar worden gezien. Gedefinieerde concepten en stellingen worden gereduceerd tot deze twee, de laatste door middel van bewijs. Aristoteles 'bewijsverslag als demonstratief argument sluit heel goed aan bij de structuur van de oude geometrie zoals die in Euclides werd gebruikt. De specifieke vorm van de logica van Aristoteles, de theorie van het syllogisme, heeft in plaats daarvan, zo lijkt het,bijna niets te maken met bewijzen in de Euclidische meetkunde. Deze bewijzen bleven meer dan tweeduizend jaar intuïtief.

Vóór het werk van Frege in 1879 scheen niemand te hebben beweerd dat er een volledige reeks bewijsprincipes zou kunnen zijn, in de zin die Frege uitdrukte toen hij dat in zijn symbolische taal schreef,

alles wat nodig is voor een juiste gevolgtrekking wordt volledig uitgedrukt, maar wat niet nodig is, wordt over het algemeen niet aangegeven; niets wordt aan giswerk overgelaten. (Begriffsschrift, p.3)

(Men zou kunnen stellen dat Boole een uitzondering is wat de klassieke propositionele logica betreft.) Frege's stap voorwaarts was bepalend voor de ontwikkeling van logica en fundamenteel onderzoek. Het contrast met de Ouden is groot: Aristoteles gaf een patroon om argumenten te combineren, maar het idee van een eindige gesloten reeks regels was, filosofisch, de dromen van iemand vóór Frege, met de mogelijke uitzondering van Leibniz, voorbij.

Zoals we nu weten, zijn de bewijsprincipes van Frege compleet voor de klassieke predikatenlogica.

Rond 1890 gaf Giuseppe Peano een formalisering van logische gevolgtrekking, met als doel het formeel bewijzen in rekenkunde weer te geven. Zijn baanbrekende Arithmetices principia, nova methodo exposita, oorspronkelijk in het Latijn geschreven, is opgenomen in Engelse vertaling in de collectie From Frege to Gödel (1967) die Jean van Heijenoort redigeerde. Helaas kon de redacteur niet erkennen wat Peano deed met formele gevolgtrekking, en de opvatting verspreidde zich dat Peano alleen de taal van logica en rekenen formaliseerde, niet de bewijsprincipes. Als de bewijzen van Peano zelfs met een beetje zorg worden gelezen, blijkt dat het puur formele afleidingen zijn die twee principes gebruiken:

1. Axioma's impliceren hun instanties. Dergelijke implicaties kunnen worden geschreven als regels in bewijzen.
2. Een implicatie en het antecedent ervan impliceren samen de consequentie.

Peano is heel voorzichtig om op elke regel van zijn afleidingen op te sommen wat de formele reden is om de regel te schrijven.

Russell nam de logica van Frege over, maar gebruikte de notatie en formele bewijsregels van Peano in een paper uit 1906 met de titel 'The theory of implication'. Het formele machinepark is precies hetzelfde als dat van Peano. In later werk veranderde Russell het axiomatische systeem en dat van Principia Mathematica (Whitehead en Russell 1910–13) werd standaard. Het filosofische idee van Russell, en hier volgde hij Frege, was dat de axioma's logische basiswaarheden uitdrukken en dat andere logische waarheden hieruit worden afgeleid door middel van modus ponens en universele generalisatie, de twee principes die Frege had geïdentificeerd. Wiskunde zou worden gereduceerd tot logica, zodat de bewijzen ervan in hetzelfde axiomatische patroon zouden worden gepresenteerd.

Frege's en Peano-Russell's benadering van logica werd de algemeen aanvaarde, vooral door de invloed van Hilbert en zijn medewerkers in de jaren twintig. In de 19e eeuw was Frege een marginale figuur en de algebraïsche benadering van de logica, zoals in Boole en vooral Ernst Schröder, was de dominante. Het is duidelijk dat er een goed begrip was van de principes van de predikaatlogica in deze traditie, want hoe had er anders een Löwenheim-Skolem-stelling kunnen bestaan? Skolem kwam via Principia Mathematica pas achter de logica van Frege nadat hij de stelling had uitgewerkt in zijn paper uit 1920. Het eerste deel van dat paper, dat veel gelezen werd vanwege de Engelse vertaling in Van Heijenoort's From Frege to Gödel, markeert het einde van de algebraïsche traditie van logica die in stilte overging in roostertheorie. Andere secties van het artikel bevatten een opmerkelijk begin van de analyse van bewijzen in roostertheorie en in projectieve meetkunde: Skolem beschouwde de axioma's van een wiskundige theorie vanuit een puur combinatorisch en formeel oogpunt, als middel om afleidingen te maken van een formule van gegeven formules gebruikt als aannames. Begin jaren negentig werd ontdekt dat het deel over de roostertheorie de oplossing bevat van een beslissingsprobleem, het woordprobleem voor vrij gegenereerde roosters, waarvan de bekende oplossing stamt uit 1988! De terminologie en notatie van Skolem in de roostertheorie zijn die van Schröder en dat is een deel van de reden waarom zijn werk een gemiste kans was voor bewijstheorie. Skolem beschouwde de axioma's van een wiskundige theorie vanuit een puur combinatorisch en formeel oogpunt, als middel voor het produceren van afleidingen van een formule uit gegeven formules die als veronderstellingen werden gebruikt. Begin jaren negentig werd ontdekt dat het deel over de roostertheorie de oplossing bevat van een beslissingsprobleem, het woordprobleem voor vrij gegenereerde roosters, waarvan de bekende oplossing stamt uit 1988! De terminologie en notatie van Skolem in de roostertheorie zijn die van Schröder en dat is een deel van de reden waarom zijn werk een gemiste kans was voor bewijstheorie. Skolem beschouwde de axioma's van een wiskundige theorie vanuit een puur combinatorisch en formeel oogpunt, als middel voor het produceren van afleidingen van een formule uit gegeven formules die als veronderstellingen werden gebruikt. Begin jaren negentig werd ontdekt dat het deel over de roostertheorie de oplossing bevat van een beslissingsprobleem, het woordprobleem voor vrij gegenereerde roosters, waarvan de bekende oplossing stamt uit 1988! De terminologie en notatie van Skolem in de roostertheorie zijn die van Schröder en dat is een deel van de reden waarom zijn werk een gemiste kans was voor bewijstheorie.noemde het woordprobleem voor vrij gegenereerde roosters, waarvan de bekende oplossing stamt uit 1988! De terminologie en notatie van Skolem in de roostertheorie zijn die van Schröder en dat is een deel van de reden waarom zijn werk een gemiste kans was voor bewijstheorie.noemde het woordprobleem voor vrij gegenereerde roosters, waarvan de bekende oplossing stamt uit 1988! De terminologie en notatie van Skolem in de roostertheorie zijn die van Schröder en dat is een deel van de reden waarom zijn werk een gemiste kans was voor bewijstheorie.

2. Hilbert's oude axiomatische bewijstheorie

Hilbert's boek Grundlagen der Geometrie uit 1899 vormde het toneel voor de centrale fundamentele problemen van de wiskunde van de eerste decennia van de 20e eeuw. We kunnen deze problemen als volgt opsommen:

1. De formalisering van een wiskundige theorie. Dit omvat een keuze van de basisobjecten en relaties en een keuze van de axioma's.
2. Een bewijs van de consistentie van de axioma's.
3. De kwestie van de onderlinge onafhankelijkheid en volledigheid van de axioma's.
4. Het beslissingsprobleem: is er een methode om elke vraag te beantwoorden die binnen de theorie zou kunnen worden gesteld?

Wat Hilbert's geometrie betreft, de poging tot formalisering voldeed niet aan het ideaal waaraan het was geboren. Hilbert vond een veel belangrijker gebied waarop zijn 'metamathematica' zou worden toegepast, namelijk rekenen en analyseren. De basis was een studie van de vier fundamentele problemen in axiomatische formuleringen van pure logica. De propositielogica werd aldus geformaliseerd, consistent en volledig bevonden en beslissend. De eerste resultaten over predikaatlogica zijn van 1915, toen Leopold Löwenheim zijn versie gaf van wat later de Löwenheim-Skolem-stelling voor predikaatlogica zou worden (zie de vermelding over klassieke logica). Hij loste ook speciale gevallen van het beslissingsprobleem op. Deze ontwikkeling was onafhankelijk van de Frege-Russell-traditie en was in plaats daarvan gebaseerd op de algebraïsche benadering van de logica van Ernst Schröder. Rond 1920,de axiomatische benadering in "Hilbert-stijl", zoals deze vaak wordt genoemd, was bij iedereen bekend en domineerde de logische scène; de algebraïsche benadering ging bijna zonder aankondiging op in de roostertheorie. Tegen 1928 werd in Hilbert en Ackermanns Grundzüge der theoretischen Logik een axiomatisch formeel systeem voor predikaatlogica gepresenteerd, samen met het probleem van de volledigheid ervan. Deze laatste werd in 1929 door Gödel opgelost, een jaar later gepubliceerd (Gödel 1930). Het vierde fundamentele probleem, het beslissingsprobleem voor predicaatlogica, bleek in 1936 door Church in een kort document een negatieve oplossing te hebben als een uitvloeisel van Gödel's onvolledigheidsstelling.s Grundzüge der theoretischen Logik, een axiomatisch formeel systeem voor predikaatlogica werd gepresenteerd, samen met het probleem van de volledigheid ervan. Deze laatste werd in 1929 door Gödel opgelost, een jaar later gepubliceerd (Gödel 1930). Het vierde fundamentele probleem, het beslissingsprobleem voor predicaatlogica, bleek in 1936 door Church in een kort document een negatieve oplossing te hebben als een uitvloeisel van Gödel's onvolledigheidsstelling.s Grundzüge der theoretischen Logik, een axiomatisch formeel systeem voor predikaatlogica werd gepresenteerd, samen met het probleem van de volledigheid ervan. Deze laatste werd in 1929 door Gödel opgelost, een jaar later gepubliceerd (Gödel 1930). Het vierde fundamentele probleem, het beslissingsprobleem voor predicaatlogica, bleek in 1936 door Church in een kort document een negatieve oplossing te hebben als een uitvloeisel van Gödel's onvolledigheidsstelling.

Hilbert en zijn school, met vooral Bernays, Ackermann en von Neumann, en de jonge Herbrand in Frankrijk, volgden de metamathematische studie van rekenen in de tweede helft van de jaren twintig van de twintigste eeuw. Hilbert ontwikkelde een methode voor het bestuderen van consistentieproblemen, de epsilon-substitutiemethode genaamd, om met de kwantoren om te gaan. Hij was van mening dat indirecte gevolgtrekkingen met kwantoren in gevallen met een oneindig aantal objecten het cruciale punt van consistentieproeven waren en een rechtvaardiging nodig hadden. Stel dat als de aanname dat alle natuurlijke getallen de eigenschap P hebben tot een onmogelijkheid leidt, het bestaan van een getal met de tegengestelde eigenschap niet-P kan worden afgeleid. Het centrale probleem was dus het rechtvaardigen van het gebruik van klassieke logica in wiskundige bewijzen, in de eerste plaats rekenkundige. Ackermann was eind jaren twintig zeer dicht bij een oplossing en in de Hilbertschool heerste optimisme. Toen gebeurde er natuurlijk het onverwachte toen Gödel de onmogelijkheid van een volledige formalisering van elementaire rekenkunde bewees, en, zoals al snel werd geïnterpreteerd, de onmogelijkheid om de consistentie van rekenkunde met finitaire middelen te bewijzen, de enige die door absoluut betrouwbaar werden geacht door Hilbert.

3. De onbewijsbaarheid van consistentie

Nadat Gödel de onvolledigheid van rekenen in september 1930 openbaar had gemaakt, ontdekte von Neumann dat de consistentie van rekenen tot de Gödeliaanse niet-beproefde stellingen zou behoren. Helaas had Gödel dezelfde ontdekking gedaan, dus publiceerde von Neumann zijn bewijs nooit. Hij vermoedde echter in overeenstemming met Gödel de onbewijsbaarheid van de consistentie van rekenen en dus van wiskunde als geheel, in absolute zin. Von Neumann was de sleutelfiguur bij de ontvangst van de resultaten van Gödel: hij onderbrak zijn lezingen over Hilbert's bewijstheorie in Berlijn in de herfst van 1930 om de nieuwe ontdekkingen uit te leggen. Deze gebeurtenissen veroorzaakten een enorme opwinding onder de wiskundigen, zoals blijkt uit de getuigenis van Carl Hempel:

Ik volgde daar een cursus bij von Neumann, die ging over Hilbert's poging om de consistentie van de klassieke wiskunde op finitaire wijze te bewijzen. Ik herinner me dat halverwege de cursus von Neumann op een dag binnenkwam en aankondigde dat hij zojuist een paper had ontvangen van … Kurt Gödel die liet zien dat de doelstellingen die Hilbert voor ogen had en waarop ik de cursus van Hilbert in Göttingen had gehoord, niet konden worden bereikt. Von Neumann stopte daarom met het volgen van dit onderwerp en wijdde de rest van de cursus aan de presentatie van de resultaten van Gödel. De vondst veroorzaakte een enorme opwinding. (Hempel 2000, p.13)

In 1932-1933 vonden Gödel en Gentzen onafhankelijk van elkaar een vertaling van klassieke Peano-rekenkunde naar intuïtionistische Heyting-rekenkunde. Het toont met name aan dat als een tegenstrijdigheid in het eerste geval bewezen kan worden, het in het tweede geval bewezen kan worden. Dan zou de consistentie van intuïtionistische rekenkunde ook de consistentie van klassieke rekenkunde garanderen. Dit resultaat was een verrassing: zoals gezegd had Hilbert gedacht dat de 'transfinite' indirecte existentieproeven het deel van de rekenkunde zouden zijn dat tegenstrijdig moet worden gemaakt. Door het resultaat van Gödel en Gentzen bevatten al intuïtionistische rekenkundige principes die verder gingen dan de finitaire redenering. Een brief die Gentzen op 25 februari 1933 aan Heyting schreef, vat de situatie als volgt samen:

Een consistentiebewijs met eindige middelen is tot dusver niet gelukt, zodat dit oorspronkelijke doel van Hilbert niet is bereikt. Als men daarentegen de intuïtionistische positie als een veilige basis op zichzelf erkent, dat wil zeggen als een consistente, wordt de consistentie van de klassieke rekenkunde bepaald door mijn resultaat. Als men aan Hilbert's eisen zou willen voldoen, zou het nog steeds de taak zijn om intuïtionistisch rekenkundig consistent te tonen. Dit is echter niet mogelijk door zelfs het formele apparaat van klassieke rekenkunde, op basis van Gödel's resultaat in combinatie met mijn bewijs. Toch ben ik geneigd te geloven dat een consistentiebewijs voor intuïtionistisch rekenen, vanuit een nog duidelijkere positie, mogelijk en ook wenselijk is. (Menzler-Trott 2007, p.38)

Het laatstgenoemde was het doel dat Gentzen zich begin 1932 had gesteld, toen hij in een brief aan zijn oude leraar Hellmuth Kneser schreef:

Ik heb als mijn specifieke taak gesteld om een bewijs te vinden van de consistentie van logische deductie in rekenen … De taak wordt een puur wiskundig probleem door de formalisering van logische deductie. Het bewijs van consistentie is tot nu toe alleen uitgevoerd voor speciale gevallen, bijvoorbeeld de rekenkunde van de gehele getallen zonder de regel van volledige inductie. Ik zou op dit punt verder willen gaan en op zijn minst rekenkunde met volledige inductie willen wissen. Ik werk hier bijna een jaar aan en hoop snel af te zijn, en zou dit werk dan als mijn proefschrift presenteren (met prof. Bernays). (Menzler-Trott 2007, p.31)

4. Natuurlijke aftrek en opeenvolgende calculus

Bij het voortzetten van zijn consistentieprogramma stelde Gentzen als zijn eerste taak de analyse van puur logische deductie, die later zou worden uitgebreid tot rekenen en analyse. In zijn proefschrift (1934–1935) stelt Gentzen dat hij als taak had de analyse van wiskundige bewijzen zoals ze in de praktijk voorkomen. De eerste waarneming is dat feitelijke bewijzen niet zijn gebaseerd op axioma's die in een logische taal zijn uitgedrukt, zoals in Hilbert's axiomatische bewijstheorie. Het meest typische kenmerk is daarentegen dat stellingen hun beweringen doen onder enkele veronderstellingen. De aannames worden in delen geanalyseerd en de conclusie wordt ook in delen geanalyseerd totdat deze twee analyses elkaar ontmoeten en een bewijs kan worden samengesteld. Deze laatste analyse volgt op wat Gentzen introductieregels noemde: ze bieden voldoende voorwaarden om een propositie van een bepaalde vorm af te leiden. Bijvoorbeeld,om een voegwoord A & B af te leiden, volstaat het om de voegwoorden A en B afzonderlijk af te leiden. De conclusie wordt formeel gegeven zoals in de regel

AB	&IK
A & B

Aannames worden daarentegen in hun componenten geanalyseerd door middel van eliminatieregels die over het algemeen directe gevolgen hebben van de aannames. Een conjunctie die als aanname wordt gebruikt, kan bijvoorbeeld worden ontbonden in de bestanddelen ervan, zoals in de regels

A & B & E 1 EEN

A & B & E 2 B

Gentzen ontwikkelde en bestudeerde het systeem van natuurlijke aftrek in 1932 en kwam in september 1932 tot een calculus van natuurlijke aftrek (afgekort ND) die vandaag de dag standaard is. Tegen die tijd had hij gemerkt dat als een inleiding, bijvoorbeeld een afleiding van A & B van A en B afzonderlijk, wordt gevolgd door de overeenkomstige eliminatie, bijvoorbeeld een afleiding van A, de formule A & B een lokaal maximum vormt, een “heuveltje”, dat kan worden geëlimineerd. Hij noemde zulke heuveltjes ook 'omwegen', en wat nu een omwegconversie wordt genoemd, verwijdert zulke onnodige paren van introductie-eliminatiestappen. Het resultaat van de stappen van "normalisatie" is een afleiding in "normale vorm".

Implicatie is misschien meer typerend voor ND dan conjunctie: om A ⊃ B af te leiden, neemt men tijdelijk A aan en probeert vervolgens B af te leiden. Als dit lukt, wordt de tijdelijke aanname gesloten of 'ontslagen' wanneer de conclusie voor A ⊃ B wordt getrokken, zoals in de schematische afleiding

[EEN]
⋮
B	⊃I
A ⊃ B

In de andere richting kan A ⊃ B worden geëlimineerd als een afleiding van A is gevonden, want dan kan B worden geconcludeerd:

A ⊃ BA	⊃E
B

Als regel ⊃I wordt gevolgd door ⊃E, is er een niet-normaliteit die wordt verwijderd door een omwegconversie: een afleiding van B (en wat daarna volgt) wordt geconstrueerd door de afleiding te nemen van de kleine premisse A van de eliminatieregel en de afleiding van B uit de aanname A in de inleiding. Deze twee stukken worden samen gecombineerd tot een afleiding van B die niet de omleidingsformule A ⊃ B heeft. In Gentzen's proefschrift worden alle aannames uiteindelijk afgesloten door implicatie-inleidingen, maar tegenwoordig beschouwt men ook afleidingen die een verzameling formules als open aannames achterlaten.

Kijkend naar de regels van conjunctie en implicatie, merkt men op dat de premissen (de formules direct boven de inferentielijn) subformules zijn van de conclusie in de I-regels, terwijl het andersom is in de E-regels. Gentzen merkte op dat bij normale afleidingen deze eigenschap van enkele stappen wordt geërfd door de hele afleiding, in die zin dat alle formules subformules zijn van de conclusie. Dit resultaat gaf als bijproduct een beslissingsmethode voor intuïtionistische propositionele logica. Een ander logisch gevolg was een syntactisch bewijs van consistentie: als een tegenspraak kan worden bewezen, is alles te bewijzen, maar een atoomformule heeft bijvoorbeeld geen bewijs: als het een bewijs heeft, heeft het een normaal bewijs, maar zijn er geen E-regels van toepassing op een atomaire formule, en geen enkele I-regel concludeert het ook.

Het idee van Gentzen was om de natuurlijke aftrek uit te breiden tot een rekenstelsel door een regel toe te voegen die overeenkomt met het principe van volledige inductie. Consistentie zou dan volgen uit de normalisatie van afleidingen en de eigenschap van de subformule. Begin 1933 realiseerde Gentzen zich dat deze bewijsstrategie niet door zou gaan: de inductieregel is schematisch en heeft een oneindig aantal instanties, zonder gebonden te zijn aan de complexiteit van de inductieformules. Het is onmogelijk om deze formules van tevoren te beperken, dus kan geen enkele eigenschap van een subformule gelden. Na deze mislukking haalde Gentzen de vertaling van klassieke naar intuïtionistische rekenkunde woordelijk uit zijn vroege proefschriftmanuscript en diende het als een paper in maart 1933 in, maar trok het paper terug na het horen van Gödel's publicatie van het resultaat.

Gentzen schreef dat hij geen normalisatiestelling kon bewijzen voor een klassiek systeem van ND. Hij bedacht daarom een andere logische calculus die hij sequent calculus noemde (Sequenzenkalkul, letterlijk "calculus van sequenties") en maakte er het centrale onderwerp van zijn proefschrift van. De naam van de calculus komt van de weergave van aannames van een afleiding als een lijst. Het woord "sequent" dat als zelfstandig naamwoord wordt gebruikt, is een suggestie van Kleene's in zijn Inleiding tot de metamathematica (1952: 441), die in veel talen is opgenomen in de vorm van puur verzonnen woorden.

Sequent calculus, kortweg SC, kan worden gezien als een formele weergave van de afleidingsrelatie in natuurlijke aftrek. Een sequent bestaat uit een lijst Γ van formules, een pijl (in Gentzen zijn later ook andere markers gebruikt), en één formule als conclusie. De lijst geeft de aannames waarvan de conclusie afhangt in een afleiding, in een lokale notatie waar ze in ND worden gevonden in de bladeren van een afleidingsboom. Gentzen generaliseerde ook sequenties zodat ze, in plaats van één conclusie, een lijst met mogelijke gevallen achter de pijl hebben. Deze nieuwigheid leidde tot de eerste bevredigende formulering van een bewijssysteem voor klassieke logica. De SC-regels van Gentzen voor voeging en implicatie zijn, met komma's die elementen in lijsten scheiden:

Conjunctie
Γ → Δ, A Γ → Δ, B R & Γ → Δ, A & B	A, Γ → Δ L & 1 A & B, Γ → Δ	B, Γ → Δ L & 2 A & B, Γ → Δ

Implicatie
A, Γ → Δ, B R⊃ Γ → Δ, A ⊃ B	Γ → Θ, AB, Δ → Λ L⊃ EEN ⊃ B, Γ, Δ → Θ, Λ

Dit is niet de plaats om de details van ND en SC uit te leggen (maar zie de vermelding over geautomatiseerd redeneren). Gentzen formuleerde het laatste, aangeduid met LK, zodat het een intuïtionistische calculus opleverde, aangeduid met LJ, als een speciaal geval, het geval waarin de conclusie een lijst is van hoogstens één geval. Vervolgens bewees hij het analoog van de normalisatiestelling voor de klassieke calculus, de calculus en het bewijs zorgvuldig geformuleerd, zodat het resultaat voor de intuïtionistische calculus een speciaal geval was van dat voor de klassieke calculus. In LJ en LK staat L voor "logistiek", een term waarmee Gentzen verwijst naar de axiomatische logica van Frege, Russell en Hilbert en Bernays. In dergelijke berekeningen is elke regel in een afleiding op zichzelf correct, dat wil zeggen een logische waarheid, vandaar de term. De letters K en J komen van de Duitse woorden klassisch en intuïtionistisch.(Dit laatste zou dus hoofdletter "I" moeten zijn, maar oudere Duitsers gebruiken hoofdletters "J" voor hoofdletters "I".)

Gentzen noemde het analoog van normalisatie de fantasieloze naam Hauptsatz, 'hoofdstelling'. De standaardterminologie van vandaag is de 'verwijderingsstelling'. Alle logische regels van SC hebben de eigenschap van de subformule in zeer directe zin: elke formule in een premisse is een formule of subformule in de conclusie. De regel voor het combineren van afleidingen, analoog aan de regel die hierboven is uitgelegd voor het geval van omleidingsconversies in ND, wordt "cut" genoemd. Daarin verschijnt formule A als casus in een eerste premisse en als aanname in een tweede premisse. In de conclusie is deze formule verdwenen en zijn de aannames van de twee premissen bij elkaar verzameld:

Γ → AA, Δ → C	Besnoeiing
Γ, Δ → C

Dus knippen is de enige regel die ervoor zorgt dat een formule in een afleiding "verdwijnt". Gentzen toonde aan dat gevallen van de snijlijn kunnen worden geëlimineerd uit afleidingen door ze naar boven toe te permuteren totdat ze punten bereiken waarop de afleiding begint. In ND zijn de uitgangspunten aannames, in SC zijn het "initiële sequenties" van de vorm A → A waarin de aanname formule A tegelijkertijd de conclusie is. Een snee met zo'n sequentie als de ene premisse heeft de andere premisse gelijk aan de conclusie en kan daarom worden verwijderd.

Na het bewijs van eliminatie van snijwonden, had Gentzen geen gebruik van het bewijs van normalisatie voor intuïtionistische natuurlijke deductie. Hij gaf de eerste handgeschreven versie van zijn proefschrift, met het gedetailleerde bewijs van normalisatie (equivalent aan ongeveer 13 afgedrukte pagina's) aan Bernays, maar de laatste lijkt nooit te hebben beseft wat hij in handen had. Het bewijs, onder de papieren van Bernays in Zürich, werd in februari 2005 door de huidige auteur ontdekt en is nu beschikbaar in een Engelse vertaling (Gentzen 1933 [2008]).

5. De consistentie van rekenen en analyse

Na zijn scriptiewerk aan ND en SC voor pure logica, zette Gentzen zijn plan voort om de consistentie van rekenen te bewijzen. Het resultaat was in december 1934 gereed. Wat dit allereerste bewijs was, is niet in detail bekend. Een brief aan Bernays uit 1938 geeft echter aan dat het bewijs dat Gentzen tegen de zomer van 1935 opschreef niet dit origineel was, maar een tweede bewijs (zie Menzler-Trott 2001, 79). Dit tweede bewijs werd bekritiseerd door Bernays en Gödel die het bespraken tijdens hun Atlantische reis naar Princeton in september 1935. Het idee van Gentzen in het bewijs was als volgt: neem eerst het conjunctie-negatie-universele kwantificeringsfragment van natuurlijke deductie als logica die wordt gebruikt in de formalisering van rekenen. Schrijf vervolgens elke regelinstantie zodat de uitgangspunten en conclusie de open aannames hebben die links worden vermeld,met een pijl die de conclusie scheidt, dus als sequenties. Deze variant van ND heet nu ND in SC-stijl. Overweeg een sequentie Γ →C. Als de conclusie een atoomformule is, is het een vergelijking tussen getallen. In het ergste geval is het vals, dus overweeg dan de lijst met aannames. Als een aanname een voegwoord is, vervang het dan door een conjunct naar keuze, als een universele kwantificering, door een instantie. Als het een ontkenning is ¬ A, vervang dan de conclusie door A. Als in een van de stadia van dit "reductieproces" de conclusie van een sequent een samengestelde formule is, moet u elke conjunctie of elk geval van universele kwantificatie als een mogelijke conclusie beschouwen. In het geval van ontkenning ¬ A als conclusie, verplaats A naar het verondersteldeel en vervang de conclusie door 0 = 1. Gentzen laat zien dat door op deze manier verder te gaan in de veronderstelling dat de sequent in kwestie afleidbaar is, ofwel een echte vergelijking wordt gevonden als conclusie, of een valse vergelijking als aanname. Dus,er zijn geen afleidbare sequenties met alle aannames waar en de conclusie onwaar.

Het was onduidelijk voor Gödel en Bernays wat het bewijs veronderstelde; ze dachten dat het veronderstelde wat in de intuïtionistische wiskunde bekend staat als de stelling van de fans, maar dit was onjuist. Beëindiging van Gentzen's reductieprocedure kan in plaats daarvan worden bewezen door inductie op goed gefundeerde bomen ("staafinductie"), een principe dat Gentzen op intuïtieve gronden gebruikte. Hoe dan ook, het resultaat van de kritiek was dat Gentzen het bewijs zonder verder oponthoud veranderde in een derde bewijs dat het nu beroemde principe van transfinite inductie gebruikt tot aan het eerste epsilon-nummer. Deze inductie werd gepresenteerd door middel van een codering die decimale getallen gebruikte. Het concrete resultaat van de wijzigingen voor Gentzen's paper gepubliceerd in 1936 was echter niet goed: de logische berekening werd halverwege gewijzigd in een artikel van zeventig pagina's dat erg moeilijk te lezen werd. Daarom gaf Gentzen nog een ander, door de huidige telling het vierde bewijs van de consistentie van rekenen in 1938 (in het Bernays-archief van de ETH Zürich), dit keer gebaseerd op de klassieke sequentrekening LK van 1933. Zoals gezegd, blijkt uit correspondentie met Bernays dat hij keerde daarmee terug naar de bewijsmethode die in 1934 tot succes had geleid. Het gebruik van transfinite inductie wordt duidelijk zichtbaar gemaakt in het artikel uit 1938 door middel van een ordinale notatie. Dergelijke inductieprincipes over Cantors 'tweede getallenklasse' worden in detail besproken in Hilbert's lezing uit 1925 'Über das Unendliche' ('Over het oneindige', gepubliceerd in 1926), een paper waarnaar Gentzen verwees.deze keer gebaseerd op de klassieke sequentrekening LK van 1933. Zoals gezegd, blijkt uit correspondentie met Bernays dat hij daarmee terugkeerde naar de bewijsmethode die in 1934 tot succes had geleid. Het gebruik van transfinite inductie wordt duidelijk zichtbaar gemaakt in het artikel uit 1938 door middel van een ordinale notatie. Dergelijke inductieprincipes over Cantors 'tweede getallenklasse' worden in detail besproken in Hilbert's lezing uit 1925 'Über das Unendliche' ('Over het oneindige', gepubliceerd in 1926), een paper waarnaar Gentzen verwees.deze keer gebaseerd op de klassieke sequentrekening LK van 1933. Zoals gezegd, blijkt uit correspondentie met Bernays dat hij daarmee terugkeerde naar de bewijsmethode die in 1934 tot succes had geleid. Het gebruik van transfinite inductie wordt duidelijk zichtbaar gemaakt in het artikel uit 1938 door middel van een ordinale notatie. Dergelijke inductieprincipes over Cantors 'tweede getallenklasse' worden in detail besproken in Hilbert's lezing uit 1925 'Über das Unendliche' ('Over het oneindige', gepubliceerd in 1926), een paper waarnaar Gentzen verwees.s lezing uit 1925 'Über das Unendliche' ('On the infinite', gepubliceerd 1926), een paper waarnaar Gentzen verwees.s lezing uit 1925 'Über das Unendliche' ('On the infinite', gepubliceerd 1926), een paper waarnaar Gentzen verwees.

Je zou denken dat dat het was, maar Gentzen had reden om zelfs een vierde bewijs te leveren van de consistentie van rekenen, in zijn laatste paper, gepubliceerd in 1943 maar geschreven voor de oorlog in 1939. Hij breidde Peano-rekenkunde uit door middel van transfinite ordinals en maakte de transfinite inductieprincipe onderdeel van deze uitgebreide calculus. Vervolgens liet hij direct zien dat transfinite inductie tot aan het eerste epsilon-nummer ε ₀ in het systeem wel uit te drukken maar niet aantoonbaar is. De onvolledigheidsstelling van Gödel wordt dus op een heel andere manier bewezen. Het idee van het bewijs is, in het kort, als volgt: eerst wordt vastgelegd wat het betekent om transfinite inductie af te leiden tot een specifiek rangnummer in het systeem. Ten tweede, rangnummers onder ε ₀worden geassocieerd met afleidingen. Dit worden 'waarden' genoemd. Vervolgens wordt getoond dat als transfinite inductie naar een rangnummer afleidbaar is, dit rangnummer niet groter kan zijn dan de waarde van de afleiding. Daarom is transfinite inductie naar ε ₀ niet af te leiden.

Aangezien het inductieprincipe kan worden uitgedrukt maar niet bewezen in gewone rekenkunde, wordt een formule gevonden die niet kan worden bewezen in Peano-rekenkunde. Een gemakkelijk gevolg van Gentzen's versie van de onvolledigheidsstelling is de consistentie van Peano-rekenkunde, omdat alles zou kunnen worden bewezen in een inconsistent systeem. In tegenstelling tot Gödel's "kunstmatige" onbewijsbare formule die werd verkregen door middel van een codering van het rekenkundig bewijsbaarheidspredikaat, is Gentzen's transfinite inductieprincipe een principe van "gewone" wiskunde.

Het laatste bewijs van Gentzen bepaalde de 'proof-theoretic ordinal' van Peano-rekenkunde, namelijk degene die nodig is om de consistentie te bewijzen, met de eigenschap dat niets minder zou volstaan. Het werk markeerde het begin van de theorie van de ordinale bewijzen. Het was zonder twijfel de meest opmerkelijke fundamentele prestatie in de rekenkunde na Gödel's onvolledigheidsstellingen, maar het is nog grotendeels onbekend - men kan veel boeken vinden over Gödel's stellingen die Gentzen niet eens noemen.

Gödel had er blijkbaar niet aan gedacht om een consistent bewijs van rekenen te geven door het gebruik van niet-finitaire maar nog steeds constructieve principes. Eind jaren dertig, tenminste vanaf 1938, ontwikkelde hij als antwoord op het bewijs van Gentzen zijn eigen speciale interpretatie van intuïtionistische logica en rekenkunde, wat bekend werd als de dialectische interpretatie. Het gebruikt berekenbare functionaliteiten om de bewijzen van intuïtionistische rekenkunde te interpreteren. Gödel publiceerde de interpretatie pas in 1958, ook al had hij hem in lezingen in 1941 gepresenteerd. Het is niet bekend of hij de kwestie besprak toen hij Gentzen ontmoette in december 1939.

Op verzoek van Bernays reproduceerde Ackermann het bewijs van Gentzen in termen van Hilbert's epsilon-calculus in 1940. Het document van Ackermann was het startpunt van Kreisels 1951 'niet-tegenvoorbeeld'-interpretatie van rekenen. Het was een verrassing toen de publicatie van Gödel's verzamelde papers zijn "Zilsel-lezing" in Wenen in 1938 aan het licht bracht: hij schetst daar deze interpretatie als een herformulering van Gentzen's bewijs uit 1935. (De kwestie wordt in detail besproken in Tait (2005), die zelf in de jaren zestig had gewerkt aan de interpretatie zonder tegenvoorbeeld en de uitbreiding ervan tot analyse.)

De volgende voor de hand liggende taak in de bewijstheorie, na het bewijs van de consistentie van rekenen, was het bewijzen van de consistentie van analyse, dat wil zeggen van de theorie van reële getallen. Gentzen deed wat werk in deze richting, maar werd in het najaar van 1939 toegewezen aan militaire dienst. (Hij observeerde en rapporteerde het type, het aantal en de richting van vliegtuigen die boven de stad Brunswick vlogen, totdat hij werd geraakt door een zenuw inzinking begin 1942.) Vanaf 1943 hervatte hij het analysewerk, maar de moeilijkheden die inherent waren aan het onderwerp waren groot, evenals de praktische moeilijkheden van het leven veroorzaakt door de oorlog. Analyse zou worden geformuleerd als een systeem van rekenkunde van de tweede orde, wat betekent dat kwantificering wordt uitgebreid over getaltheoretische predikaten of, equivalent, over sets van natuurlijke getallen. De tweede-orde getaltheorie wordt gebruikt in Gentzen's laatste paper,gepubliceerd in 1943, waarin kort wordt aangetoond dat het principe van transfinite inductie tot ε₀ is af te leiden in de tweede-orde getaltheorie.

Meer dan een halve eeuw is verstreken zonder constructief bewijs van de consistentie van volledige tweede-orde rekenkunde in zicht. Tot de pioniers op dit gebied behoorden Kurt Schütte en Gaisi Takeuti. De eerste creëerde in 1951 een oneindige opeenvolgende calculus om consistentieproeven op een opvallende manier te presenteren, de laatste gebruikte in plaats daarvan een meer traditionele Gentzen-achtige calculus (zie Takeuti 1987).

In het huidige onderzoek naar de bewijstheorie van rekenkunde van de tweede orde bestudeert men zogenaamde subsystemen van rekenkunde van de tweede orde. De sterkste resultaten van vandaag zijn, in een zeer korte schets, de volgende: laat X de getaltheoretische predikaten overschrijden. Een formule zoals X (x) stelt dat x de eigenschap heeft die wordt uitgedrukt door X. We kunnen nu logica van de eerste en tweede orde gebruiken om samengestelde formules te vormen, zoals ∀ X (X x ∨ ¬ X x). De verzameling natuurlijke getallen waarvoor een dergelijke formule met één universele tweede-orde-kwantor geldt, wordt een Π11-set genoemd (in dit geval het geheel van de natuurlijke getallen). Meer in het algemeen heeft een begrijpend axioma de vorm ∃ X ∀ x (X x ↔ B (x)). Als de formule B geen kwantificatoren van de tweede orde heeft, geeft het axioma een zogenaamd rekenkundig begrip of ACA. Als B de vorm ∀ Y ∃ ZC (x) kan hebben zonder andere tweede-orde kwantoren, wordt het speciale geval van Π12-begrip verkregen. Toshiyasu Arai en Michael Rathjen hebben halverwege de jaren negentig consistentiebewijzen voor een subsysteem van rekenkunde van de tweede orde met Π12-begrip geleverd. (zie Rathjen 1995 voor deze ontwikkelingen).

6. Latere ontwikkelingen in natuurlijke aftrek

In de tijd dat Gentzen zijn systeem van natuurlijke aftrek uitwerkte, ontwikkelde Stanislaw Jaskowski ook een logisch systeem voor redeneren met aannames. Formules in afleidingen zijn gerangschikt in een lineaire opeenvolging, maar Jaskowski's paper uit 1934 bleef fragmentarisch en zonder substantiële resultaten zoals een subformule-eigenschap. De lineaire variant van natuurlijke deductie wordt gevolgd in veel pedagogische uiteenzettingen van elementaire logica (ook wel "Fitch-systemen" genoemd). Gentzen vond Jaskowski's werk tegen juni 1936, toen beiden in Münster waren, en beschouwde de lineaire opstelling van formules als een verbetering, een 'bevrijding van het keurslijf van de boomvorm', in een die 'de lineariteit van het denken' weerspiegelt (de eerste van ongepubliceerde aantekeningen, de laatste uit Gentzen's proefschrift).

Het systeem van natuurlijke aftrek bleef ongeveer dertig jaar inactief, tot de thesis van Dag Prawitz van 1965, Natural Deduction: A Proof-Theoretical Study. De volgorde waarin Prawitz de normalisatiestelling presenteerde, was anders dan die in Gentzen's vroege proefschriftmanuscript. Prawitz gaf eerst een normalisatiestelling en subformule-eigenschap voor een systeem van natuurlijke afleiding voor klassieke logica. Dit systeem bevat geen disjunctie of bestaan. In een tweede fase overwoog hij intuïtionistische natuurlijke deductie voor de volledige taal van de predikaatlogica en reduceerde de normalisatie ervan tot het verwijderen van omwegconversies zoals in het fragment van de klassieke logica. Toen Gentzen's bewijs van normalisatie in 2005 aan het licht kwam, zei Prawitz, in gesprek met de huidige auteur, dat het duidelijk is dat Gentzen het resultaat kende,omdat de opmerkingen in het gedrukte proefschrift zo suggestief zijn.

Eind jaren zestig werd sterke normalisatie een probleem: Prawitz bewees met behulp van eerder werk van William Tait en Jean-Yves Girard in 1971 dat niet-normaalheden in een afleiding in elke volgorde kunnen worden omgezet, met een beëindigend normalisatieproces en een uniek normale afleiding als resultaat. Gentzen lijkt het laatste niet te hebben opgemerkt, maar lijkt eerder het tegendeel te hebben gedacht door het falen van deze eigenschap voor het elimineren van bezuinigingen in de opeenvolgende calculus.

Ongeveer op hetzelfde moment dat sterke normalisatie werd bestudeerd, kwam de Curry-Howard-correspondentie naar voren. Curry had in zijn werk over combinatorische logica eind jaren vijftig de analogie waargenomen tussen eliminatie van implicaties bij natuurlijke deductie en functionele toepassing (Curry en Feys 1958). Het idee was zo oud als de intuïtionistische logica: door de "BHK-uitleg" van de connectieven en kwantoren (voor Brouwer-Heyting-Kolmogorov), drukken de vormen van proposities in de intuïtionistische logica voorschriften uit om die proposities te bewijzen: een conjunctie A & B wordt bewezen door A en B afzonderlijk te bewijzen, een disjunctie A ∨ B door een van A en B te bewijzen, en een implicatie A ⊃ B door te laten zien hoe je elk bewijs van A kunt omzetten in een bewijs van B, enzovoort. Deze uitleg komt heel dicht in de buurt van de introductie regels van natuurlijke aftrek,maar het blijft onbekend wat hun effect op de gedachte van Gentzen was.

De Curry-Howard-correspondentie, afkomstig uit een paper van William Howard uit 1969, maar pas in 1980 gepubliceerd, is gebaseerd op het 'formules-als-typen'-principe, of in een ander jargon, op het' propositions-as-sets'-principe. Een voorstel wordt beschouwd als een reeks bewijzen. De waarheid van een propositie komt overeen met de niet-leegheid van de set. Bewijzen van A ⊃ B zijn nu functies van (bewijzen van) A tot (bewijzen van) B en A ⊃ B zelf de verzameling van dergelijke functies. Dus als f: A ⊃ B en a: A, dan geeft functionele toepassing f (a): B. Het omgekeerde, dat overeenkomt met de introductie van een implicatie, wordt vastgelegd door het principe van functionele abstractie van de λ-calculus van Alonzo Church.

De correspondentie tussen Curry en Howard heeft intuïtionistische natuurlijke deductie tot een onderdeel van het computerwetenschappelijke curriculum gemaakt: het geeft een computationele semantiek voor intuïtionistische logica waarin berekeningen en de uitvoering van programma's in het algemeen worden bewerkstelligd door normalisatie. Een bewijs van implicatie A ⊃ B is bijvoorbeeld een programma dat gegevens van type A omzet in een uitvoer van type B. De constructie van een object (proef, functie, programma) f van het type A ⊃ B eindigt met een abstractie. Als een object a van type A als argument in f wordt ingevoerd, is de resulterende uitdrukking niet normaal, maar heeft deze een vorm die overeenkomt met een inleiding gevolgd door een eliminatie. Normalisatie is nu hetzelfde als de uitvoering van het programma f. Het gebruik van intuïtionistische logica is niet gebonden aan enige intuïtionistische filosofie van de wiskunde,maar is slechts een systematische garantie voor het beëindigen van de uitvoering van computerprogramma's.

7. Sequent Calculus: latere ontwikkelingen / toepassingen

Gentzen's proefschrift markeerde de geboorte van de structurele bewijstheorie, in tegenstelling tot de oude axiomatische bewijstheorie van Hilbert. Oiva Ketonen zette in zijn proefschrift van 1944 een opmerkelijke stap voorwaarts in de ontwikkeling van systemen van sequentiële calculus. Ketonen, een student wiskunde en filosofie in Helsinki, ging in 1938 naar Göttingen om de theorie te bestuderen, waarbij Gentzen de dichtstbijzijnde was aan een student die laatstgenoemde ooit heeft gehad. Het verband lijkt te zijn gelegd door Ketonen's filosofieprofessor Eino Kaila die Gentzen in 1936 in Münster had ontmoet. Ketonen herinnerde zich later dat Gentzen 'een sympathieke jongeman van weinig woorden' was die hem een inleiding gaf over de bewijstheoretische systemen en resultaten. Ketonen 'De bekendste ontdekking is een sequentierekening voor klassieke propositionele logica waarvan de logische regels allemaal omkeerbaar zijn, wat betekent dat wanneer een sequent een vorm heeft die overeenkomt met de conclusie van een logische regel, de bijbehorende premissen, uniek gedefinieerd uit de gegeven sequent en de regel zijn ook afleidbaar. Het omgekeerde is onmiddellijk (pas gewoon de regel toe). Regels L & en L⊃ worden bijvoorbeeld gewijzigd in

A, B, Γ → Δ L & A & B, Γ → Δ

Γ → Δ, AB, Γ → Δ L⊃ A ⊃ B, Γ → Δ

Er is slechts één linkerregel voor voeging (en twee keer slechts één rechterregel voor disjunctie). De linkse implicatieregel heeft zogenaamde "gedeelde contexten": de aannames en gevallen in de conclusie, behalve de formule met het verbindende, worden in beide premissen identiek herhaald. Ketonen's idee was om een systeem van zoeken naar bewijzen te definiëren: men vertrekt van een bepaalde sequentie die moet worden afgeleid, kiest er een formule in en schrijft de premissen van een regel die de gegeven sequentie kan afsluiten. Door omkeerbaarheid wordt de kwestie van afleidbaarheid vervangen door een of twee equivalente afleidingsvragen op eenvoudigere sequenties. De nieuwe regels zijn nodig om te zorgen voor uniek gedefinieerde premissen bij een dergelijke "root-first" -decompositie.

Ketonen's bewijs van inverteerbaarheid van de logische regels van zijn opeenvolgende calculus gebruikte de structurele snijregel. Later leverden Kurt Schütte (1950) en Haskell Curry (1963) directe bewijzen van omkeerbaarheid, de laatste met het expliciete resultaat dat de inversies hoogtebesparend zijn: als een gegeven sequent in maximaal n stappen kan worden afgeleid, gaat de premisse uit in een regel die kan concluderen dat sequent ook een afleiding heeft in maximaal n stappen.

Hoeveel van Ketonen's werk voortkomt uit suggesties van Gentzen blijft onbekend, omdat er geen correspondentie is gevonden. Ketonen schrijft in het voorwoord van zijn proefschrift dat “Dr. G. Gentzen uit Göttingen wees me op het probleemgebied van dit werk”. Het proefschrift was Ketonen's enige originele werk in de logica, gered van de vergetelheid door een lange recensie die Bernays erover schreef voor The Journal of Symbolic Logic in 1945.

Een persoon die Ketonen's calculus eind jaren veertig kende, was Evert Beth. Toen Beth later, in 1955, zijn bekende tableau-calculus presenteerde, lijkt hij de oorsprong van de tableau-calculus te zijn vergeten als een herformulering van die van Ketonen, maar verwijst hij in plaats daarvan naar Kleene's invloedrijke Inleiding tot de metamathematica van 1952. Kleene had genomen omhoog Ketonen's calculus uit de Bernays 'review en behandelde ook intuïtionistische sequent calculus waarin de omkeerbaarheid beperkter is dan in de klassieke calculus. Met Kleene's boek werden Gentzen's opeenvolgende calculi algemeen bekend en toegankelijk.

Kleene's werk uit de vroege jaren vijftig was ook een pionier in een opmerkelijke ontwikkeling in sequentiële calculus, namelijk de "contractie-vrije" klassieke en intuïtionistische calculi die tegenwoordig worden aangeduid met G3c en G3i. Deze berekeningen hebben de eigenschap dat geen van Gentzen's oorspronkelijke "structurele regels" nodig is. De regel van "verzwakking" staat de toevoeging van overbodige gevallen en veronderstellingen toe, en de regel van "contractie" de verwijdering van één kopie van een formule als er twee aanwezig waren in een lijst, zoals in

Verzwakking		Contractie
Γ → Δ Wk A, Γ → Δ		A, A, Γ → Δ Ctr A, Γ → Δ

Analoge regels maken verzwakking en contractie in de juiste, opeenvolgende delen van sequenties mogelijk. Verzwakking wordt een elimineerbare regel gemaakt door aanvankelijke sequenties de vorm A, Γ → Δ, A te laten hebben in plaats van Gentzen's A → A. Samentrekking wordt eveneens geëlimineerd door een geschikte formulering van de regels. De import is dat er bij root-first proof zoeken geen regels hoeven te worden toegepast die een duplicatie van een formule in een premisse zouden opleveren. Zonder dit resultaat zou het niet beëindigen van het zoeken naar bewijzen niet volgen.

De klassieke calculus heeft de hierboven genoemde eigenschap van hoogtebesparende omkeerbaarheid van zijn logische regels. Albert Dragalin verfijnde eind jaren zeventig de calculus tot een waarin de structurele regels bovendien "hoogtebesparend toelaatbaar" zijn, wat betekent dat wanneer de premisse van een dergelijke regel afleidbaar is, de conclusie afleidbaar is zonder de regel en met hoogstens hetzelfde grootte (maximum aantal regelinstanties in een afleidingstak) van afleiding. Deze eigenschap heeft diepgaande effecten op de eliminatie van snijwonden: bij het permuteren van snijwonden moest Gentzen de oorspronkelijke contexten (de Γ's en Δ's) herstellen door verzwakkingen en contracties. Met de hoogtebesparende toelaatbaarheid van deze regels, neemt de omvang van een afleiding niet toe wanneer de regels worden toegepast. Dragalin gaf ook een intuïtionistische calculus met meerdere successen met dezelfde soort ontvankelijkheid van de structurele regels. Troelstra, tenslotte, gaf in het leerboek Basic Proof Theory (2000, eerste ed. 1996) een intuïtionistische calculus met één successie en een hoogtebesparende toelaatbaarheid van verzwakking en contractie. De samentrekkingsvrije sequentieberekeningen zijn krachtige hulpmiddelen voor de analyse van formele afleidingen. Veel moeilijke logische onderzoeksresultaten worden slechts oefeningen door controle over de structuur van bewijzen die de G3 -calculi toestaan. De samentrekkingsvrije sequentieberekeningen zijn krachtige hulpmiddelen voor de analyse van formele afleidingen. Veel moeilijke logische onderzoeksresultaten worden slechts oefeningen door controle over de structuur van bewijzen die de G3 -calculi toestaan. De samentrekkingsvrije sequentieberekeningen zijn krachtige hulpmiddelen voor de analyse van formele afleidingen. Veel moeilijke logische onderzoeksresultaten worden slechts oefeningen door controle over de structuur van bewijzen die de G3 -calculi toestaan.

De vroegste toepassing van opeenvolgende calculus in de wiskunde was in de bewijstheorie van rekenkunde, in Gentzen's proefschrift en op een beslissende manier in het bewijs van de consistentie van rekenkunde uit 1938. Troelstra noemt het werk van Ketonen als

een vroege analyse van snijvrije bewijzen in Gentzen calculi met axioma's; maar hij overweegt de vorm van snijvrije afleidingen in de zuivere calculus waar axioma's aanwezig zijn in het antecedent van de afgeleide sequenties. (Troelstra en Schwichtenberg 2000: 142)

De axioma's die Ketonen beschouwt, zijn die van projectieve en affiene geometrie, de eerste uit het artikel van Skolem uit 1920 dat in de eerste sectie hierboven werd besproken. Ketonen wilde de formele bewijsregels van Skolem formuleren binnen sequent calculus. Het werk van Ketonen was echter vooral alleen bekend door de beoordeling door Bernays en alleen het logische deel van de sequentierekening werd daar in detail uitgelegd.

Een tweede manier om de sequentieberekening toe te passen, is om sequenties die beginnen met afleidingstakken, naast de initiële sequenties ook de vorm → A te geven, waarin A een axioma is, of een instantie van een universeel axioma. Nu, door Gentzen's "uitgebreide Hauptsatz", kunnen bezuinigingen op afleidingen worden doorgevoerd tot een van hun premissen een axioma is, maar deze bezuinigingen op axioma's blijven bestaan. Een andere, nieuwere methode is om axioma's om te zetten in extra regels die worden toegevoegd aan de logische regels van sequentiële calculus, met behoud van volledige cut-out eliminatie (zoals uitgelegd in Negri en von Plato 2001, hoofdstuk 6, en in Troelstra en Schwichtenberg's 2000, hoofdstuk 4.7).

8. De doelstellingen van de bewijstheorie

In hoeverre heeft de bewijstheorie haar oorspronkelijke doelen bereikt? Voor Hilbert waren de doelen een volledige opheldering van de fundamentele problemen door middel van finitaire bewijzen van consistentie, enz., Doelen waarin de bewijstheorie faalde. Hilbert was in zijn programma niet geïnteresseerd in het bestuderen van wiskundige bewijzen op zich, maar alleen in het ophelderen van de centrale fundamentele problemen (en deze vervolgens te vergeten). Een recent gevonden aantekening van Hilbert geeft een ander beeld: in de aantekening staat dat Hilbert als 24e en laatste probleem in zijn beroemde Parijse lijst van openstaande wiskundige problemen van 1900 de ontwikkeling van 'een theorie van beproefde methoden in de wiskunde' wilde toevoegen. Dit was voordat zijn metamathematisch programma voor de ontwikkeling van een bewijstheorie naar voren kwam.

Voor Gentzen waren de doelen, samen met die van Hilbert, om de structuur van wiskundige bewijzen te begrijpen. Dit programma was een absoluut succes wat betreft pure logica en rekenen. Vooral de methoden van opeenvolgende calculus maken de analyse van bewijzen met diepgaande resultaten mogelijk. Het grote doel van de bewijstheorie, een bewijs van de consistentie van analyse zoals in Hilbert's tweede probleem in Parijs, is niet verwezenlijkt maar wordt ook niet uitgesloten.

Enig begrip van het begrip bewijs is nodig voor elke wiskundige, althans voor niets, dan in ieder geval voor de overdraagbaarheid van wiskundige resultaten: publicatie berust op het begrip dat bewijzen zo expliciet kunnen worden gemaakt dat ze routinematig controleerbaar zijn op juistheid. De bewijstheorie is tot nu toe echter geen praktisch hulpmiddel geworden voor de werkende wiskundige; de toepassingen in de wiskunde waren nogal geïsoleerde gevallen. Recent werk over het formaliseren van wiskundige bewijzen met geautomatiseerde systemen, proefeditors genoemd, kan dit beeld geleidelijk veranderen.

Bewijstheorie heeft nieuwe doelen gecreëerd buiten de traditionele wiskunde, vooral in verband met informatica. Onderwerpen als de verificatie van de juistheid van computerprogramma's zijn een uitvloeisel van de bewijstheorie. Natuurlijke afleiding heeft geleid tot de Curry-Howard-correspondentie en tot verbanden met functionele programmering, en sequentiele calculus wordt vaak gebruikt in systemen van automatisch zoeken naar bewijzen, zoals in logische programmering.

Bibliografie

Teksten over de proefleer

• Buss, Sam (red.), 1998, Handbook of Proof Theory, Amsterdam: Elsevier.
• Negri, S. en J. von Plato, 2001, Structural Proof Theory, Cambridge: Cambridge University Press.
• von Plato, J., 2013, Elements of Logical Reasoning, Cambridge: Cambridge University Press.
• Takeuti, G., 1987, Proof Theory, Amsterdam: Noord-Holland, 2e druk.
• Troelstra, A. en H. Schwichtenberg, 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2e editie.

Originele werken en hun reproducties

• Ackermann, W. 1940, "Zur Widerspruchsfreiheit der Zahlentheorie", Mathematische Annalen, 117: 162–194.
• Beth, E., 1955, Semantische gevolgtrekking en formele afleidbaarheid (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe reeks, deel 18, no. 13), Amsterdam: Noord-Holland.
• Church, A., 1936, 'A Note on the Entscheidungsproblem', Journal of Symbolic Logic, 1: 40–41.
• Curry, H., en Feys, R., 1958. Combinatory Logic. (Studies in Logic and the Foundations of Mathematics, Vol. I), 1e druk, Amsterdam: Noord-Holland.
• Curry, H., 1963, Foundations of Mathematical Logic, New York: McGraw-Hill; herdrukt New York: Dover, 1977.
• Dragalin, A., 1988, Mathematical Intuitionism: Introduction to Proof Theory, Providence, RI: American Mathematical Society.
• Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Investigations into Logical Inference), Ph. D. proefschrift, Universität Göttingen. Gepubliceerd in Gentzen 1969: 68–131.
• Gentzen, G., 1938, "Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie", Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19–44. Vertaald in Gentzen 1969: 252–286.
• Gentzen, G., 1943, "Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie", Mathematische Annalen, 119: 252–286. Vertaald in Gentzen 1969: 287–308.
• Gentzen, G., 1969, The Collected Papers of Gerhard Gentzen, ed. M. Szabo, Amsterdam: Noord-Holland.
• Gentzen, G., 2008, 'The normalization of derivations', 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, "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes", Dialectica, 12: 280–287.
• Gödel. K., 1986-2003, Collected Papers (Volumes I – V), S. Feferman et al. (redactie), Oxford: Oxford University Press.
• van Heijenoort, J., 1967, From Frege to Gödel, Cambridge, MA: Harvard University Press.
• Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: BG Teubner.
• Hilbert, D., 1926, "Über das Unendliche" ("Op het oneindige"), Mathematische Annalen, 95: 161–190. [Lezing gegeven Münster, 4 juni 1925.]
• Hilbert, D., en 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], "Het formules-als-typen-idee van constructie", in J. Seldin en J. Hindley (red.), To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Londen, New York: Academic Press, blz. 480–490.
• Jaskowski, S., 1934, "Over de regels van veronderstelling in formele logica", in S. McCall (red.), Polish Logic 1920–1939, Oxford: Clarendon Press, 1967, pp. 232–258.
• Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae scientiarum fennicae (Ser. AI 23), Helsinki.
• Kleene, S., 1952, Inleiding tot de metamathematica, Amsterdam: Noord-Holland.
• Kreisel, G., 1951, "Over de interpretatie van niet-finitistische bewijzen: deel I", The Journal of Symbolic Logic, 16 (4): 241–267.
• Löwenheim, L., 1915, "Über Möglichkeiten im Relativkalkül", Mathematische Annalen, 76 (4): 447–470.
• Menzler-Trott, E., 2001, Gentzens Problem, Berlijn: Birkhäuser Verlag.
• Menzler-Trott, E., 2007, Logic's Lost Genius: The Life and Work of Gerhard Gentzen, Providence, RI: American Mathematical Society.
• Prawitz, D., 1965, Natural Deduction: A Proof-Theoretical Study, Stockholm: Almqvist & Wiksell; herdruk New York: Dover (met een nieuw voorwoord), 2006.
• –––, 1971, "Ideeën en resultaten in bewijstheorie", in J. Fenstad (red.), Proceedings of the Second Scandinavian Logic Symposium, Amsterdam: Noord-Holland, pp. 235–308.
• Rathjen, M., 1995, “Recente vorderingen in ordinale analyse; Π ¹ ₂ -CA en aanverwante systemen ', 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 Erfassung der unendlichen Induktion in der Zahlentheorie", Mathematische Annalen, 122: 369–389.
• Skolem, T., 1920, "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathischer Sätze, nebst einem Theoreme über dichte Mengen," vertaald en herdrukt in Selected Works in Logic, JE Fenstad (red.), Oslo, Universitetsforlaget, 1970, pp. 103–136:
• Whitehead, AN en B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Secundaire literatuur

• Bernays, P., 1945, "Review: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul", The Journal of Symbolic Logic, 10 (4): 127–130.
• –––, 1965, "Betrachtungen zum Sequenzen-kalkul", in Bijdragen aan logica en methodologie ter ere van JM Bochenski, Amsterdam: Noord-Holland, pp. 1-44.
• –––, 1979, "Over het originele Gentzen-consistentiebewijs voor de getaltheorie", in J. Myhill et al. (red.), Intuitionism and Proof Theory, Amsterdam: Noord-Holland, pp. 409–417.
• Feferman, S., 2000, "Highlights in proof theory", in V. Hendricks et al. (redactie) 2000, 11-31.
• Hempel, C., 2000, "Een intellectuele autobiografie." In Science, Explanation en Rationality, red. J. Fetzer, blz. 3-35.
• Hendricks, V., et al. (red.), 2000, Proof Theory: History and Philosophical Significance, Dordrecht: Kluwer.
• Mancosu, P., 1999, "Tussen Berlijn en Wenen: de onmiddellijke ontvangst van Gödel's onvolledigheidsstellingen", History and Philosophy of Logic, 20: 33–45.
• von Plato, J., 2007, "In de schaduw van de stelling van Löwenheim-Skolem: vroege combinatorische analyses van wiskundige bewijzen", The Bulletin of Symbolic Logic, 13 (2): 189–225.
• –––, 2007, "Van Hilbert's programma tot Gentzen's programma", in de appendix, Menzler-Trott 2007.
• –––, 2009, "Gentzen's logic", in Handbook of the History and Philosophy of Logic (Volume 5), Amsterdam: Elsevier.
• –––, 2012, "Gentzen's proefsystemen: bijproducten in een geniaal programma", The Bulletin of Symbolic Logic, 18 (3): 313–367.
• Smorynski, C., 2007, "Hilbert's programma", in de appendix, Menzler-Trott 2007.
• Tait, W., 2005, "Gödel's herformulering van Gentzen's eerste consistentiebewijs voor rekenen: de no-counterexample-interpretatie", The Bulletin of Symbolic Logic, 11 (2): 225–238.
• Troelstra, A. en Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2e editie.

Academische hulpmiddelen

	Hoe deze vermelding te citeren.
	Bekijk een voorbeeld van de PDF-versie van dit item bij de Vrienden van de SEP Society.
	Zoek dit itemonderwerp op bij het Internet Philosophy Ontology Project (InPhO).
	Verbeterde bibliografie voor dit item op PhilPapers, met links naar de database.

Andere internetbronnen

[Neem contact op met de auteur voor suggesties.]