Vývoj Teorie Důkazů

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-08-25 04:38

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Vývoj teorie důkazů

První publikováno 16. dubna 2008; věcná revize po 13. října 2014

Vývoj teorie důkazů lze přirozeně rozdělit na: prehistorie pojmu důkaz ve staré logice a matematice; Fregeův objev, že matematické důkazy, a nejen návrhy matematiky, mohou (a měly) být zastoupeny v logickém systému; Hilbertova stará teorie axiomatického důkazu; selhání cílů Hilberta pomocí Gödelových teorémů neúplnosti; Gentzenova tvorba dvou hlavních typů logických systémů soudobé teorie důkazů, přirozeného dedukce a sekvenčního počtu (viz položka o automatickém uvažování); aplikace a rozšíření přirozené dedukce a sekvenčního počtu, až po výpočetní interpretaci přirozené dedukce a její souvislosti s informatikou.

• 1. Prehistorie pojmu důkaz
• 2. Hilbertova stará teorie axiomatického důkazu
• 3. Nevyhovatelnost konzistence
• 4. Přirozená dedukce a sekvenční počet
• 5. Konzistence aritmetiky a analýzy
• 6. Pozdější vývoj přirozené dedukce
• 7. Sekvenční počet: pozdější vývoj / aplikace
• 8. Cíle teorie důkazů

• Bibliografie

  • Texty na důkazní teorii
  • Původní díla a jejich dotisky
  • Sekundární literatura
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Prehistorie pojmu důkaz

Důkazní teorii lze popsat jako studium obecné struktury matematických důkazů a argumentů s demonstrační silou, s nimiž se logicky setkáváme. Myšlenka takových demonstračních argumentů, tj. Těch, jejichž závěr nevyhnutelně vyplývá z učiněných předpokladů, je v Aristotelově analytické posterioře ústřední: deduktivní věda je organizována kolem řady základních pojmů, o nichž se předpokládá, že jsou chápány bez dalšího vysvětlení, a řady základních pravd nebo axiomů, které jsou okamžitě považovány za pravdivé. Definované pojmy a věty jsou redukovány na tyto dva, druhé prostřednictvím důkazu. Aristotelovo vysvětlení důkazu jako demonstrativního argumentu se velmi dobře hodí ke struktuře starověké geometrie, která byla axiomatizována v Euklidu. Specifická forma Aristotelovy logiky, teorie syllogismu má místo toho, tak se zdá,téměř nic společného s důkazy v euklidovské geometrii. Tyto důkazy zůstaly intuitivní po více než dva tisíce let.

Před prací Frege v roce 1879 se zdá, že nikdo netvrdil, že by mohl existovat kompletní soubor důkazních principů, ve smyslu vyjádřeném Fregeem, když to napsal ve svém symbolickém jazyce,

vše, co je nezbytné pro správný závěr, je vyjádřeno v plném rozsahu, ale to, co není nutné, není obecně uvedeno; nic není ponecháno na hádání. (Begriffsschrift, str. 3)

(Jeden by mohl tvrdit, že Boole je výjimka, pokud jde o klasickou výrokovou logiku.) Fregeův krok vpřed byl rozhodující pro vývoj logické a základní studie. Kontrast s antiky je velký: Aristoteles dal vzorec pro kombinování argumentů, ale myšlenka konečné uzavřené sady pravidel byla, filozoficky, za sny kohokoli před Fregeem, s možnou výjimkou Leibniz.

Jak víme dnes, Fregeovy zásady dokazování jsou pro klasickou predikátovou logiku kompletní.

Kolem roku 1890 dal Giuseppe Peano formalizaci logického závěru s cílem reprezentovat formální důkazy v aritmetice. Jeho seminární práce Arithmetices principia, nova Methodo exposita, původně psaná latinou, je součástí anglického překladu ve sbírce Od Frege po Gödel (1967), kterou editoval Jean van Heijenoort. Editor bohužel nedokázal rozpoznat, co Peano udělal s formálním odvozením, a názor se rozšířil, že Peano formalizoval pouze jazyk logiky a aritmetiky, ne jeho principy důkazu. Pokud jsou Peanovy důkazy čteny s malou pečlivostí, ukázalo se, že se jedná o čistě formální derivace, které používají dva principy:

1. Axiomy naznačují jejich případy. Tyto důsledky lze zapsat jako řádky v důkazech.
2. Důsledek a jeho předchůdce znamenají společně následek.

Peano je velmi opatrný, aby na každém řádku svých derivací uvedl, jaký je formální důvod pro napsání řádku.

Russell převzal Fregeovu logiku, ale používal notaci a formální pravidla důkazu Peana, v papíru 1906 s titulem “teorie implikace.” Jeho formální mašinérie je úplně stejná jako u Peana. V pozdější práci Russell změnil axiomatický systém a systém Principia Mathematica (Whitehead a Russell 1910–13) se stal standardem. Russellova filosofická myšlenka, a zde následoval Fregeho, spočíval v tom, že axiomy vyjadřují základní logické pravdy a další logické pravdy jsou z nich odvozovány prostřednictvím modus ponens a univerzální generalizace, což byly dva principy, které Frege identifikoval. Matematika měla být zredukována na logiku, aby její důkazy byly prezentovány stejným axiomatickým vzorem.

Fregeův a Peano-Russellův přístup k logice se stal všeobecně přijímaným přístupem, zejména vlivem Hilberta a jeho spolupracovníků ve 20. letech 20. století. V 19. století byl Frege okrajovou postavou a dominantní byl algebraický přístup k logice, jako v Boole a zejména Ernst Schröder. Je zřejmé, že v této tradici existovalo dobré pochopení principů predikátové logiky, protože jak by jinak mohla existovat Löwenheimova-Skolemova věta? Skolem se dozvěděl o Fregeově logice prostřednictvím Principia Mathematica teprve poté, co vypracoval teorém ve svém příspěvku z roku 1920. První část tohoto článku, široce přečtená kvůli anglickému překladu ve Van Heijenoortově knize Od Frege do Gödel, označuje konec algebraické tradice logiky, která se tiše spojila s teorií mříže. Další části příspěvku obsahují pozoruhodný začátek analýzy důkazů v teorii mříže a v projektivní geometrii: Skolem považoval axiomy matematické teorie z ryze kombinatorického a formálního hlediska za prostředek pro tvorbu derivací vzorce z daného vzorce používané jako předpoklady. Začátkem 90. let bylo zjištěno, že část teorie mříže obsahuje řešení problému s rozhodnutím, nazvaného slovo problém pro volně generované mříže, jehož známé řešení pramení z roku 1988! Skolemova terminologie a notace v teorii mříže jsou terminologie Schrödera, a to je důvod, proč jeho práce byla ztracenou příležitostí pro teorii důkazů. Skolem považoval axiomy matematické teorie z čistě kombinatorického a formálního hlediska za prostředek k vytváření derivací vzorce z daných vzorců používaných jako předpoklady. Začátkem 90. let bylo zjištěno, že část teorie mříže obsahuje řešení problému s rozhodnutím, nazvaného slovo problém pro volně generované mříže, jehož známé řešení pramení z roku 1988! Skolemova terminologie a notace v teorii mříže jsou terminologie Schrödera, a to je důvod, proč jeho práce byla ztracenou příležitostí pro teorii důkazů. Skolem považoval axiomy matematické teorie z čistě kombinatorického a formálního hlediska za prostředek k vytváření derivací vzorce z daných vzorců používaných jako předpoklady. Začátkem 90. let bylo zjištěno, že část teorie mříže obsahuje řešení problému s rozhodnutím, nazvaného slovo problém pro volně generované mříže, jehož známé řešení pramení z roku 1988! Skolemova terminologie a notace v teorii mříže jsou terminologie Schrödera, a to je důvod, proč jeho práce byla ztracenou příležitostí pro teorii důkazů.nazval slovo problém pro volně generované mříže, jejichž známé řešení pramení z roku 1988! Skolemova terminologie a notace v teorii mříže jsou terminologie Schrödera, a to je důvod, proč jeho práce byla ztracenou příležitostí pro teorii důkazů.nazval slovo problém pro volně generované mříže, jejichž známé řešení pramení z roku 1988! Skolemova terminologie a notace v teorii mříže jsou terminologie Schrödera, a to je důvod, proč jeho práce byla ztracenou příležitostí pro teorii důkazů.

2. Hilbertova stará teorie axiomatického důkazu

Hilbertova kniha Grundlagen der Geometrie z roku 1899 připravila půdu pro základní základní problémy matematiky na počátku desetiletí 20. století. Tyto problémy můžeme vyjmenovat následovně:

1. Formalizace matematické teorie. To zahrnuje výběr jeho základních objektů a vztahů a výběr axiomů.
2. Doklad o konzistenci axiomů.
3. Otázka vzájemné nezávislosti a úplnosti axiomů.
4. Problém s rozhodnutím: Existuje metoda odpovědi na jakoukoli otázku, která by mohla být položena v rámci teorie?

Pokud jde o Hilbertovu geometrii, její pokus o formalizaci nedosáhl ideálu, k němuž se narodil. Hilbert našel mnohem důležitější pole, na které měla být použita jeho „metamatematika“, aritmetika a analýza. Základem byla studie čtyř základních problémů v axiomatických formulacích čisté logiky. Propoziční logika byla tedy formalizována, shledána konzistentní a úplnou a rozhodnutelnou. První výsledky o predikátové logice jsou z roku 1915, kdy Leopold Löwenheim přednesl svou verzi toho, co se později stalo predikátovou logikou Löwenheim-Skolemova věta (viz záznam o klasické logice). Rovněž řešil zvláštní případy rozhodovacího problému. Tento vývoj byl nezávislý na tradici Frege-Russella a byl založen na algebraickém přístupu k logice Ernsta Schrödera. Kolem roku 1920„Hilbertův“axiomatický přístup, jak se často říká, byl známý všem a ovládal logickou scénu; algebraický přístup se spojil téměř bez upozornění s teorií mříže. V roce 1928 byl v Hilbertově a Ackermannově Grundzüge der theoretischen Logik představen axiomatický formální systém predikátové logiky spolu s problémem jeho úplnosti. Ten byl vyřešen Gödelem v roce 1929, vyšel o rok později (Gödel 1930). Čtvrtý základní problém, rozhodovací problém pro predikátovou logiku, se ukázal jako negativní řešení v krátké knize církve v roce 1936 jako důsledek Gödelovy věty o neúplnosti.s Grundzüge der theoretischen Logik byl představen axiomatický formální systém predikátové logiky spolu s problémem jeho úplnosti. Ten byl vyřešen Gödelem v roce 1929, vyšel o rok později (Gödel 1930). Čtvrtý základní problém, rozhodovací problém pro predikátovou logiku, se ukázal jako negativní řešení v krátké knize církve v roce 1936 jako důsledek Gödelovy věty o neúplnosti.s Grundzüge der theoretischen Logik byl představen axiomatický formální systém predikátové logiky spolu s problémem jeho úplnosti. Ten byl vyřešen Gödelem v roce 1929, vyšel o rok později (Gödel 1930). Čtvrtý základní problém, rozhodovací problém pro predikátovou logiku, se ukázal jako negativní řešení v krátké knize církve v roce 1936 jako důsledek Gödelovy věty o neúplnosti.

Hilbert a jeho škola spolu s Bernaysem, Ackermannem a von Neumannem, stejně jako s mladým Herbrandem ve Francii, studovali ve druhé polovině dvacátých let metamathematické studium aritmetiky. Hilbert vyvinul metodu pro studium problémů s konzistencí nazvanou epsilon substituční metoda, která se zabývá kvantifikátory. Cítil, že nepřímé závěry s kvantifikátory v případech s nekonečnem předmětů byly klíčovým bodem důkazů konzistence a potřebovaly ospravedlnění. Řekněme, že pokud předpoklad, že všechna přirozená čísla mají vlastnost P, vede k nemožnosti, lze odvodit existenci čísla s opačnou vlastností ne-P. Ústředním problémem tedy bylo ospravedlnit použití klasické logiky v matematických důkazech, aritmetických důkazech. Ackermann byl velmi blízko řešení ke konci dvacátých let a optimismus vládl v Hilbertově škole. Potom se ovšem neočekávaně stalo, když Gödel dokázal nemožnost úplné formalizace elementární aritmetiky, a jak bylo brzy vyloženo, nemožnost prokázat konzistenci aritmetiky finitivními prostředky, jediní, kteří byli soudí podle „absolutně spolehlivé“podle Hilbert.

3. Nevyhovatelnost konzistence

Poté, co Gödel v září 1930 zveřejnil neúplnost aritmetiky, von Neumann zjistil, že konzistence aritmetiky bude mezi Gödelovými neověřitelnými tvrzeními. Bohužel, Gödel udělal stejný objev, takže von Neumann nikdy nezveřejnil svůj důkaz. Ve shodě s Gödelem však v jistém smyslu předpokládal nedůslednost konzistence aritmetiky, a tedy matematiky jako celku. Von Neumann byl klíčovou postavou v přijímání Gödelových výsledků: Na podzim roku 1930 přerušil přednášky o Hilbertově důkazní teorii v Berlíně, aby vysvětlil nové objevy. Tyto události vyvolaly mezi matematiky obrovské vzrušení, jak o tom svědčí svědectví Carla Hempela:

Absolvoval jsem tam kurz s von Neumannem, který se zabýval Hilbertovým pokusem dokázat konzistenci klasické matematiky pomocí finitivních prostředků. Vzpomínám si, že uprostřed kurzu přišel von Neumann za jeden den a oznámil, že právě dostal novinu od … Kurt Gödel, který ukázal, že cíle, které Hilbert měl na mysli a na které jsem slyšel Hilbertův kurz v Göttingenu, nemohl dosáhnout vůbec. Von Neumann proto upustil od snahy o toto téma a zbytek kurzu věnoval prezentaci Gödelových výsledků. Nález vyvolal obrovské vzrušení. (Hempel 2000, s. 13)

V letech 1932–33 našli Gödel a Gentzen nezávisle na sobě překlad z klasické peano aritmetiky do intuicionální Heyting aritmetiky. Konkrétně to ukazuje, že pokud je v prvním případě rozpor prokazatelný, je v druhém případě prokazatelný. Pak by konzistence intuicionistické aritmetiky zaručovala také konzistenci klasické aritmetiky. Tento výsledek byl překvapením: jak již bylo zmíněno, Hilbert si myslel, že „nepřímé“důkazy o nepřímé existenci budou součástí aritmetiky, která musí být zajištěna rozporem. Podle Gödelova a Gentzenova výsledku již intuicionistická aritmetika obsahovala principy, které přesahovaly finální uvažování. Dopis, který Gentzen napsal Heytingu dne 25. února 1933, shrnuje situaci takto:

Důkaz konzistence konečnými prostředky… zatím nebyl úspěšný, takže tohoto původního cíle Hilberta nebylo dosaženo. Pokud naopak člověk přiznává intuicionistické postavení jako bezpečný základ sám o sobě, tj. Jako důsledný, je můj výsledek zajištěn soulad klasické aritmetiky. Pokud by někdo chtěl vyhovět Hilbertovým požadavkům, úkolem by stále zůstalo ukázat intuitivní aritmetickou konzistentnost. To však není možné ani formálním aparátem klasické aritmetiky, na základě Gödelova výsledku v kombinaci s mým důkazem. Přesto mám sklon věřit, že důkaz konzistence pro intuicionistickou aritmetiku je z ještě zjevnější pozice možný a také žádoucí. (Menzler-Trott 2007, s. 38)

Posledním zmíněným byl cíl, který si Gentzen stanovil na začátku roku 1932, když v dopise svému starému učiteli Hellmuthovi Kneserovi napsal:

Jako svůj specifický úkol jsem si stanovil důkaz konzistence logického dedukce v aritmetice … Úloha se stává čistě matematickým problémem formalizací logické dedukce. Důkaz konzistence byl doposud prováděn pouze ve zvláštních případech, například aritmetice celých čísel bez pravidla úplné indukce. Chtěl bych v tomto bodě pokračovat dále a vyčistit alespoň aritmetiku s úplnou indukcí. Pracuji na tom téměř rok a doufám, že budu brzy dokončena, a pak tuto práci představím jako svou dizertační práci (s prof. Bernaysem). (Menzler-Trott 2007, s. 31)

4. Přirozená dedukce a sekvenční počet

Při provádění svého programu konzistence si Gentzen stanovil jako svůj první úkol analýzu ryze logické dedukce, která se později rozšíří na aritmetiku a analýzu. Ve své diplomové práci (1934–1935) Gentzen uvádí, že si za svůj úkol stanovil analýzu matematických důkazů, které se vyskytují v praxi. První pozorování je, že skutečné důkazy nejsou založeny na axiomech vyjádřených v logickém jazyce, jako v Hilbertově axiomatické teorii důkazů. Nejtypičtějším rysem je místo toho, že věty dělají svá tvrzení za určitých předpokladů. Předpoklady jsou analyzovány na části a závěr je také analyzován na části, dokud se tyto dvě analýzy nesetkají a není možné syntetizovat důkaz. Tato analýza vychází z toho, co Gentzen nazýval úvodními pravidly: dávají dostatečné podmínky pro odvození návrhu dané formy. Například,k odvození spojky A a B postačí odvodit spojky A a B odděleně. Závěr je dán formálně jako z pravidla

AB	& Já
A & B

Předpoklady jsou místo toho analyzovány na jejich složky prostřednictvím vylučovacích pravidel, která z velké části způsobují okamžité důsledky předpokladů. Například spojka použitá jako předpoklad může být rozložena na její složky, jako v pravidlech

A & B & E 1 A

A & B & E 2 B

Gentzen vyvinul a studoval systém přirozené dedukce během roku 1932 a do září 1932 dorazil na počet přirozených odpočtů (zkráceně ND), který je dnes standardní. Do této doby si všiml, že pokud po úvodu, řekněme derivaci A & B z A a B odděleně, následuje odpovídající eliminaci, řekněme derivaci A, vzorec A & B představuje lokální maximum, „ hillock “, což lze eliminovat. Takovéto kopce nazval také „objížďky“a to, co se nyní nazývá přeměnou objížďky, odstraňuje takové zbytečné páry kroků k zavedení a odstranění. Výsledkem kroků „normalizace“je odvození v „normální formě“.

Implikace je možná typičtější pro ND než spojení: pro odvození A ⊃ B, jeden dočasně předpokládá A, pak se pokusíme odvodit B. Pokud se to podaří, dočasný předpoklad se uzavře nebo „vypustí“, jakmile dojde k závěru k A ⊃ B, jako ve schematickém odvození

[A]
⋮
B	„Já
A ⊃ B

V opačném směru může být A ⊃ B vyloučeno, pokud byla nalezena derivace A, pro B pak lze uzavřít:

A ⊃ BA	⊃E
B

Pokud za pravidlem ⊃I následuje ⊃E, existuje neštandardnost, která je odstraněna přeměnou objížďky: odvození B (a to, co po něm následuje) se vytvoří odvozením menší premisy A vylučovacího pravidla. a odvození B z předpokladu A v úvodu. Tyto dva kusy se spojí do derivace B, která nemá vzorec objížďky A ⊃ B. V Gentzenově diplomové práci jsou všechny předpoklady nakonec zavřeny implikačními úvody, ale v současné době je možné považovat derivace, které nechávají sbírku vzorců, za otevřené předpoklady.

Když se podíváme na pravidla spojování a implikace, je třeba poznamenat, že premisy (vzorce bezprostředně nad inferenční linií) jsou podformuláři závěru v I-rulách, zatímco je to naopak v E-rulách. Gentzen si všiml, že v normálních derivacích je tato vlastnost jednotlivých kroků zděděna celou derivací v tom smyslu, že všechny vzorce jsou podformuláři závěru. Tento výsledek dal jako vedlejší produkt metodu rozhodování pro intuicionální výrokovou logiku. Dalším důsledkem byl syntaktický důkaz konzistence: je-li rozpor prokazatelný, lze prokázat cokoli, ale atomový vzorec, řekněme, nemá žádný důkaz: pokud má důkaz, má normální důkaz, ale žádné E-pravidla se nevztahují na atomový vzorec a žádný I-roule to ani nedokončí.

Gentzenova myšlenka měla rozšířit přirozenou dedukci na systém aritmetiky přidáním pravidla, které odpovídá principu úplné indukce. Konzistence by pak vyplynula z normalizace derivací a vlastnosti podformule. Začátkem roku 1933 si Gentzen uvědomil, že tato strategie důkazu neproběhne: indukční pravidlo je schématické a má nekonečno instancí, aniž by bylo vázáno na složitost indukčních vzorců. Bylo by nemožné omezit tyto vzorce předem, takže žádná vlastnost podformule nemůže obsahovat. Po tomto neúspěchu Gentzen ze svého raného rukopisu doslovně přeložil překlad z klasické na intuicionistickou aritmetiku a v březnu 1933 jej předložil jako referát, ale po vyslechnutí Gödelho zveřejnění výsledku ho stáhl.

Gentzen napsal, že nebyl schopen prokázat normalizační větu pro klasický systém ND. Vynalezl tedy další logický počet, který nazval sekvenční počet (Sequenzenkalkul, doslova „počet sekvencí“), a učinil z něj ústřední téma své práce. Název počtu pochází z reprezentace předpokladů derivace jako seznamu. Slovo „sequent“používané jako podstatné jméno je návrhem Kleeneho v jeho Úvod do metamatematiky (1952: 441), převzatým v mnoha jazycích ve formě čistě vynalezených slov.

Sekvenční počet, zkráceně SC, lze chápat jako formální reprezentaci vztahu derivability v přirozené dedukci. Sekvence se skládá ze seznamu Γ vzorců, šipky (v Gentzenu, později byly použity i jiné markery) a jednoho vzorce jako závěru. Seznam uvádí předpoklady, na nichž závěr závisí, v derivaci, v lokálním zápisu, kde jsou v ND nalezeny v listech derivačního stromu. Gentzen také zobecnil posloupnosti tak, že místo jednoho závěru mají za šipkou seznam možných případů. Tato novinka vedla k první uspokojivé formulaci důkazního systému pro klasickou logiku. Gentzenova pravidla SC pro spojování a implikaci jsou, s čárkami oddělujícími prvky v seznamech:

Spojení
Γ → Δ, A Γ → Δ, B R & Γ → Δ, A a B	A, Γ → Δ L & 1 A & B, Γ → Δ	B, Γ → Δ L & 2 A & B, Γ → Δ

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

Toto není místo, kde by se vysvětlovaly podrobnosti ND a SC (ale viz položka o automatickém zdůvodnění). Gentzen formuloval posledně jmenovaný, označený LK, takže poskytl intuicionální počet, označil LJ jako zvláštní případ, v němž je závěr nejvýše jedním případem. Poté důkladně dokázal analogii normalizační věty pro klasický počet, počet a důkaz, takže výsledek pro intuicionální počet byl zvláštním případem pro klasický počet. V LJ a LK, L znamená “logistic”, termín, kterým Gentzen odkazuje na axiomatické kalkulátory logiky Frege, Russell a Hilbert a Bernays. V takových kalkulech je každá linie v derivaci správná sama o sobě, tj. Logická pravda, odkud je termín. Písmena K a J pocházejí z německých slov klassisch a intuitionistisch.(Posledně jmenovaná by tedy měla být velká písmena „I“, ale starší němčina používá velká písmena „J“pro velká písmena „I“.)

Gentzen nazval analog normalizace podle nepředstavitelného jména Hauptsatze, „hlavní věta“. Standardní terminologie je dnes „cut eliminační věta“. Všechna logická pravidla SC mají vlastnost podformuláře ve velmi bezprostředním smyslu: každý vzorec v premisu je v závěru vzorec nebo podformulář. Pravidlo pro kombinování derivací, analogické s tím, které bylo vysvětleno výše, pro případ převodu objížďky v ND, se nazývá „řez“. V něm se vzorec A jeví jako případ v prvním předpokladu a jako předpoklad ve druhém předpokladu. Na závěr tento vzorec zmizel a předpoklady dvou předpokladů shromážděných společně:

Γ → AA, Δ → C	Střih
Γ, Δ → C

Řez je tedy jediným pravidlem, které způsobí, že vzorec v derivaci zmizí. Gentzen ukázal, že příklady pravidla řezu lze z derivací vyloučit jejich permutací směrem nahoru, dokud nedosáhnou bodů, ve kterých začíná derivace. V ND jsou počáteční body předpoklady, v SC jsou to „počáteční posloupnosti“tvaru A → A, ve kterém je předpokladový vzorec zároveň závěr. Řez s takovou sekvencí, jako je jeden předpoklad, má druhý předpoklad stejný jako závěr, a proto může být vypuštěn.

Po důkazu o eliminaci řezu Gentzen neměl žádný důkaz o normalizaci intuicionálního přirozeného dedukce. Dal první ručně psanou verzi své práce s podrobným důkazem normalizace (ekvivalentem asi 13 vytištěných stránek) Bernaysovi, ale zdá se, že si nikdy neuvědomil, co měl ve svých rukou. Důkaz mezi novinami Bernays v Curychu objevil současný autor v únoru 2005 a je nyní k dispozici v anglickém překladu (Gentzen 1933 [2008]).

5. Konzistence aritmetiky a analýzy

Po práci na ND a SC pro čistou logiku pokračoval Gentzen ve svém plánu prokazování konzistence aritmetiky. Výsledek byl připraven do prosince 1934. Co byl tento první důkaz, není podrobně známo. Dopis Bernaysovi z roku 1938 však naznačuje, že důkaz, který Gentzen napsal do léta 1935, nebyl tento originál, ale druhý důkaz (viz Menzler-Trott 2001, 79). Tento druhý důkaz byl kritizován Bernaysem a Gödelem, kteří o něm diskutovali během své atlantické plavby do Princetonu v září 1935. Gentzenova myšlenka v důkazu byla následující: za prvé, vezměte spojovací-negační-univerzální kvantifikační fragment přirozené dedukce jako logiku používanou v formalizace aritmetiky. Pak napište každou instanci pravidla tak, aby předpoklady a závěr měly otevřené předpoklady uvedené vlevo,se šipkou oddělující závěr, tak jako následky. Tato varianta ND se nyní nazývá ND ve stylu SC. Zvažte sekvenci Γ →C. Pokud je jeho závěr atomový vzorec, jedná se o rovnici mezi čísly. V nejhorším případě je to nepravdivé, proto zvažte seznam předpokladů. Pokud je jeden předpoklad spojkou, nahraďte jej spojkou dle vašeho výběru, pokud jde o univerzální kvantifikaci, instancí. Pokud jde o negaci ¬ A, nahraďte závěr písmenem A. Pokud je v kterékoli fázi tohoto „redukčního procesu“závěr sekvenčního postupu složený vzorec, musíte za možný závěr považovat jakýkoli spoj nebo jakoukoli instanci univerzální kvantifikace. V případě negace ¬ A jako závěru, přesuňte A k části předpokladů a nahraďte závěr 0 = 1. Gentzen ukazuje, že tímto způsobem za předpokladu, že daný sled je odvozitelný, je nalezena buď skutečná rovnice jako závěr, nebo jako falešná rovnice. Tím pádem,neexistují žádné odvozitelné posloupnosti se všemi předpoklady pravdivými a závěr nepravdivý.

Gödelovi a Bernaysovi nebylo jasné, co důkaz dokazuje; mysleli si, že předpokládá to, co je v intuicionální matematice známé jako věta fanoušků, ale toto bylo nepravdivé. Ukončení Gentzenovy redukční procedury může být namísto toho prokázáno indukcí na dobře založených stromech („bar indukce“), což je princip, který Gentzen použil na intuitivním základě. Výsledkem kritiky však bylo, že Gentzen bez dalšího přebral důkaz na třetí důkaz, který používá dnes slavný princip indukce transfinitu až do prvního epsilon-čísla. Tato indukce byla prezentována prostřednictvím kódování, které používalo desetinná čísla. Konkrétní výsledek změn pro Gentzenův článek publikovaný v roce 1936 však nebyl dobrý: logický počet byl změněn uprostřed článku o sedmdesáti lichých stránkách, které se staly velmi obtížně čitelné. Gentzen proto dal dalším, současným početem, čtvrtý důkaz konzistence aritmetiky v roce 1938 (v archivu Bernays v ETH Curych), tentokrát na základě klasického sekvenčního počtu LK z roku 1933. Jak již bylo zmíněno, korespondence s Bernaysem naznačuje, že tím se vrátil k důkazní metodě, která vedla k úspěchu v roce 1934. Použití indukce transfinitu je jasně vidět v papíru z roku 1938 prostřednictvím ordinální notace. Tyto indukční principy na Cantorově „druhé číselné třídě“jsou podrobně diskutovány v Hilbertově přednášce z roku 1925 „Über das Unendliche“(„Na nekonečno“, publikováno v roce 1926), na kterou se Gentzen odvolával.tentokrát na základě klasického sekvenčního počtu LK z roku 1933. Jak již bylo zmíněno, korespondence s Bernaysem naznačuje, že se tím vrátil k důkazní metodě, která vedla k úspěchu v roce 1934. Použití indukce transfinitu je jasně vidět v papíru z roku 1938 pořadová notace. Tyto indukční principy na Cantorově „druhé číselné třídě“jsou podrobně diskutovány v Hilbertově přednášce z roku 1925 „Über das Unendliche“(„Na nekonečno“, publikováno v roce 1926), na kterou se Gentzen odvolával.tentokrát na základě klasického sekvenčního počtu LK z roku 1933. Jak již bylo zmíněno, korespondence s Bernaysem naznačuje, že se tím vrátil k důkazní metodě, která vedla k úspěchu v roce 1934. Použití indukce transfinitu je jasně vidět v papíru z roku 1938 pořadová notace. Tyto indukční principy na Cantorově „druhé číselné třídě“jsou podrobně diskutovány v Hilbertově přednášce z roku 1925 „Über das Unendliche“(„Na nekonečno“, publikováno v roce 1926), na kterou se Gentzen odvolával.s 1925 přednáška “Über das Unendliche” (“On the nekonečný”, publikoval 1926), papír, ke kterému Gentzen zmínil.s 1925 přednáška “Über das Unendliche” (“On the nekonečný”, publikoval 1926), papír, ke kterému Gentzen zmínil.

Člověk by si myslel, že to bylo tak, ale Gentzen měl důvod předložit dokonce čtvrtý důkaz konzistence aritmetiky ve svém posledním příspěvku publikovaném v roce 1943, ale napsaném před válkou v roce 1939. Peano aritmetiku rozšířil prostřednictvím transfinitálních ordinálů a vytvořil transfinitová indukční princip je součástí tohoto rozšířeného počtu. Pak přímo ukázal, že indukce transfinitu až do prvního epsilon-čísla ε ₀ je v systému vyjádřitelná, ale nelze jej prokázat. Gödelova věta o neúplnosti je tedy prokázána zcela odlišným způsobem. Myšlenka důkazu je stručně následující: nejprve je stanoveno, co to znamená odvodit indukci transfinitu na konkrétní pořadové číslo v systému. Za druhé, pořadová čísla pod ε ₀jsou spojeny s derivacemi. Nazývají se „hodnoty“. Je tedy ukázáno, že pokud je indukce transfinitu na pořadové číslo odvozitelná, nemůže být toto pořadové číslo větší než hodnota derivace. Proto transfinitní indukce na ε ₀ není odvoditelné.

Protože princip indukce může být vyjádřen, ale neprokázán v běžné aritmetice, nachází se v Peano aritmetice vzorec, který nelze prokázat. Snadným důsledkem Gentzenovy verze věty o neúplnosti je konzistence Peano aritmetiky, protože v nekonzistentním systému by bylo možné prokázat cokoli. Na rozdíl od Gödelova „umělého“nevyzkoušitelného vzorce, které bylo získáno kódováním aritmetizovaného predikátu prokazatelnosti, je Gentzenův princip indukce transfinitu principem „běžné“matematiky.

Gentzenův poslední důkaz určoval „důkaz-teoretický ordinál“Peano aritmetiky, jmenovitě ten, který je potřebný k prokázání konzistence, s majetkem, který by nic méně nestačilo. Práce znamenala začátek teorie ordinálních důkazů. Byl to bezpochyby nejvýznamnější zakladatelský úspěch v aritmetice po Gödelových teorémech neúplnosti, ale stále je do značné míry neznámý - lze najít mnoho knih o Gödelových teorémech, které ani nezmiňují Gentzena.

Zdá se, že Gödel neměl v úmyslu poskytnout důkazy o aritmetice pomocí konzistence, ale stále konstruktivních principů. Na konci třicátých let, alespoň od roku 1938, si jako odpověď na Gentzenův důkaz vyvinul vlastní speciální interpretaci intuicionistické logiky a aritmetiky, která se stala známou jako interpretace dialektiky. K interpretaci důkazů intuicionistické aritmetiky používá kompatibilní funkcionály. Gödel publikoval interpretaci až v roce 1958, přestože ji uvedl na přednáškách v roce 1941. Není známo, zda o této záležitosti diskutoval, když se setkal s Gentzenem v prosinci 1939.

Na žádost Bernayse Ackermann v roce 1940 reprodukoval Gentzenův důkaz, pokud jde o Hilbertův epsilon-počet. Bylo překvapením, když publikace Gödelových sebraných článků vynesla na světovou „přednášku Zilsel“ve Vídni v roce 1938: nastíňuje tuto interpretaci jako přeformulování Gentzenova důkazu z roku 1935. (Tato záležitost je podrobně diskutována v Tait (2005), který sám pracoval na interpretaci bez protikladů a jejím rozšíření na analýzu v 60. letech.)

Dalším zjevným úkolem v teorii důkazů, po prokázání konzistence aritmetiky, bylo prokázat konzistenci analýzy, tj. Teorie reálných čísel. Gentzen dělal nějakou práci v tomto směru, ale byl pak přidělen k vojenské službě na podzim 1939. (Pozoroval a hlášil typ, číslo a směr letadel, které letěly nad městem Brunswick, dokud nebyl zasažen nervózním zhroucení na počátku roku 1942.) Od roku 1943 pokračoval v práci na analýze, ale obtíže spojené s tématem byly velké, stejně jako praktické životní potíže způsobené válkou. Analýza měla být formulována jako systém aritmetiky druhého řádu, což znamená, že kvantifikace je rozšířena na predikáty číselných teoretiků, nebo ekvivalentně na množiny přirozených čísel. Teorie čísel druhého řádu se používá v Gentzenově posledním článku,publikováno v roce 1943, ve kterém je stručně ukázáno, že princip indukce transfinitu do ε₀ je možné odvodit v teorii čísel druhého řádu.

Více než půl století prošlo bez konstruktivního důkazu konzistence úplné aritmetiky druhého řádu v dohledu. Mezi první průkopníky v této oblasti patřili Kurt Schütte a Gaisi Takeuti. První z nich v roce 1951 vytvořil infinitární sekvenční počet, který představil důkladným způsobem důkazy o konzistenci, druhý z nich místo toho použil tradičnější gentzenský počet (viz Takeuti 1987).

V současném výzkumu teorie důkazů aritmetiky druhého řádu se studuje tzv. Subsystémy aritmetiky druhého řádu. Nejsilnější výsledky jako dnes jsou ve velmi stručném přehledu následující: nechť X se pohybuje nad číselně-teoretickými predikáty. Vzorec jako X (x) uvádí, že x má vlastnost vyjádřenou X. Nyní můžeme použít logiku prvního a druhého řádu k vytvoření složených vzorců, jako je ∀ X (X x ∨ ¬ X x). Soubor přirozených čísel, pro který platí taková formule s jedním univerzálním kvantifikátorem druhého řádu, se nazývá Π11-sada (v tomto případě celá přirozená čísla). Obecněji řečeno, axiom porozumění má tvar ∃ X ∀ x (X x ↔ B (x)). Pokud vzorec B nemá žádné kvantifikátory druhého řádu, axiom dává to, čemu se říká aritmetické porozumění nebo ACA. Jestliže B může mít tvar ∀ Y ∃ ZC (x) bez dalších kvantifikátorů druhého řádu, získá se zvláštní případ Π12-porozumění. Důkazy o shodě pro subsystém aritmetiky druhého řádu s porozuměním Π12 poskytli Toshiyasu Arai a Michael Rathjen v polovině 90. let. (viz Rathjen 1995 pro tento vývoj).

6. Pozdější vývoj přirozené dedukce

V době, kdy Gentzen vypracoval svůj systém přirozené dedukce, vyvíjel Stanislaw Jaskowski také logický systém pro uvažování s předpoklady. Vzorce v derivacích jsou uspořádány v lineární posloupnosti, ale Jaskowského papír z roku 1934 zůstal fragmentární a bez podstatných výsledků, jako je vlastnost subformule. Lineární varianta přirozené dedukce je sledována v mnoha pedagogických výstavách elementární logiky (někdy nazývaných „Fitchovy systémy“). Gentzen našel Jaskowského dílo do června 1936, kdy byli oba v Münsteru, a jeho lineární uspořádání vzorců považovalo za zlepšení, „osvobození od svěrací kazajky stromové formy“, do podoby, která odráží „linearitu myšlení“(první z nepublikované poznámky, poslední z Gentzenovy práce).

Systém přirozené dedukce spočíval většinou v klidu po dobu asi třiceti let, až do té doby, co obdržela tezi Dag Prawitze z roku 1965, Přírodní dedukce: Proof-teoretická studie. Pořadí, ve kterém Prawitz představil normalizační větu, se lišilo od pořadí v Gentzenově rukopisu z rané práce. Prawitz dal nejprve normalizační teorém a vlastnost subformula pro systém přirozené dedukce pro klasickou logiku. Tento systém neobsahuje žádné disjunkce ani existenci. Ve druhé fázi zvažoval intuicionální přirozené dedukce pro celý jazyk predikátové logiky a redukoval její normalizaci na odstranění konvertibility objížďky jako ve fragmentu klasické logiky. Když v roce 2005 vyšel najevo Gentzenův důkaz normalizace, Prawitz v rozhovoru se současným autorem řekl, že je jasné, že Gentzen věděl výsledek,protože poznámky v tištěné tezi jsou tak sugestivní.

V pozdních šedesátých létech, silná normalizace se stala problémem: Prawitz, používat předchozí práci Williama Taita a Jean-Yves Girard, dokázal v roce 1971 že non-normalities v derivaci mohou být přeměněny v nějakém pořadí, s ukončujícím normalizačním procesem a jedinečným výsledkem je normální odvození. Zdá se, že Gentzen si toho nevšiml, ale zdá se, že si spíše myslel opak, selháním této vlastnosti pro odstranění škrtů v sekvenčním počtu.

Přibližně ve stejnou dobu, kdy byla studována silná normalizace, se objevila Curry-Howardova korespondence. Curry pozoroval ve své práci na kombinatorické logice na konci padesátých let analogii mezi eliminací implikací v přirozené dedukci a funkční aplikaci (Curry a Feys 1958). Myšlenka byla stejně stará jako intuicionální logika: „vysvětlením BHK“spojek a kvantifikátorů (pro Brouwer-Heyting-Kolmogorov) vyjadřují formy výroků v intuicionistické logice předpisy, jak tyto výroky prokázat: spojení A & B se prokazuje samostatným prokázáním A a B, disjunkcí A ∨ B prokázáním jednoho z A a B a implikací A ⊃ B ukázáním, jak převést jakýkoli důkaz A na nějaký důkaz B a tak dále. Tato vysvětlení se velmi blíží úvodním pravidlům přirozeného odpočtu,ale zůstává neznámo, jaký je jejich účinek na Gentzenovu myšlenku.

The Curry-Howard korespondence, z papíru Williama Howarda z roku 1969, ale publikovaného teprve v roce 1980, je založena na principu „vzorce-jako-typy“, nebo v jiném žargonu, na principu „návrhy-jako-sady“. Návrh je považován za soubor důkazů. Pravda výroku odpovídá nevyplnění sady. Důkazy A ⊃ B jsou nyní funkcemi od (důkazů) A do (důkazů) B a A ⊃ B samotného souboru takových funkcí. Pokud tedy f: A ⊃ B a a: A, pak funkční aplikace dá f (a): B. Zpět, odpovídající zavedení implikace, je zachycen principem funkční abstrakce A-kalkulu Alonzo Church.

Curry-Howardova korespondence učinila intuicionální přirozenou dedukci součástí učebních osnov počítačové vědy: dává výpočetní sémantiku pro intuicionální logiku, ve které se výpočty a provádění programů obecně provádějí prostřednictvím normalizace. Důkazem implikace A ⊃ B je program, který převádí data typu A na výstup typu B. Konstrukce objektu (důkaz, funkce, program) f typu A ⊃ B končí abstrakcí. Když je objekt a typu A přiváděn do f jako argument, výsledný výraz není normální, ale má formu, která odpovídá úvodu následovanému eliminací. Normalizace je nyní stejná jako provedení programu f. Použití intuicionistické logiky není spojeno s žádnou intuicionistickou filozofií matematiky,ale je to jen systematická záruka za ukončení provádění počítačových programů.

7. Sekvenční počet: pozdější vývoj / aplikace

Gentzenova disertační práce znamenala zrození teorie strukturálních důkazů, na rozdíl od staré teorie axiomatických důkazů Hilberta. Oiva Ketonen ve své doktorské práci z roku 1944 učinil pozoruhodný krok vpřed ve vývoji systémů sekvenčního počtu. Ketonen, student matematiky a filosofie v Helsinkách, odešel v roce 1938 do Göttingenu studovat důkazní teorii a Gentzen byl nejblíže studentovi, který ten druhý měl. Zdá se, že toto spojení bylo vytvořeno profesorem filozofie Ketonen Eino Kaila, který se setkal s Gentzenem v roce 1936 v Münsteru. Ketonen si později vzpomněl, že Gentzen je „sympatický mladý muž několika slov“, který mu představil důkazně-teoretické systémy a výsledky. Ketonen 'nejznámějším objevem je sekvenční počet pro klasickou výrokovou logiku, jejíž logická pravidla jsou všechna invertibilní, což znamená, že kdykoli je sekvenční forma ve formě, která odpovídá závěru logického pravidla, odpovídající předpoklady, jednoznačně definované z daného sekvenčního a pravidlo, jsou také odvozitelné. Zpět je okamžitý (stačí použít pravidlo). Například pravidla L & a L⊃ jsou upravena na

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

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

Existuje pouze jedno levé pravidlo pro spojení (a dvojí pouze jedno pravé pravidlo pro disjunkce). Pravidlo pro implikaci vlevo má tzv. „Sdílené kontexty“: předpoklady a případy v závěru, s výjimkou vzorce s pojivem, se identicky opakují v obou předpokladech. Ketonenova myšlenka měla definovat systém vyhledávání důkazů: jeden začíná od dané sekvence, která má být odvozena, vybere v ní vzorec a zapíše předpoklady pravidla, které může danou sekvenci uzavřít. Nevratitelností je otázka derivovatelnosti nahrazena jednou nebo dvěma ekvivalentními otázkami derivovatelnosti na jednodušších sekvencích. Nová pravidla jsou nezbytná k zajištění jedinečně definovaných předpokladů v takovém rozkladu typu root-first.

Ketonenův důkaz invertibility logických pravidel jeho sekvenčního počtu použil strukturální pravidlo střihu. Později Kurt Schütte (1950) a Haskell Curry (1963) poskytli přímé důkazy o invertibilitě, ta druhá s výslovným výsledkem, že inverze udržují výšku: pokud je daný sled odvozitelný ve většině n kroků, předpokládá se pravidlo, které může usuzují, že sekvence má také derivaci ve většině n kroků.

Kolik Ketonenovy práce pramení z podnětů Gentzena zůstává neznámé, protože nebyla nalezena žádná korespondence. Ketonen v předmluvě své práce uvádí, že „Dr. G. Gentzen z Göttingenu mě nasměroval k problémové oblasti této práce. “Diplomová práce byla Ketoneniným originálním dílem v logice, zachráněným před zapomenutím dlouhým recenzím, který o něm Bernays psal pro The Journal of Symbolic Logic v roce 1945.

Jeden člověk, který znal Ketonenův počet na konci 40. let, byl Evert Beth. Když Beth později, v roce 1955, představil svůj známý tabákový počet, zdá se, že zapomněl na původ tabákového kalkulu jako naformulování Ketonena, ale místo toho odkazuje na Kleenův vlivný úvod do metamatematiky z roku 1952. Kleene vzal nahoru Ketonenův počet z Bernaysovy recenze a také léčil intuicionální sekvenční počet, ve kterém je nezaměnitelnost omezenější než v klasickém počtu. S Kleeninou knihou se Gentzenovy sekvenční kameny staly obecně známými a přístupnými.

Kleeneova práce z počátku padesátých let byla také průkopníkem pozoruhodného vývoje v sekvenčním počtu, a to klasických a intuitivních kamenů „bez kontrakce“, které dnes označují G3c a G3i. Tyto kameny mají tu vlastnost, že žádné z Gentzenových původních „strukturálních pravidel“není potřeba. Pravidlo „oslabení“umožňuje doplnění nadbytečných případů a předpokladů a pravidlo „smrštění“vymazání jedné kopie vzorce, pokud byly dvě v seznamu, jako v

Oslabení		Kontrakce
Γ → Δ Wk A, Γ → Δ		A, A, Γ → Δ Ctr A, Γ → Δ

Analogická pravidla umožňují oslabení a kontrakci v pravých, následných částech posloupnosti. Oslabení je provedeno odstranitelným pravidlem tím, že počáteční sekvence mají tvar A, Γ → Δ, A místo Gentzenova A → A. Kontrakce je rovněž odstranitelná vhodnou formulací pravidel. Import je, že při hledání kořenových důkazů nemusí být použita žádná pravidla, která by vedla k duplicitě vzorce. Bez tohoto výsledku by nenastalo ukončení vyšetřování důkazů.

Klasický počet má výše zmíněnou vlastnost výškové zachování invertovatelnosti svých logických pravidel. Albert Dragalin na konci 70. let zdokonalil počet, ve kterém jsou strukturální pravidla navíc „přípustná pro zachování výšky“, což znamená, že kdykoli je předpoklad takového pravidla odvozitelný, lze jej odvodit bez tohoto pravidla a nanejvýš se stejným velikost (maximální počet instancí pravidla v derivační větvi) derivace. Tato vlastnost má hluboké účinky na odstranění řezu: při permutaci řezu musel Gentzen obnovit původní kontexty (Γ a Δ) prostřednictvím oslabení a kontrakcí. S přípustností těchto pravidel pro zachování výšky se velikost derivace při použití pravidel nezvětší. Dragalin dal také intuicionální multisukcedentní počet se stejným typem přípustnosti strukturálních pravidel. Troelstra nakonec v učebnici Základní teorie důkazů (2000, 1. vyd. 1996) vydal jednoúspěšný intuicionistický počet s výškovou ochranou přípustnosti oslabení a kontrakce. Sekvenční kameny bez kontrakce jsou výkonnými nástroji pro analýzu formálních derivací. Mnoho obtížných výsledků výzkumu v logice se stává pouhým cvičením prostřednictvím kontroly nad strukturou důkazů, které umožňují výpočty G3. Sekvenční kameny bez kontrakce jsou výkonnými nástroji pro analýzu formálních derivací. Mnoho obtížných výsledků výzkumu v logice se stává pouhým cvičením prostřednictvím kontroly nad strukturou důkazů, které umožňují výpočty G3. Sekvenční kameny bez kontrakce jsou výkonnými nástroji pro analýzu formálních derivací. Mnoho obtížných výsledků výzkumu v logice se stává pouhým cvičením prostřednictvím kontroly nad strukturou důkazů, které umožňují výpočty G3.

Nejčasnější aplikace sekvenčního počtu v matematice byla v důkazní teorii aritmetiky, v Gentzenově práci a rozhodujícím způsobem v roce 1938 důkaz konzistence aritmetiky. Troelstra zmiňuje Ketonenovu práci jako

časná analýza důkazů cutfree v Gentzenových kalkulích s axiómy; ale zvažuje formu bezrozměrných derivací v čistém počtu, kde jsou axiomy přítomny v antecedentu odvozených sekvencí. (Troelstra a Schwichtenberg 2000: 142)

Axiomy, které Ketonen zvažuje, jsou ty, které mají projekční a afinní geometrii. Ketonen chtěl formulovat Skolemova formální pravidla důkazu v sekvenčním počtu. Ketonenova práce však byla známa většinou pouze prostřednictvím Bernaysovy revize a podrobně zde byla vysvětlena pouze logická část o sekvenčním počtu.

Druhým způsobem, jak aplikovat sekvenční počet, je nechat posloupnosti, které zahajují derivační větve, mít kromě počátečních posloupností také tvar → A, ve kterém A je axiom nebo instance univerzálního axiomu. Nyní, Gentzenovým „rozšířeným Hauptsatzem“, mohou být redukce derivací permutovány až do okamžiku, kdy jeden z jejich předpokladů je axiom, ale tyto škrty na axiómech zůstanou. Další novější metodou je převést axiomy do zvláštních pravidel, která se přidávají k logickým pravidlům sekvenčního počtu, s úplnou eliminací řezů (jak je vysvětleno v Negri a von Plato 2001, kapitola 6, a v Troelstra a Schwichtenberg's 2000, kapitola 4.7)..

8. Cíle teorie důkazů

Do jaké míry dosáhla teorie důkazů svých původních cílů? Pro Hilberta byly cílem úplné objasnění základních problémů prostřednictvím konečných důkazů o shodě atd. Cílů, u nichž teorie důkazů selhala. Hilbert se ve svém programu nezajímal o studium matematických důkazů samých o sobě, ale pouze o objasnění ústředních základních problémů (a pak na ně zapomněl). Nedávno nalezená poznámka Hilberta dává jiný obrázek: poznámka uvádí, že Hilbert chtěl přidat jako 24. a poslední problém ve svém slavném pařížském seznamu otevřených matematických problémů z roku 1900 vývoj „teorie důkazních metod v matematice“. To bylo dříve, než se objevil jeho metamatematický program pro vývoj teorie důkazů.

Pro Gentzena byly cílem společně s Hilbertovými pochopit strukturu matematických důkazů. Tento program byl naprostým úspěchem, pokud jde o čistou logiku a aritmetiku. Zejména metody sekvenčního počtu umožňují analýzu důkazů s hlubokými výsledky. Velký cíl teorie důkazů, důkaz konzistence analýzy jako v Hilbertově druhém pařížském problému, nebyl proveden, ale není vyloučen.

Nějaké chápání pojmu důkaz je nezbytné pro každého matematika, ne-li pro nic jiného, pak alespoň pro přenositelnost matematických výsledků: publikace spočívá na pochopení, že důkazy lze učinit tak explicitní, aby byly běžně kontrolovatelné z hlediska správnosti. Teorie důkazů se však dosud nestala praktickým nástrojem pro pracujícího matematika; aplikace v matematice byly spíše ojedinělými případy. Nedávná práce na formalizaci matematických důkazů pomocí počítačových systémů, zvaných editory důkazů, může tento obrázek postupně změnit.

Důkazová teorie vytvořila nové cíle mimo tradiční matematiku, zejména v souvislosti s informatikou. Témata, jako je ověřování správnosti počítačových programů, jsou výsledkem teorie důkazů. Přirozená dedukce vedla k Curryho-Howardově korespondenci ak souvislostem s funkčním programováním. Sekvenční počet se často používá v systémech automatického vyhledávání důkazů, stejně jako v logickém programování.

Bibliografie

Texty na důkazní teorii

• Buss, Sam (ed.), 1998, Handbook of Proof Theory, Amsterdam: Elsevier.
• Negri, S. a J. von Plato, 2001, Structure Proof Theory, Cambridge: Cambridge University Press.
• von Plato, J., 2013, Elements of Logical Reasoning, Cambridge: Cambridge University Press.
• Takeuti, G., 1987, Proof Theory, Amsterdam: North-Holland, 2. vydání.
• Troelstra, A. a H. Schwichtenberg, 2000, Základní teorie důkazů, Cambridge: Cambridge University Press, 2. vydání.

Původní díla a jejich dotisky

• Ackermann, W. 1940, „Zur Widerspruchsfreiheit der Zahlentheorie,“Mathematische Annalen, 117: 162–194.
• Beth, E., 1955, sémantická entealment a formální derivabilita (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe reeks, deel 18, č. 13), Amsterdam: North-Holland.
• Church, A., 1936, „Poznámka k Entscheidungsproblemu“, Journal of Symbolic Logic, 1: 40–41.
• Curry, H. a Feys, R., 1958. Combinatory Logic. (Study in Logic and the Foundations of Mathematics, svazek I), 1. vydání, Amsterdam: North-Holland.
• Curry, H., 1963, základy matematické logiky, New York: McGraw-Hill; dotisk New York: Dover, 1977.
• Dragalin, A., 1988, Mathematical Intuitionism: Úvod do teorie důkazů, Providence, RI: American Mathematical Society.
• Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Výzkumy do logické inference), Ph. D. disertační práce, Universität Göttingen. Publikováno v Gentzenu 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. Překlad v 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. Překlad v Gentzen 1969: 287–308.
• Gentzen, G., 1969, The Collected Papers of Gerhard Gentzen, ed. M. Szabo, Amsterdam: Severní Holandsko.
• Gentzen, G., 2008, „Normalizace derivací,“Bulletin symbolické logiky, 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 (svazky I – V), S. Feferman a kol. (eds.), Oxford: Oxford University Press.
• van Heijenoort, J., 1967, Z Frege do Gödel, Cambridge, MA: Harvard University Press.
• Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: BG Teubner.
• Hilbert, D., 1926, „Über das Unendliche“(„Na nekonečno“), Mathematische Annalen, 95: 161–190. [Přednáška přednesená Münsterovi, 4. června 1925.]
• Hilbert, D., a Ackermann, W., 1928, Grundzüge der theoretischen Logik, Berlín: Springer.
• Hilbert, D., 1931, „Die Grundlegung der elementaren Zahlenlehre“, Mathematische Annalen, 104: 484–494.
• Howard, W., 1980 [1969], „Koncepty pojmů konstrukce podle typu“, v J. Seldin a J. Hindley (ed.), HB Curry: Eseje o kombinované logice, Lambda počet a formalismus, Londýn, New York: Academic Press, s. 480–490.
• Jaskowski, S., 1934, „O pravidlech předpokladu ve formální logice“, v S. McCall (ed.), Polská logika 1920–1939, Oxford: Clarendon Press, 1967, s. 232–258.
• Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae scientiarum fennicae (Ser. AI 23), Helsinky.
• Kleene, S., 1952, Úvod do metamatematiky, Amsterdam: Severní Holandsko.
• Kreisel, G., 1951, „K interpretaci finitistických důkazů: část 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, Berlín: Birkhäuser Verlag.
• Menzler-Trott, E., 2007, Logic's Lost Genius: Život a dílo Gerharda Gentzena, Providence, RI: American Mathematical Society.
• Prawitz, D., 1965, Natural Deduction: Proof-Theoret Study, Stockholm: Almqvist & Wiksell; dotisk New York: Dover (s novou předmluvou), 2006.
• –––, 1971, „Nápady a výsledky v teorii důkazů“, v J. Fenstad (ed.), Sborník z druhého skandinávského logického sympozia, Amsterdam: North-Holland, s. 235–308.
• Rathjen, M., 1995, „Poslední pokroky v ordinální analýze; Π ¹ ₂ -CA a související systémy, “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 Indukce in der Zahlentheorie,“Mathematische Annalen, 122: 369–389.
• Skolem, T., 1920, „Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit Mathatischer Sätze, nebst einem Theoreme über dichte Mengen,“přeložil a přetiskl ve vybraných dílech v logice, JE Fenstad (ed.), Oslo, Universitetsforlaget, 1970, Oslo, Universitetsforlaget, 1970, str. 103–136:
• Whitehead, AN a B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Sekundární literatura

• Bernays, P., 1945, „Recenze: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul,“The Journal of Symbolic Logic, 10 (4): 127–130.
• –––, 1965, „Betrachtungen zum Sequenzen-kalkul,“v příspěvcích k logice a metodologii na počest JM Bochenského, Amsterdam: North-Holland, s. 1–44.
• –––, 1979, „O původním Gentzenově důkazu konzistence teorie čísel,“v J. Myhill et al. (eds.), Intuitionism and Proof Theory, Amsterdam: North-Holland, s. 409–417.
• Feferman, S., 2000, „Highlights in the proof proof“, V. Hendricks et al. (eds.) 2000, 11–31.
• Hempel, C., 2000, „Intelektuální autobiografie“. V Science, Explanation and Rationality, ed. J. Fetzer, str. 3-35.
• Hendricks, V., et al. (eds.), 2000, Proof Theory: History and Philosophical Význam, Dordrecht: Kluwer.
• Mancosu, P., 1999, „Mezi Berlínem a Vídní: Okamžité přijetí Gödelových teorémů neúplnosti,“Historie a filozofie logiky, 20: 33–45.
• von Plato, J., 2007, „Ve stínu Löwenheimovy-Skolemovy věty: časné kombinatorické analýzy matematických důkazů,“Bulletin symbolické logiky, 13 (2): 189–225.
• ––– 2007, „Od Hilbertovy po Gentzenův program,“v příloze, Menzler-Trott 2007.
• –––, 2009, „Gentzenova logika“, v Příručce dějin a filozofie logiky (svazek 5), Amsterdam: Elsevier.
• ––– 2012, „Gentzenovy důkazní systémy: vedlejší produkty v geniálním programu“, Bulletin of Symbolic Logic, 18 (3): 313–367.
• Smorynski, C., 2007, „Hilbertův program“, v dodatku, Menzler-Trott 2007.
• Tait, W., 2005, „Gödelova reformulace Gentzenova prvního důkazu konzistence pro aritmetiku: interpretace bez protikladů,“Bulletin symbolické logiky, 11 (2): 225–238.
• Troelstra, A. a Schwichtenberg, H., 2000, Základní teorie důkazů, Cambridge: Cambridge University Press, 2. vydání.

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

[Obraťte se na autora s návrhy.]