Tõestusteooria Arendamine

2023 Autor: Noah Black | [email protected]. Viimati modifitseeritud: 2023-05-24 11:17

Sisenemise navigeerimine

• Sissesõidu sisu
• Bibliograafia
• Akadeemilised tööriistad
• Sõprade PDF-i eelvaade
• Teave autori ja tsitaadi kohta
• Tagasi üles

Tõestusteooria arendamine

Esmakordselt avaldatud K, 16. aprill 2008; sisuline redaktsioon esmaspäeval 13. oktoobril 2014

Areng tõestusteooria võib loomulikult jagada: esiajalugu mõiste tõend Vana loogika ja matemaatika; Frege'i avastus, et matemaatilisi tõestusi ja mitte ainult matemaatika väiteid saab (ja peaks) esindama loogilises süsteemis; Hilberti vana aksioomaatilise tõestuse teooria; Hilberti eesmärkide nurjumine Gödeli puudulikkuse teooriate kaudu; Gentzen on loonud tänapäevase tõestusteooria kaks peamist loogikasüsteemi tüüpi: naturaalne deduktsioon ja järjestikune arvutus (vt automatiseeritud mõttekäiku käsitlevat sissekannet); loodusliku deduktsiooni ja järjestikuse arvutuse rakendused ja laiendid kuni loodusliku deduktsiooni arvutusliku tõlgendamiseni ja selle seosteni arvutiteadusega.

• 1. Tõestuse mõiste eelajalugu
• 2. Hilberti vana aksomaatiline tõestusteooria
• 3. Järjepidevuse tõestamatus
• 4. Naturaalne deduktsioon ja järjestikune arvutus
• 5. Aritmeetika ja analüüsi järjepidevus
• 6. Loodusliku deduktsiooni hilisemad arengud
• 7. Järjestikune arvutus: hilisemad arengud / rakendused
• 8. Tõestusteooria eesmärgid

• Bibliograafia

  • Tekstid tõestusteooria kohta
  • Originaalteosed ja nende kordustrükid
  • Teisene kirjandus
• Akadeemilised tööriistad
• Muud Interneti-ressursid
• Seotud kirjed

1. Tõestuse mõiste eelajalugu

Tõestusteooriat võib kirjeldada kui matemaatiliste tõendite üldise struktuuri ja loogikas esinevate demonstreerimisjõuga argumentide uurimist. Aristotelese Analytica Posteriora keskmes on selliste demonstratiivsete argumentide, st nende, mille järeldus tingimata tuleneb tehtud eeldustest, idee: deduktiivne teadus on korraldatud paljude põhimõistete ümber, mida eeldatakse mõistvat ilma täiendava selgituseta, ja mitmeid põhitõdedest või aksioomidest, mida peetakse kohe tõeseks. Määratletud mõisted ja teoreemid taandatakse nendele kahele, viimane tõendusmaterjali kaudu. Aristotelese tõestusmaterjal kui demonstreeriv argument sobib väga hästi iidse geomeetria struktuuriga, nagu see oli Euclidis aksiomaatiseeritud. Aristotelese loogika spetsiifilisel kujul on sillogismi teooria oma, selle asemel näib,peaaegu midagi pistmist eukleidilise geomeetria tõenditega. Need tõendid püsisid intuitiivselt enam kui kaks tuhat aastat.

Enne Frege tööd 1879. aastal ei paistnud keegi olevat väitnud, et võiks olemas olla täielik tõenduspõhimõtete tähendus, mida Frege väljendas oma sümboolses keeles kirjutades,

kõik, mis on vajalik korrektsete järelduste tegemiseks, on väljendatud täies mahus, kuid mida pole vaja, seda üldjuhul ei näidata; midagi ei jää arvamiseks. (Begriffsschrift, lk 3)

(Võib väita, et Boole on klassikalise propositsioonilise loogika osas erand.) Frege samm edasi oli loogika ja alusuuringute arendamisel määrav. Vastupidine iidsetele on suurepärane: Aristoteles andis mustri argumentide ühendamiseks, kuid lõpliku suletud reeglistiku idee oli filosoofiliselt filosoofilises mõttes kaugemale kellegi unistustest enne Frege'i, võimaliku erandiga Leibniz.

Nagu me täna teame, on Frege tõenduspõhimõtted klassikalise predikaatloogika jaoks täielikud.

Umbes 1890. aastal vormistas Giuseppe Peano loogilised järeldused, eesmärgiga esitada formaalselt tõestatud aritmeetika. Tema algupäraselt ladina keeles kirjutatud algdokument Arithmetices principia, nova metodopositita on lisatud ingliskeelse tõlkena kogumikus Frege-Gödel (1967), mille redigeeris Jean van Heijenoort. Kahjuks ei suutnud toimetaja aru saada, mida Peano tegi ametlike järeldustega, ja levis arvamus, et Peano vormistas ainult loogika ja aritmeetika keele, mitte selle tõestamispõhimõtted. Kui Peano tõestusi loetakse isegi vähese hoolikusega, selgub, et need on puhtalt formaalsed tuletised, mis kasutavad kahte põhimõtet:

1. Aksioomid viitavad nende juhtumitele. Selliseid mõjusid saab tõenditesse kirjutada ridadena.
2. Mõju ja selle eelnev tähendavad koos järeldavat.

Peano loetleb väga hoolikalt oma tuletiste igal real, milline on rea kirjutamise ametlik alus.

Russell lähtus Frege loogikast, kuid kasutas Peano nootide ja ametlike tõendite esitamise reegleid 1906. aasta paberis pealkirjaga “Kaasamise teooria”. Selle ametlik masin on täpselt sama mis Peano oma. Hilisemas töös muutis Russell aksioomaatilist süsteemi ja Principia Mathematica (Whitehead ja Russell 1910–13) süsteem muutus standardseks. Russelli filosoofiline idee, mille ta järgnes Frege'ile, oli see, et aksioomid väljendavad loogilisi põhitõdesid ja muud loogilised tõed tuletatakse neist modus ponensi ja universaalse üldistamise kaudu, mille Frege oli kindlaks teinud kaks põhimõtet. Matemaatika pidi taandama loogikale, nii et selle tõestused oleksid esitatud sama aksomaatiliselt.

Frege ja Peano-Russelli lähenemisviis loogikale sai üldtunnustatud lähenemiseks, eriti Hilberti ja tema kaastöötajate mõjutamise kaudu 1920. aastatel. 19. sajandil oli Frege marginaalne kuju ja domineeriv oli algebraline lähenemine loogikale, nagu Boole ja eriti Ernst Schröderi puhul. On selge, et selles traditsioonis oli predikaatloogika põhimõtetest hästi aru saadud, kuidas oleks muidu võinud olla Löwenheim-Skolemi teoreem? Skolem sai Frege loogikast Principia Mathematica kaudu teada alles pärast seda, kui oli oma teoses 1920. aastal välja töötanud. Selle artikli esimene osa, mida on laialdaselt loetud Van Heijenoorti teose „Frege to Gödel” ingliskeelse tõlke tõttu, tähistab algebralise teksti lõppu. loogika traditsioon, mis sulandus vaikselt võreteooriasse. Teised paberilõigud sisaldavad tähelepanuväärse analüüsi algust võreteoorias ja projektiivses geomeetrias: Skolem pidas matemaatilise teooria aksioome puhtalt kombinatoorilisest ja formaalsest vaatepunktist valemite tuletatud väärtuste saamiseks eeldustena kasutatavad valemid. 1990ndate alguses selgus, et võreteooria osa sisaldab otsustusprobleemi lahendust, mida nimetatakse sõnaprobleemiks vabalt genereeritavate võrede jaoks, mille teadaolev lahendus tulenes 1988. aastast! Skolemi terminoloogia ja märkused võlateoorias on Schröderi omad ja see on osa põhjusest, miks tema töö oli kadunud võimalus tõestamisteooria kasutamiseks. Skolem pidas matemaatilise teooria aksioome puhtalt kombinatoorsest ja formaalsest vaatepunktist valemite derivatsioonide valmistamise vahendiks antud valemite põhjal, mida kasutatakse oletustena. 1990ndate alguses selgus, et võreteooria osa sisaldab otsustusprobleemi lahendust, mida nimetatakse sõnaprobleemiks vabalt genereeritavate võrede jaoks, mille teadaolev lahendus tulenes 1988. aastast! Skolemi terminoloogia ja märkused võlateoorias on Schröderi omad ja see on osa põhjusest, miks tema töö oli kadunud võimalus tõestamisteooria kasutamiseks. Skolem pidas matemaatilise teooria aksioome puhtalt kombinatoorsest ja formaalsest vaatepunktist valemite derivatsioonide valmistamise vahendiks antud valemite põhjal, mida kasutatakse oletustena. 1990ndate alguses selgus, et võreteooria osa sisaldab otsustusprobleemi lahendust, mida nimetatakse sõnaprobleemiks vabalt genereeritavate võrede jaoks, mille teadaolev lahendus tulenes 1988. aastast! Skolemi terminoloogia ja märkused võlateoorias on Schröderi omad ja see on osa põhjusest, miks tema töö oli kadunud võimalus tõestamisteooria kasutamiseks.kutsus sõna probleem vabalt tekkivate võrede jaoks, mille teadaolev lahendus tulenes 1988. aastast! Skolemi terminoloogia ja märkused võlateoorias on Schröderi omad ja see on osa põhjusest, miks tema töö oli kadunud võimalus tõestamisteooria kasutamiseks.kutsus sõna probleem vabalt tekkivate võrede jaoks, mille teadaolev lahendus tulenes 1988. aastast! Skolemi terminoloogia ja märkused võlateoorias on Schröderi omad ja see on osa põhjusest, miks tema töö oli kadunud võimalus tõestamisteooria kasutamiseks.

2. Hilberti vana aksomaatiline tõestusteooria

Hilberti 1899. aasta raamat Grundlagen der Geometrie pani aluse 20. sajandi esimeste kümnendite matemaatika kesksetele alusprobleemidele. Need probleemid võib loetleda järgmiselt:

1. Matemaatilise teooria vormistamine. See hõlmab selle põhiobjektide ja suhete valikut ning aksioomide valikut.
2. Aksioomide järjepidevuse tõend.
3. Küsimus aksioomide vastastikuse sõltumatuse ja täielikkuse kohta.
4. Otsustusprobleem: kas on olemas meetod vastuseks kõigile küsimustele, mida võiks teooria raames tõstatada?

Hilberti geomeetria osas jäi selle vormistamise katse ideaalist, mille ta sünnitas. Hilbert leidis palju olulisema valdkonna, millesse ta pidi rakendama oma metamaatikat - nimelt aritmeetikat ja analüüsi. Alustööks oli puhta loogika aksiomaatiliste formulatsioonide nelja põhiprobleemi uurimine. Seega vormistati eeltöötlemise loogika, leiti, et see on järjepidev, täielik ja otsustatav. Esimesed tulemused predikaatloogika kohta on aastast 1915, kui Leopold Löwenheim esitas oma versiooni sellest, mis hiljem sai Löwenheim-Skolemi teoreemiks predikaatloogika jaoks (vt klassikalise loogika sissekannet). Ta lahendas ka otsustusprobleemi erijuhtumid. See areng ei sõltunud Frege-Russelli traditsioonist ja põhines selle asemel Ergest Schröderi algebralisel lähenemisel loogikale. 1920. aasta paiku„Hilberti stiilis” aksiomaatiline lähenemine, nagu seda sageli nimetatakse, oli kõigile teada ja domineeris loogilises stseenis; algebraline lähenemine sulandus võlateooriaga peaaegu märkamata. 1928. aastaks oli Hilberti ja Ackermanni väljaandes Grundzüge der theoretischen Logik esitatud predikaatloogika aksiomaatiline formaalne süsteem koos selle täielikkuse probleemiga. Viimane lahendas Gödel 1929. aastal, avaldati aasta hiljem (Gödel 1930). Neljandal põhiprobleemil, predikaatloogika otsustusprobleemil, osutus kiriku poolt 1936. aastal avaldatud lühikeses artiklis negatiivseks lahenduseks, mis tuleneb Gödeli puudulikkuse teoreemist.s Grundzüge der theoretischen Logik, predikaatloogika aksiomaatiline formaalne süsteem koos selle terviklikkuse probleemiga. Viimane lahendas Gödel 1929. aastal, avaldati aasta hiljem (Gödel 1930). Neljandal põhiprobleemil, predikaatloogika otsustusprobleemil, osutus kiriku poolt 1936. aastal avaldatud lühikeses artiklis negatiivseks lahenduseks, mis tuleneb Gödeli puudulikkuse teoreemist.s Grundzüge der theoretischen Logik, predikaatloogika aksiomaatiline formaalne süsteem koos selle terviklikkuse probleemiga. Viimane lahendas Gödel 1929. aastal, avaldati aasta hiljem (Gödel 1930). Neljandal põhiprobleemil, predikaatloogika otsustusprobleemil, osutus kiriku poolt 1936. aastal avaldatud lühikeses artiklis negatiivseks lahenduseks, mis tuleneb Gödeli puudulikkuse teoreemist.

Hilbert ja tema kool, eeskätt Bernays, Ackermann ja von Neumann, ning samuti noor Herbrand Prantsusmaal, tegid 1920. aastate teisel poolel aritmeetika metamatmaatilist uurimist. Hilbert töötas kvantitaatoritega tegelemiseks välja järjepidevusprobleemide uurimise meetodi, mida nimetatakse epsiloni asendusmeetodiks. Ta leidis, et kaudsed järeldused kvantifikaatorite kohta objektide lõpmatuse korral on järjepidevuse tõestuse ülioluline punkt ja vajavad põhjendust. Ütle, et kui eeldus, et kõigil naturaalarvudel on omadus P, viib võimatuseni, siis võib järeldada arvu, mille omadus on P, mitte vastupidist. Keskne probleem oli seega klassikalise loogika kasutamise õigustamine matemaatilistes tõendites, esiteks aritmeetilistes tõendites. Ackermann oli 1920. aastate lõpu poole lahendusele väga lähedal ja Hilberti koolis valitses optimism. Siis juhtus muidugi ootamatus, kui Gödel tõestas elementaarse aritmeetika täieliku vormistamise võimatust ja, nagu seda varsti tõlgendati, võimatust tõestada aritmeetika järjepidevust sõjaliste vahenditega - ainsad pidasid seda „absoluutselt usaldusväärseks” Hilbert.

3. Järjepidevuse tõestamatus

Pärast seda, kui Gödel oli aritmeetika puudulikkuse septembris 1930 avalikustanud, leidis von Neumann, et aritmeetika järjepidevus on üks Gödeli vaieldamatuid väiteid. Kahjuks oli Gödel teinud sama avastuse, nii et von Neumann ei avaldanud kunagi oma tõendit. Kuid ta arvas, et kirjavahetuses Gödeliga on aritmeetika ja seetõttu ka kogu matemaatika kui terviku järjepidevuse tõestamatus mingis absoluutses mõttes. Gödeli tulemuste vastuvõtmisel oli peategelane Von Neumann: Uute avastuste selgitamiseks katkestas ta 1930. aasta sügisel Berliinis Hilberti tõestusteooria loengud. Need sündmused tekitasid matemaatikute hulgas tohutut elevust, mida näitas ka Carl Hempeli tunnistus:

Võtsin seal kursuse von Neumanniga, kus käsitleti Hilberti katset klassikalise matemaatika järjepidevust tõestada lõplike vahenditega. Meenutan, et keset kursust tuli von Neumann ühe päeva jooksul ja teatas, et sai just paberi Kurt Gödelilt, kes näitas, et eesmärgid, mida Hilbert silmas pidas ja millest ma olin kuulnud Hilberti kursust Göttingenis, ei saa üldse saavutada. Seetõttu loobus Von Neumann selle teemaga tegelemisest ja pühendas ülejäänud kursuse Gödeli tulemuste tutvustamisele. Leiud tekitasid tohutult põnevust. (Hempel 2000, lk 13)

Aastatel 1932–33 leidsid Gödel ja Gentzen üksteisest sõltumatult tõlke klassikalisest Peano aritmeetikast intuitiivsele Heytingi aritmeetikale. Täpsemalt näitab see, et kui vastuolu on tõestatav esimeses, siis see on tõestatav ka teises. Siis tagaks intuitiivse aritmeetika järjepidevus ka klassikalise aritmeetika järjepidevuse. See tulemus oli üllatus: nagu mainitud, arvas Hilbert, et kaudsed "transfinite" eksistentsi tõestused on see osa aritmeetikast, millele tuleb vastuolusid tagada. Gödeli ja Gentzeni tulemuse järgi sisaldas juba intuitsiooniline aritmeetika põhimõtteid, mis ulatusid kaugemale lõplikust arutluskäigust. Heytingule 25. veebruaril 1933 kirjutatud kirjaga Gentzen võtab olukorra kokku järgmiselt:

Piiratud viisil järjepidevuse tõestamine pole… seni õnnestunud, nii et seda Hilberti algset eesmärki pole saavutatud. Kui seevastu tunnistab intuitiivset positsiooni turvalise alusena, st järjekindlana, siis klassikalise aritmeetika järjepidevuse tagab minu tulemus. Kui tahaksime Hilberti nõudeid rahuldada, jääks ikkagi ülesandeks näidata intuitionistlikku aritmeetikat. See pole aga isegi klassikalise aritmeetika ametliku aparatuuri abil võimalik, tuginedes Gödeli tulemusele koos minu tõendiga. Isegi siis kaldun arvama, et intuitiivse aritmeetika järjekindluse tõestamine veelgi ilmsemast positsioonist on võimalik ja ka soovitav. (Menzler-Trott 2007, lk 38)

Viimati mainitud eesmärk oli Gentzeni endale 1932. aasta alguses seatud, kui ta oma vanale õpetajale Hellmuth Kneserile kirja kirjutas:

Olen seadnud oma konkreetseks ülesandeks leida tõend loogilise deduktsiooni järjepidevuse kohta aritmeetikas… Ülesanne muutub loogilise deduktsiooni vormistamise kaudu puhtalt matemaatiliseks probleemiks. Järjepidevuse tõestamine on seni toimunud ainult erijuhtudel, näiteks täisarvude aritmeetika korral ilma täieliku induktsiooni reeglina. Tahaksin selles punktis edasi liikuda ja tühjendada täieliku induktsiooniga vähemalt aritmeetika. Töötan selle kallal juba peaaegu aasta ja loodan varsti selle lõpetada ning esitaksin selle töö siis oma väitekirjana (prof. Bernays). (Menzler-Trott 2007, lk 31)

4. Naturaalne deduktsioon ja järjestikune arvutus

Järjepidevusprogrammi elluviimisel seadis Gentzen oma esimeseks ülesandeks puhtalt loogilise deduktsiooni analüüsi, mida hiljem laiendada aritmeetikale ja analüüsile. Oma väitekirjas (1934–1935) väidab Gentzen, et seadis oma ülesandeks matemaatiliste tõendite analüüsi, nagu need praktikas esinevad. Esimene tähelepanek on see, et tegelikud tõendid ei põhine loogilises keeles väljendatud aksioomidel, nagu Hilberti aksomaatilises tõestusteoorias. Kõige tüüpilisem omadus on selle asemel, et teoreemid esitavad väiteid mõne eelduse alusel. Eeldusi analüüsitakse osade kaupa ja järeldust analüüsitakse ka osade kaupa, kuni need kaks analüüsi kohtuvad ja tõendusmaterjali saab sünteesida. Viimane analüüs lähtub sellest, mida Gentzen nimetas sissejuhatusreegliteks: need annavad piisavad tingimused antud vormi pakkumise tuletamiseks. Näiteks,konjunktsiooni A & B tuletamiseks piisab konjunktsioonide A ja B tuletamisest eraldi. Järeldused antakse formaalselt nagu reeglis

AB	Ja mina
A ja B

Selle asemel analüüsitakse eeldusi nende komponentidesse kõrvaldamisreeglite kaudu, mis annavad üldjoontes eelduste otsesed tagajärjed. Näiteks võib eeldusena kasutatud konjunktsiooni lagundada selle koostisosadeks, nagu reeglites

A ja B & E 1 A

A ja B & E 2 B

Gentzen töötas loodusliku deduktsiooni süsteemi välja ja uuris seda 1932. aastal ning oli jõudnud septembriks 1932 loodusliku deduktsiooni arvutusteni (lühidalt ND), mis on tänapäeval standardne. Selleks ajaks oli ta märganud, et kui sissejuhatusele, näiteks A- ja B-derivatsioonile A-st ja B-st eraldi, järgneb vastav elimineerimine, näiteks A-tuletus, siis valemiga A & B on kohalik maksimum, “küngas”, mida saab kõrvaldada. Ta nimetas selliseid künkaid ka ümbersõiduks ja see, mida nüüd nimetatakse ümbersõidu muundamiseks, eemaldab sellised tarbetud sissejuhatuse-kõrvaldamise etappide paarid. “Normaliseerimise” etappide tulemus on tuletus “normaalsel kujul”.

Implikatsioon on ND-le võib-olla tüüpilisem kui konjunktsioon: A ⊃ B tuletamiseks eeldatakse ajutiselt A, seejärel üritatakse B tuletada. Kui see õnnestub, siis ajutine eeldus suletakse või tühistatakse, kui tehakse järeldus A ⊃ B-le, nagu skemaatilises tuletuses.

[A]
⋮
B	⊃Ma
A ⊃ B

Teises suunas saab A ⊃ B elimineerida, kui leitakse tuletis A, mille jaoks saab B järeldada:

A ⊃ BA	⊃E
B

Kui reeglile ⊃M järgneb ⊃E, siis on tegemist normatiivsusega, mis eemaldatakse ümbersõidu teisendusega: B tuletus (ja mis sellele järgneb) konstrueeritakse, kui saadakse kõrvaldamise reegli väiksema eelduse A tuletus. ja B tuletamine sissejuhatuses oletusest A. Need kaks tükki ühendatakse tuletiseks B, millel puudub ümbersõidu valem A ⊃ B. Gentzeni väitekirjas suletakse kõik eeldused implikatsiooniliste sissejuhatustega, kuid tänapäeval peetakse valemite kogumit avatud eeldustena ka tuletisteks.

Konjunktsiooni ja implikatsiooni reegleid vaadates tuleb märkida, et eeldused (vahetult järeldamisjoone kohal olevad valemid) on I-reeglite järelduse alamvormid, E-reeglites on see vastupidi. Gentzen märkas, et tavalistes tuletustes pärib see üksikute sammude omadus kogu tuletuse selles mõttes, et kõik valemid on järelduse alamvormid. See tulemus andis kõrvalsaadusena otsustusmeetodi intuitsioonilise ettepanekuloogika jaoks. Teine järeldus oli järjekindluse süntaktiline tõend: kui vastuolu on tõestatav, siis on ka midagi tõestatavat, kuid aatomi valemitel pole näiteks ühtegi tõendit: kui tal on tõend, siis on see tavaline, kuid E-reegleid ei kohaldata aatomi valemiga ja seda ei järelda ka ükski I-reegel.

Gentzeni idee oli laiendada looduslikku deduktsiooni aritmeetika süsteemile, lisades reegli, mis vastab täieliku induktsiooni põhimõttele. Järjepidevus tuleneb siis tuletiste ja alamvormi omaduste normaliseerimisest. 1933. aasta alguseks mõistis Gentzen, et see tõestusstrateegia ei lähe läbi: induktsiooni reegel on skemaatiline ja sellel on juhtumite lõpmatus, kuid induktsiooni valemite keerukus pole seotud. Neid valemeid oleks võimatu eelnevalt piirata, seega ei saa alamvormi omadusi omada. Pärast seda ebaõnnestumist võttis Gentzen sõna otseses mõttes oma varase lõputöö käsikirjast tõlke klassikalisest intuitionistlikuks aritmeetikast ja esitas selle paberina märtsis 1933, kuid võttis paberi tagasi, kuuldes Gödeli tulemuse avaldamisest.

Gentzen kirjutas, et ta ei suutnud tõestada ND klassikalise süsteemi normaliseerimisteooriat. Seetõttu leiutas ta uue loogilise meetodi, mida ta nimetas järjestikuseks (Sequenzenkalkul, sõna otseses mõttes "jadade arvutamiseks") ja muutis selle oma lõputöö keskseks teemaks. Arvutuse nimi pärineb tuletise eelduste loendist. Nimisõnana kasutatav sõna “järjestikune” on Kleene'i vihje oma sissejuhatuses metamaatikale (1952: 441), mis on võetud paljudes keeltes puhtalt leiutatud sõnade kujul.

Järjestikust arvutust, lühidalt SC, võib pidada tuletatavuse suhte formaalseks esitamiseks naturaalses deduktsioonis. Järjestik koosneb valemite loendist an, noolt (Gentzenis on hiljem kasutatud ka muid markereid) ja järeldust ühest valemist. Loend annab eeldused, millest järeldus sõltub tuletises, lokaalses märkes, kus ND-s leidub neid tuletuspuu lehtedes. Gentzen üldistas ka järjestused, nii et neil on ühe järelduse asemel noole järel võimalike juhtumite loetelu. See uudsus viis klassikalise loogika tõestussüsteemi esimese rahuldava formuleerimiseni. Gentzeni konjunktsiooni ja implikatsiooni SC reeglid koos komadega eraldavad elemente loendites:

Konjunktsioon
Γ → Δ, A Γ → Δ, B R & Γ → Δ, A ja B	A, Γ → Δ L & 1 A & B, Γ → Δ	B, Γ → Δ L ja 2 A & B, Γ → Δ

Mõju
A, Γ → Δ, B R⊃ Γ → Δ, A ⊃ B	Γ → Θ, AB, Δ → Λ L⊃ A ⊃ B, Γ, Δ → Θ, Λ

See pole koht, kus selgitada ND ja SC üksikasju (kuid vaadake automatiseeritud mõttekäiku käsitlevat kirjet). Gentzen sõnastas viimase, tähistades LK, nii et see andis intuitsioonistliku arvutuse, tähistas LJ erijuhuna, mille kokkuvõtteks on maksimaalselt ühe juhtumi loetelu. Seejärel tõestas ta klassikalise kivi, arvutuskriteeriumi ja normatiivsuse teoreemi analoogi, mis olid hoolikalt formuleeritud nii, et intuitionistliku arvutuse tulemus oli eriline juhtum klassikalise arvutuse jaoks. LJ-s ja LK-s tähistab L “logistilisust” - terminit, milles Gentzen viitab Frege, Russelli ning Hilbert ja Bernaysi loogika aksiomaatilistele kalkulaatoritele. Sellistes arvutustes on tuletise iga rida iseenesest õige, st loogiline tõde, kust see mõiste pärineb. Tähed K ja J pärinevad saksa sõnadest klassisch ja intuitionistisch.(Viimane peaks seega olema suurtäht "I", kuid vanem saksa keel kasutab suurtähte "J" suurtähe "I" jaoks.)

Gentzen nimetas normaliseerimise analoogi Hauptsatzi kujuteldamatu nimega “peateemaks”. Tänapäeval on standardterminiks lõigatud elimineerimise teoreem. Kõigil SC loogilistel reeglitel on alamvormi omadus väga otseses tähenduses: iga eelduse valem on valem või alamvorm järeldustes. Tuletuste kombineerimise reeglit, mis on analoogne ülaltoodud selgitusega ümbersõidu teisenduste korral ND-s, nimetatakse lõikamiseks. Selles esineb valem A juhtumina esimeses eelduses ja eelduses teises eelduses. Kokkuvõtteks on see valem kadunud ja kahe eelduse kokku kogutud eeldused:

Γ → AA, Δ → C	Lõika
Γ, Δ → C

Seega on lõikamine ainus reegel, mis muudab valemi tuletises „kaduma“. Gentzen näitas, et lõikereegli juhtumeid saab tuletistest kõrvaldada, lastes neid ülespoole, kuni nad jõuavad punktideni, kus tuletus algab. ND-s on lähtepunktid eeldused, SC-s on nad „algjärjestused“kujul A → A, milles eelduse valem A on samal ajal ka järeldus. Lõikel, mille järjestus on üks eeldus, on teine eeldus võrdne järeldusega ja seetõttu saab selle kustutada.

Pärast kärbete kõrvaldamise tõendit polnud Gentzenil võimalik intuitiivse loomuliku deduktsiooni normaliseerimiseks tõestada. Ta andis Bernaysile oma väitekirja esimese käsikirjalise versiooni koos üksikasjalike normaliseerimistõenditega (mis vastab umbes 13 trükitud lehele), kuid viimane näib olevat kunagi mõistnud, mis tal käes oli. Tõend avastas selle autor Zürichi Bernaysi artiklite hulgas 2005. aasta veebruaris ja on nüüd saadaval ingliskeelses tõlkes (Gentzen 1933 [2008]).

5. Aritmeetika ja analüüsi järjepidevus

Pärast oma lõputööd ND ja SC puhta loogika alal jätkas Gentzen oma kava aritmeetika järjepidevuse tõestamiseks. Tulemus oli valmis detsembriks 1934. Mis see esimene tõestus oli, pole üksikasjalikult teada. Kuid 1938. aasta kirjas Bernays'ile osutatakse, et tõend, mille Gentzen 1935. aasta suveks maha kirjutas, polnud mitte originaal, vaid teine tõend (vt Menzler-Trott 2001, 79). Seda teist tõendit kritiseerisid Bernays ja Gödel, kes arutasid seda oma Atlandi ookeani-teekonna ajal Princetonisse septembris 1935. Gentzeni idee tõendis oli järgmine: kõigepealt võtke loodusliku deduktsiooni konjunktsiooni-eituse-universaalse kvantifitseerimise fragment kui loogikat, mida kasutatakse aritmeetika vormistamine. Seejärel kirjutage iga reegli eksemplar nii, et eeldustel ja järeldustel oleksid vasakpoolses osas toodud avatud eeldused,noolega, mis eraldab järelduse, järelikult. Seda ND varianti nimetatakse nüüd SC-stiilis ND-ks. Mõelge järgnevale Γ →C Kui selle järeldus on aatomi valem, on see arvude vaheline võrrand. Halvimal juhul on see vale, nii et siis kaaluge eelduste loetelu. Kui üks eeldus on konjunktsioon, asendage see teie valitud konjunktiiviga, kui universaalne kvantifitseerimine, siis eksemplariga. Kui see on eitus ¬ A, asendage järeldus A-ga. Kui selle "taandamisprotsessi" mis tahes etapis on järjestuse järeldus liitvalem, peate võimaliku järeldusena kaaluma mis tahes konjunkti või üldise kvantifitseerimise juhtumit. Kui eitus ¬ A järeldusena, liigutage A eelduse ossa ja asendage järeldus arvuga 0 = 1. Gentzen näitab, et jätkates sel viisil eeldusel, et vaadeldav jada on tuletatav, leitakse kas tõene võrrand järeldusena või vale võrrand eeldusena. Seegaei ole tuletatavaid jadasid, mille kõik eeldused oleksid tõesed ja järeldus vale.

Gödeli ja Bernaysi jaoks oli ebaselge, mida tõend eeldas; nad arvasid, et eeldatakse seda, mida intuitiivses matemaatikas tuntakse kui fänni teooriat, kuid see oli vale. Gentzeni redutseerimisprotseduuri lõpetamist saab selle asemel tõestada induktsiooniga hästi rajatud puudele (“bar-induction”) - põhimõttega, mida Gentzen kasutas intuitiivsetel alustel. Igatahes oli kriitika tulemuseks see, et Gentzen muutis tõendusmaterjali täiendavaks muutmata kolmandaks tõendiks, mis kasutab nüüd kuulsat transfinite induktsiooni põhimõtet kuni esimese epsiloninumbrini. See induktsioon esitati kodeerimise kaudu, milles kasutati komakohti. Gentzeni 1936. aastal avaldatud muudatuste konkreetne tulemus polnud aga hea: loogiline arvutus tehti vahepeal seitsmekümne paaritu lehekülje pikkuses artiklis, mida oli väga raske lugeda. Seetõttu tõestas Gentzen praeguse arvulise neljanda tõendi aritmeetika järjepidevuse kohta 1938. aastal (Zürichi ETH Bernays arhiivis), tuginedes seekord 1933. aasta klassikalisele järjestikusele calculus LK-le. Nagu mainitud, näitab kirjavahetus Bernays'ega järgmist: seeläbi pöördus ta tagasi tõendusmeetodi juurde, mis oli 1934. aastal edu saavutanud. Transfinite induktsiooni kasutamine on 1938. aasta paberil tavalise märkuse abil selgelt nähtav. Selliseid sissejuhatuse põhimõtteid Cantori „teise numbriklassi” kohta käsitletakse üksikasjalikult Hilberti 1925. aasta loengus „Über das Unendliche” („Lõpmatul”, avaldatud 1926), artiklis, millele Gentzen viitas.seekord põhineb 1933. aasta klassikalisel järjestikulisel arvutusel LK. Nagu mainitud, näitab kirjavahetus Bernaysiga, et ta pöördus tagasi tõendusmeetodi juurde, mis oli 1934. aastal edu saavutanud. Transfinite induktsiooni kasutamine on 1938. aasta paberil selgelt nähtav. korraline märge. Selliseid sissejuhatuse põhimõtteid Cantori „teise numbriklassi” kohta käsitletakse üksikasjalikult Hilberti 1925. aasta loengus „Über das Unendliche” („Lõpmatul”, avaldatud 1926), artiklis, millele Gentzen viitas.seekord põhineb 1933. aasta klassikalisel järjestikulisel arvutusel LK. Nagu mainitud, näitab kirjavahetus Bernaysiga, et ta pöördus tagasi tõendusmeetodi juurde, mis oli 1934. aastal edu saavutanud. Transfinite induktsiooni kasutamine on 1938. aasta paberil selgelt nähtav. korraline märge. Selliseid sissejuhatuse põhimõtteid Cantori „teise numbriklassi” kohta käsitletakse üksikasjalikult Hilberti 1925. aasta loengus „Über das Unendliche” („Lõpmatul”, avaldatud 1926), artiklis, millele Gentzen viitas.s 1925. aasta loeng “Über das Unendliche” (“Lõpmatu peal”, avaldatud 1926), paber, millele Gentzen viitas.s 1925. aasta loeng “Über das Unendliche” (“Lõpmatu peal”, avaldatud 1926), paber, millele Gentzen viitas.

Oleks võinud arvata, et see oli nii, kuid Gentzenil oli põhjust oma viimases, 1943. aastal avaldatud, kuid enne sõda 1939 kirjutatud kirjutises esitada isegi neljas tõend aritmeetika järjepidevuse kohta. Ta laiendas Peano aritmeetikat läbi piiritletud käskkirjade ja tegi transfinite induktsiooni põhimõtteline osa sellest laiendatud arvutusest. Siis näitas ta otse, et transfinite induktsioon kuni esimese epsilon-arvuni ₀ on väljendatav, kuid süsteemis mitte tõestatav. Gödeli mittetäielikkuse teoreem on seega tõestatud hoopis teisel viisil. Tõestuse idee on lühidalt järgmine: esmalt pannakse paika, mida tähendab tuletada süsteemis kindlale järjenumbrile piirmääratud induktsioon. Teiseks, järgarvud alla ε ₀on seotud tuletistega. Neid nimetatakse väärtusteks. Seejärel näidatakse, et kui järjenumbrile transfiniteeritud induktsioon on tuletatav, ei saa see järgarv olla suurem kui tuletuse väärtus. Seetõttu ei ole transfinite induktsioon väärtuseni _{0 0} tuletatav.

Kuna induktsiooni põhimõtet saab tavalises aritmeetikas väljendada, kuid mitte tõestada, leitakse Peano aritmeetikas tõestamatu valem. Gentzeni lünklikkuse teoreemi versiooni hõlpsaks tagajärjeks on Peano aritmeetika järjepidevus, sest kõik oleks ebajärjekindlas süsteemis tõestatav. Vastupidiselt Gödeli „kunstlikule” tõestamatule valemile, mis saadi aritmeeritud tõestatavuse predikaadi kodeerimise teel, on Gentzeni transfinite induktsiooni põhimõte „tavalise” matemaatika põhimõte.

Gentzeni viimane tõestus määras Peano aritmeetika “tõenditeoreetilise ordinaali”, nimelt selle, mida on vaja järjepidevuse tõestamiseks, omadusega, millest kõigest muust ei piisa. Töö tähistas ordinaalse tõestusteooria algust. See oli kahtlemata kõige olulisem aritmeetika põhiline saavutus pärast Gödeli puudulikkuse teoreeme, kuid on endiselt suures osas teadmata - Gödeli teoreemide kohta võib leida palju raamatuid, kus isegi Gentzenit ei mainita.

Näib, et Gödel polnud mõelnud aritmeetika järjepidevuse tõestamiseks mitte-finitaarsete, kuid siiski konstruktiivsete põhimõtete abil. Kolmekümnendate aastate lõpus, vähemalt alates 1938. aastast, arendas ta vastusena Gentzeni tõenditele välja omaenda intuitsioonilise loogika ja aritmeetika tõlgenduse, mida hakati nimetama Dialektika tõlgenduseks. Intuitistliku aritmeetika tõendite tõlgendamiseks kasutab see arvutatavaid funktsionaalseid. Gödel avaldas tõlgenduse alles 1958. aastal, ehkki ta oli seda 1941. aastal loengutel esitanud. Pole teada, kas ta arutas seda küsimust, kui kohtus Gentzeniga detsembris 1939.

Bernaysi palvel reprodutseeris Ackermann Gentzeni tõendid Hilberti epsilon-calculuse kohta 1940. aastal. Ackermanni paber oli Kreiseli 1951. aasta aritmeetika tõlgendamise “vastulähedase näite” lähtepunkt. Üllatus oli, kui Gödeli kogutud dokumentide avaldamine tõi 1938. aastal Viinis päevavalgele tema Zilseli-loengu: ta kirjeldab seda tõlgendust Gentzeni 1935. aasta tõendi ümbersõnastatuna. (Seda teemat käsitletakse üksikasjalikult Tait'is (2005), kes oli ise 1960. aastatel töötanud näitevaba tõlgendamise ja selle laiendamise analüüsile.)

Järgmine ilmne ülesanne tõestusteoorias oli pärast aritmeetika järjepidevuse tõestamist tõestada analüüsi, st reaalarvude teooria järjepidevust. Gentzen tegi selles suunas tööd, kuid määrati siis 1939. aasta sügisel ajateenistusse. (Ta vaatas ja teatas Brunswicki linna kohal lennanud lennukite tüüpi, arvu ja suunda, kuni teda tabas närviline 1942. aasta alguses. Jätkas ta analüüsimist, kuid teemale omased raskused olid suured, nagu ka sõja põhjustatud praktilised raskused elus. Analüüs pidi olema formuleeritud teise järgu aritmeetika süsteemina, mis tähendab, et kvantifitseerimine laieneb arvuteoreetilisele predikaadile või samaväärselt naturaalarvude komplektidele. Gentzeni viimases artiklis kasutatakse teise järgu numbriteooriat,avaldatud 1943. aastal, kus on lühidalt näidatud, et transfinite induktsiooni põhimõte kuni ε₀ on tuletatav teise astme numbrite teoorias.

Rohkem kui pool sajandit on möödunud, ilma et oleks olemas ühtegi konstruktiivset tõendit teise astme aritmeetika täielikkuse järjepidevuse kohta. Varasemad pioneerid selles valdkonnas olid Kurt Schütte ja Gaisi Takeuti. Esimene lõi 1951. aastal infinitaarse järjestikuse kalkulaadi, et esitada järjepidevuse tõestusmaterjalid silmapaistval viisil, viimane kasutas selle asemel traditsioonilisemat Gentzen-stiilis kalkulat (vt Takeuti 1987).

Praeguses teise järgu aritmeetika tõestusteooria uurimisel uuritakse, mida tuntakse teise järgu aritmeetika alamsüsteemidena. Tugevaimad tulemused tänase seisuga on lühikese lühikokkuvõtte korral järgmised: laske X vahemikul üle arvuteoreetiliste predikaatide. Valem nagu X (x) väidab, et x-l on omadus, mida väljendab X. Nüüd saame kasutada esimese ja teise järgu loogikat, et moodustada ühendvalemeid nagu (X (X x ∨ ¬ X x). Naturaalarvude kogumit, mille jaoks selline universaalse teise järgu kvantifikaatoriga valem omab, nimetatakse Π11-komplektiks (antud juhul naturaalarvude koguks). Üldisemalt on mõistmise aksioom kujul ∃ X ∀ x (X x ↔ B (x)). Kui valemil B pole teise järgu kvantiive, annab aksioom nn aritmeetilise arusaamise või ACA. Kui B võib olla kujul ∀ Y ∃ ZC (x) ilma teise järgu kvantifikaatoriteta, saadakse Π12-mõistmise erijuhtum. Toshiyasu Arai ja Michael Rathjen andsid 1990. aastate keskel tõendusmaterjali teise astme aritmeetika alamsüsteemi järjepidevuse kohta Π12-arusaamisega. (nende arengute kohta vt Rathjen 1995).

6. Loodusliku deduktsiooni hilisemad arengud

Ajal, kui Gentzen töötas välja oma loomuliku deduktsiooni süsteemi, töötas Stanislaw Jaskowski välja ka loogilise süsteemi eelduste põhjendamiseks. Tuletiste valemid on paigutatud lineaarsesse järjestusesse, kuid Jaskowski 1934. aasta paber jäi fragmentaarseks ja ilma oluliste tulemusteta, näiteks alamvormi omadus. Loodusliku deduktsiooni lineaarset varianti järgitakse paljudes elementaarse loogika pedagoogilistes ekspositsioonides (mõnikord nimetatakse neid ka "Fitchi süsteemideks"). Gentzen leidis Jaskowski teose 1936. aasta juuniks, kui mõlemad olid Münsteris, ja pidas selle valemite lineaarset paigutust parenduseks, „vabanemiseks puuvormi väsimusest” selliseks, mis peegeldab „mõtlemise lineaarsust” (endine alates avaldamata märkmeid, viimane Gentzeni lõputööst).

Loodusliku deduktsiooni süsteem seisis enamasti u 30 aastat, kuni Dag Prawitzi 1965. aasta väitekirjani “Looduslik mahaarvamine: tõestatud teoreetiline uurimus”. Järjekord, milles Prawitz esitas normaliseerimisteoreemi, erines Gentzeni varase lõputöö käsikirjas esitatud järjekorrast. Prawitz esitas kõigepealt normaalteoreemi ja alamvormi omaduse klassikalise loogika loomuliku deduktsiooni süsteemi jaoks. See süsteem ei sisalda disjunktsiooni ega olemasolu. Teises etapis pidas ta predikaatloogika täielikuks keeleks intuitiivset looduslikku deduktsiooni ja tagandas selle normaliseerimise ümbersõidu teisenduste kustutamiseni nagu klassikalise loogika fragment. Kui Gentzen tõestas normaliseerumist 2005. aastal, ütles Prawitz vestluses praeguse autoriga, et on selge, et Gentzen teadis tulemust,kuna trükitud lõputöö märkused on nii sugestiivsed.

1960. aastate lõpus muutus probleemiks tugev normaliseerumine: Prawitz, kasutades William Taiti ja Jean-Yves Girardi varasemat tööd, tõestas 1971. aastal, et derivatsiooni mitte-normaalsusi saab teisendada suvalises järjekorras, lõpetades normaliseerimisprotsessi ja ainulaadse selle tulemusel normaalne tuletus. Näib, et Gentzen pole seda viimast märganud, kuid näib arvavat pigem vastupidist, kuna selle omaduse tõttu ei õnnestunud järkjärgulises arvutis kärpeid kõrvaldada.

Umbes samal ajal, kui uuriti tugevat normaliseerumist, tekkis Curry-Howardi kirjavahetus. Curry oli oma kombinatoorse loogikaga seotud töös 1950. aastate lõpus jälginud implikatsiooni elimineerimise loomuliku deduktsiooni ja funktsionaalse rakenduse vahelist analoogiat (Curry ja Feys 1958). Idee oli sama vana kui intuitsiooniline loogika: ühenduste ja kvantifikaatorite “BHK-seletuse” abil (Brouwer-Heyting-Kolmogorovi jaoks) väljendatakse intuitsioonilises loogikas pakutavate väidete vorme ettekirjutustena nende väidete tõestamiseks: konjunktsioon A & B tõestatakse, kui tõestatakse A ja B eraldi, disjunktsioon A ∨ B tõestatakse ühega A ja B, ja implikatsioon A ⊃ B, näidates, kuidas teisendada mis tahes A tõend B-tõendiks ja nii edasi. Need seletused lähenevad loodusliku mahaarvamise sissejuhatuse reeglitele,kuid pole teada, milline oli nende mõju Gentzeni mõttele.

Curry-Howardi kirjavahetus, mis pärineb William Howardi 1969. aasta artiklist, kuid avaldati alles 1980. aastal, põhineb põhimõttel „valemid kui tüübid“või mõnes teises kõnepruugis põhimõttel „ettepanekud-kui-komplektid“. Pakkumist peetakse selle tõendite kogumiks. Pakkumise tõde vastab komplekti mittetühjusele. A ⊃ B tõendid on nüüd funktsioonid alates (tõestused) A kuni (tõendid) B ja A ⊃ B ise on selliste funktsioonide kogum. Seega, kui f: A ⊃ B ja a: A, siis funktsionaalne rakendus annab f (a): B. Pöörd, mis vastab implikatsiooni sissejuhatusele, on kinni peetud Alonzo kiriku λ-kalkulatsiooni funktsionaalse abstraktsiooni põhimõttel.

Curry-Howardi kirjavahetus on muutnud infotehnoloogia õppekavast intuitiivse loomuliku deduktiivsuse: see annab intuitsioonilise loogika jaoks arvutusliku semantika, milles arvutused ja üldisemalt programmide täitmised toimuvad normaliseerimise kaudu. Näiteks implikatsiooni A ⊃ B tõend on programm, mis teisendab A-tüüpi andmed B-tüüpi väljundiks. A-tüüpi B objekti (tõestus, funktsioon, programm) f ehitamine lõpeb abstraktsiooniga. Kui A-tüüpi objekt a sisestatakse argumendina f-sse, pole tulemuseks olev avaldis normaalne, kuid sellel on vorm, mis vastab sissejuhatusele ja millele järgneb eliminatsioon. Normaliseerimine on nüüd sama, mis programmi käivitamine f. Intuitsionistliku loogika kasutamine ei ole seotud ühegi intuitsioonilise matemaatikafilosoofiaga,kuid on lihtsalt arvutiprogrammide täitmise lõpetamise süsteemne garantii.

7. Järjestikune arvutus: hilisemad arengud / rakendused

Gentzeni doktoritöö tähistas struktuuritõestusteooria sündi, vastandatuna Hilberti vanale aksioomaatilisele tõestusteooriale. Märkimisväärse sammu järkjärgulise arvutamise süsteemide arendamisel astus Oiva Ketonen oma doktoritöös 1944. aastal. Helsingi matemaatika ja filosoofia üliõpilane Ketonen läks 1938. aastal Göttingeni õppima tõendusteooriat, kus Gentzen on kõige lähedasem. õpilasele, kes viimasel kunagi oli. Tundub, et ühenduse on loonud Ketoneni filosoofiaprofessor Eino Kaila, kes oli Gentzeniga kohtunud 1936. aastal Münsteris. Ketonen meenutas hiljem, et Gentzen oli "mõistvalt väheste sõnade noormees", kes andis talle sissejuhatuse tõenditeoreetilistesse süsteemidesse ja tulemustesse. Ketonen 'Kõige tuntum avastus on järkjärguline arvutus klassikalise propositsioonilise loogika jaoks, mille loogilised reeglid on kõik pöördumatud, mis tähendab, et kui jada on kujul, mis vastab loogilise reegli järeldusele, vastavad vastavad eeldused, mis on antud jadast üheselt määratletud ja reegel, on ka tuletatavad. Vastupidine on kohene (kohaldage lihtsalt reeglit). Näiteks reeglid L ja L⊃ muudetakse järgmisteks

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

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

Konjunktsiooniks on ainult üks vasakpoolne reegel (ja kahes käändes ainult üks parempoolne reegel). Vasakpoolse implikatsiooni reeglil on nn ühised kontekstid: järelduses esitatud oletusi ja juhtumeid, välja arvatud ühendühendiga valem, korratakse mõlemas eelduses identselt. Ketoneni idee oli määratleda tõendusotsingute süsteem: üks lähtub tuletatavast jadast, valib selles valemi ja kirjutab reegli eeldused, mis suudavad antud jada sõlmida. Ümberpööratavusega asendab tuletatavuse küsimus ühe või kahe samaväärse tuletatavuse küsimusega lihtsamatel jadadel. Uusi reegleid on vaja, et tagada üheselt määratletud eeldused sellises “juur-esimene” lagunemises.

Ketonen tõestas oma järgnenud arvutuse loogiliste reeglite ümberpööramatust tõestatuna lõike järgi. Hiljem andsid Kurt Schütte (1950) ja Haskell Curry (1963) otseseid tõendeid ümberpööratavuse kohta, kusjuures viimased olid selgesõnalise tulemusega, et ümberpööramised säilitavad kõrguse: kui antud jada on tuletatav maksimaalselt n-astmeliselt, on eeldused reeglis, mis võib järeldage, et ka järjestusel on tuletus maksimaalselt n-etapis.

Kui suur osa Ketoneni tööst tuleneb Gentzeni ettepanekutest, jääb teadmata, sest kirjavahetust pole leitud. Ketonen kirjutab oma lõputöö eessõnas, et “Dr. Göttingenist pärit G. Gentzen suunas mind selle töö probleemsesse valdkonda”. Lõputöö oli Ketoneni ainus loogika originaalteos, mille päästis unustusest pikk ülevaade, mille Bernays sellest 1945. aastal ajakirjale Symbolic Logic kirjutas.

Üks inimene, kes 1940. aastate lõpus Ketoneni kalkuleid tundis, oli Evert Beth. Kui Beth hiljem, 1955. aastal esitles oma tuntud tableau calculust, näib ta olevat unustanud tableau calculus päritolu Ketoneni ümbersõnastatuna, kuid viitab selle asemel Kleene 1952. aasta mõjukale sissejuhatusele metamaatikale. Kleene kuni Ketoneni arvutusteni Bernaysi arvustusest ja käsitles ka intuitsioonistlikku järjestikust kalkulatsiooni, mille ümberpööratavus on piiratum kui klassikalises arvutuskriteeriumis. Kleene raamatuga said Gentzeni järgnenud kalkunid üldiselt tuntuks ja kättesaadavaks.

Kleene 1950ndate alguse looming oli teerajajaks ka järkjärgulise kalkuleerimise märkimisväärsele arengule, nimelt „kokkutõmbumisvabale” klassikalisele ja intuitionistlikule kalkuleerimisele, mida täna tähistavad G3c ja G3i. Neil kalkulatsioonidel on selline omadus, et ühtegi Gentzeni algsest “struktuurireeglist” pole vaja. Nõrgendamise reegel võimaldab lisada üleliigseid juhtumeid ja eeldusi ning reegli "kahandada" valemi ühe eksemplari kustutamise, kui loendis on kaks, nagu näiteks

Nõrgenemine		Kokkutõmbumine
Γ → Δ Wk A, Γ → Δ		A, A, Γ → Δ Ctr A, Γ → Δ

Analoogsed reeglid võimaldavad nõrgendada ja kokku tõmmata jadade paremas, järjestikuses osas. Nõrgenemine on muudetav reegliks, lastes algsetel järjestustel Gentzeni A → A asemel olla A,, → Δ, A. Ka kokkutõmbumine on reeglite sobiva sõnastusega välistatav. Import tähendab seda, et juur-esimese tõendite otsingus ei pea rakendama reegleid, mis tooksid valemis eeldusest dubleerimise. Ilma selle tulemuseta ei toimuks tõendusotsingu lõpetamine.

Klassikalisel kalkunil on ülalnimetatud omadus säilitada loogiliste reeglite ümberpööramatus kõrgusega. Albert Dragalin täpsustas 1970. aastate lõpul kalkulatsiooni selliseks, milles struktuurireeglid on pealegi „kõrguse säilitamise lubatavad”, mis tähendab, et kui sellise reegli eeldus on tuletatav, on järeldus tuletatav ilma reeglita ja maksimaalselt samaga tuletise suurus (reeglite esinemisjuhtude maksimaalne arv tuletusharus). Sellel omadusel on sügav mõju lõikamise likvideerimisele: lõikamise permuteerimisel pidi Gentzen nõrkade ja kokkutõmbumiste abil taastama algsed kontekstid (Γ ja Δ). Nende reeglite lubatava kõrguse säilitamise korral tuletiste suurus reeglite kohaldamisel ei suurene. Dragalin andis ka intuitsioonilise multisuktsedent-arvutuse, mille struktuurireeglid olid sama tüüpi lubatavad. Lõpuks andis Troelstra õpikus Basic Proof Theory (2000, esimene trükk 1996) ühe õnnestumisega intuitionistliku arvutuse, mille kõrgus säilitaks nõrgenemise ja kokkutõmbumise lubatavust. Kontraktsioonivabad järjestikused kivid on võimsad tööriistad formaalsete tuletuste analüüsimiseks. Paljud loogika keerulised uurimistulemused muutuvad lihtsalt harjutusteks tõendite struktuuri kontrolli kaudu, mida G3-arvud võimaldavad. Kontraktsioonivabad järjestikused kivid on võimsad tööriistad formaalsete tuletuste analüüsimiseks. Paljud loogika keerulised uurimistulemused muutuvad lihtsalt harjutusteks tõendite struktuuri kontrolli kaudu, mida G3-arvud võimaldavad. Kontraktsioonivabad järjestikused kivid on võimsad tööriistad formaalsete tuletuste analüüsimiseks. Paljud loogika keerulised uurimistulemused muutuvad lihtsalt harjutusteks tõendite struktuuri kontrolli kaudu, mida G3-arvud võimaldavad.

Järjestikuse matemaatika varaseim rakendamine matemaatikas oli aritmeetika tõestusteoorias, Gentzeni väitekirjas ja otsustaval viisil 1938. aastal aritmeetika järjepidevuse tõestuses. Troelstra mainib Ketoneni loomingut

lõigatud tõendite varajane analüüs Gentzeni kuldides koos aksioomidega; kuid ta kaalub cutfree-tuletiste vormi puhtas arvutis, kus tuletatud sekventide eelnevas on aksioomid. (Troelstra ja Schwichtenberg 2000: 142)

Aksioomid, mida Ketonen peab, on projektiivsed ja afiinsed geomeetriad, endised on võetud Skolemi 1920. aasta paberist, mida käsitleti ülalpool esimeses osas. Ketonen soovis Skolemi ametlikud tõendamisreeglid sõnastada järjestikuses arvutustes. Kuid Ketoneni loomingut tunti enamasti ainult Bernays'i ülevaate kaudu ja seal selgitati üksikasjalikult ainult järgnenud kivi loogilist osa.

Teine viis järjestikuse arvutuse rakendamiseks on lasta tuletusharudest algavatel jadadel lisaks esialgsetele jadadele ka vorm → A, milles A on aksioom või universaalse aksioomi näide. Nüüd, Gentzeni “laiendatud Hauptsatzi” järgi, saab tuletiste kärpeid piirata seni, kuni nende üheks eelduseks on aksioom, kuid need aksioomide kärped jäävad alles. Teine, uuem meetod on aksioomide teisendamine lisareegliteks, mis lisatakse järkjärgulise arvutuse loogilistele reeglitele, säilitades täieliku lõikamise (nagu on selgitatud Negri ja von Plato 2001 6. peatükis ning Troelstra ja Schwichtenbergi 2000. aasta peatükis 4.7)..

8. Tõestusteooria eesmärgid

Mil määral on tõestusteooria oma algsed eesmärgid saavutanud? Hilberti jaoks olid eesmärgid põhjalike probleemide täielik selgitamine järjepidevuse lõplike tõendite abil jne, mille puhul tõestusteooria ebaõnnestus. Hilbert ei olnud oma programmis huvitatud matemaatiliste tõendite uurimisest iseenesest, vaid üksnes kesksete vundamentide probleemide puhastamisest (ja siis nende unustamisest). Hilberti hiljuti leitud märkus annab teistsuguse pildi: märkuses öeldakse, et Hilbert soovis oma kuulsas Pariisi 1900. aasta matemaatikaprobleemide loendis 24. ja viimase probleemina lisada matemaatika tõestusmeetodite teooria väljatöötamise. See oli enne tema metamatemaatilise programmi väljatöötamist tõestusteooria väljatöötamiseks.

Gentzeni jaoks olid eesmärgid koos Hilberti eesmärkidega mõista ka matemaatiliste tõendite ülesehitust. See programm oli puhta loogika ja aritmeetika osas täielik edu. Eelkõige võimaldavad järjestikuse arvutamise meetodid põhjalike tulemustega tõendite analüüsi. Tõendamisteooria suurt eesmärki - analüüsi järjepidevuse tõendit nagu Hilberti teises Pariisi probleemis - ei ole ka ellu viidud, kuid see pole ka välistatud.

Mõningane tõestuse mõiste mõistmine on iga matemaatiku jaoks vajalik, kui mitte millegi muu jaoks, siis vähemalt matemaatiliste tulemuste edastatavuse tagamiseks: avaldamine toetub mõistmisele, et tõestusi saab teha nii selgesõnalisena, et nende õigsust saab regulaarselt kontrollida. Tõestusteooria pole aga seni muutunud töötava matemaatiku praktiliseks tööriistaks; matemaatika rakendused on olnud üsna üksikjuhud. Hiljutised tööd matemaatiliste tõendite vormistamisel arvutipõhiste süsteemidega, mida nimetatakse korrektoriteks, võivad seda pilti järk-järgult muuta.

Tõestusteooria on loonud uued eesmärgid väljaspool traditsioonilist matemaatikat, eriti seoses arvutiteadusega. Sellised teemad nagu arvutiprogrammide õigsuse kontrollimine on tõestusteooria väljakasv. Naturaalne deduktsioon on viinud Curry-Howardi vastavusse ja ühendused funktsionaalse programmeerimisega. Järjestikuseid arvutusi kasutatakse sageli automaatse tõendusotsingu süsteemides, nagu ka loogilise programmeerimise korral.

Bibliograafia

Tekstid tõestusteooria kohta

• Buss, Sam (toim), 1998, Tõendusteooria käsiraamat, Amsterdam: Elsevier.
• Negri, S. ja J. von Plato, 2001, Struktuuritõendamise teooria, Cambridge: Cambridge University Press.
• von Plato, J., 2013, Loogilise mõtlemise elemendid, Cambridge: Cambridge University Press.
• Takeuti, G., 1987, tõestusteooria, Amsterdam: Põhja-Holland, 2. trükk.
• Troelstra, A. ja H. Schwichtenberg, 2000, algteabe teooria, Cambridge: Cambridge University Press, 2. trükk.

Originaalteosed ja nende kordustrükid

• Ackermann, W. 1940, “Zur Widerspruchsfreiheit der Zahlentheorie”, Mathematische Annalen, 117: 162–194.
• Beth, E., 1955, Semantiline kaasamine ja formaalne tuletatavus (Mededelingen der Koninklijke Nederlandse Akademie van Wetenschappen. Afd. Letterkunde. Nieuwe reeks, deel 18, nr 13), Amsterdam: Põhja-Holland.
• Church, A., 1936, “Märkus entscheidungsprobleemi kohta”, Journal of Symbolic Logic, 1: 40–41.
• Curry, H. ja Feys, R., 1958. Kombineeriv loogika. (Uuringud loogikas ja matemaatika alused, I köide), 1. trükk, Amsterdam: Põhja-Holland.
• Curry, H., 1963, Matemaatilise loogika alused, New York: McGraw-Hill; kordustrükk New York: Dover, 1977.
• Dragalin, A., 1988, Matemaatiline intuitsioonism: sissejuhatus tõendusteooriasse, Providence, RI: American Mathematical Society.
• Gentzen, G., 1934–1935, Untersuchungen über das logische Schliessen (Loogiliste järelduste uurimine), Ph. D. lõputöö, Universität Göttingen. Avaldatud Gentzen 1969: 68–131.
• Gentzen, G., 1938, “Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie”, Forschungen zur Logik ja zur Grundlegung der exakten Wissenschaften, Neue Folge 4, S. Hrizel, 19–44. Tõlgitud Gentzenis 1969: 252–286.
• Gentzen, G., 1943, “Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie”, Mathematische Annalen, 119: 252–286. Tõlgitud Gentzenis 1969: 287–308.
• Gentzen, G., 1969, Gerhard Gentzeni kogutud paberid, toim. M. Szabo, Amsterdam: Põhja-Holland.
• Gentzen, G., 2008, “Tuletuste normaliseerimine”, Sümboolse loogika bülletään, 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 (I – V köide), S. Feferman jt. (toim), Oxford: Oxford University Press.
• van Heijenoort, J., 1967, Fregest Gödelini, Cambridge, MA: Harvard University Press.
• Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: BG Teubner.
• Hilbert, D., 1926, “Über das Unendliche” (“Lõpmatul”), Mathematische Annalen, 95: 161–190. [Loeng Münsteris, 4. juunil 1925.]
• Hilbert, D. ja Ackermann, W., 1928, Grundzüge der theoretischen Logik, Berliin: Springer.
• Hilbert, D., 1931, “Die Grundlegung der elementaren Zahlenlehre”, Mathematische Annalen, 104: 484–494.
• Howard, W., 1980, [1969], “Valemite tüübi ehituse mõiste”, J. Seldin ja J. Hindley (toim.), HB Curryle: Esseed kombinatiivsest loogikast, Lambda arvutus ja formalism, London, New York: Academic Press, lk 480–490.
• Jaskowski, S., 1934, “Umbusreeglite kohta formaalses loogikas”, S. McCall (toim.), Poola loogika 1920–1939, Oxford: Clarendon Press, 1967, lk 232–258.
• Ketonen, O., 1944, Untersuchungen zum Prädikatenkalkül, Annales Academiae scientiarum fennicae (Ser. AI 23), Helsinki.
• Kleene, S., 1952, Sissejuhatus metamaatikasse, Amsterdam: Põhja-Holland.
• Kreisel, G., 1951, “Mittefinitistlike tõendite tõlgendamise kohta: I osa”, 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, Berliin: Birkhäuser Verlag.
• Menzler-Trott, E., 2007, Logic Lost Genius: Gerhard Gentzeni elu ja töö, Providence, RI: American Mathematical Society.
• Prawitz, D., 1965, Looduslik mahaarvamine: tõestatud teoreetiline uurimus, Stockholm: Almqvist & Wiksell; kordustrükk New York: Dover (uue eessõnaga), 2006.
• –––, 1971, „Ideed ja tulemused tõestusteoorias”, J. Fenstad (toim), teise Skandinaavia loogikasümpoosioni toimetised, Amsterdam: Põhja-Holland, lk 235–308.
• Rathjen, M., 1995, “Hiljutised edusammud ordinaalanalüüsis; Π ¹ ₂ -CA ja sellega seotud süsteemid,”Sümboolse loogika bülletään, 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 matemacher Sätze, nebst einem Theoreme über dichte Mengen”, tõlgitud ja kordustrükis valitud teostes logikas, JE Fenstad (toim.), Oslo, 1970, Universitetsforlaget. lk 103–136:
• Whitehead, AN ja B. Russell, 1910–1913, Principia Mathematica, Cambridge: Cambridge University Press.

Teisene kirjandus

• Bernays, P., 1945, “Arvustus: Oiva Ketonen, Untersuchungen zum Pradikatenkalkul,” The Symbolic Logic Journal, 10 (4): 127–130.
• ––– 1965, “Betrachtungen zum Sequenzen-kalkul”, loogika ja metoodika kaastööd JM Bochenski auks, Amsterdam: Põhja-Holland, lk 1–44.
• –––, 1979, „Gentzeni originaalsuse järjepidevuse tõendusmaterjal numbriteooriale”, J. Myhill jt. (toim), intuitsioon ja tõestusteooria, Amsterdam: Põhja-Holland, lk 409–417.
• Feferman, S., 2000, “Tähtsündmused tõestusteoorias”, V. Hendricks et al. (toim.) 2000, 11–31.
• Hempel, C., 2000, “Intellektuaalne autobiograafia”. Ajakirjas Science, Selection ja Rationality, toim. J. Fetzer, lk 3–35.
• Hendricks, V., et al. (toim), 2000, Tõestusteooria: ajalugu ja filosoofiline tähtsus, Dordrecht: Kluwer.
• Mancosu, P., 1999, “Berliini ja Viini vahel: Gödeli puudulike teoreemide viivitamatu vastuvõtt”, Loogika ajalugu ja filosoofia, 20: 33–45.
• von Plato, J., 2007, “Löwenheim-Skolemi teoreemi varjudes: matemaatiliste tõendite varajane kombinatoorne analüüs”, Bulletin of Symbolic Logic, 13 (2): 189–225.
• ––– 2007, „Hilberti programmist Gentzeni programmini“, Menzler-Trott 2007, lisa.
• ––– 2009, „Gentzeni loogika”, loogika ajaloo ja filosoofia käsiraamatus (5. köide), Amsterdam: Elsevier.
• –––, 2012, “Gentzeni tõestussüsteemid: kõrvalproduktid geeniuse programmis”, Sümboolse loogika bülletään, 18 (3): 313–367.
• Smorynski, C., 2007, “Hilberti programm” lisas, Menzler-Trott 2007.
• Tait, W. 2005, “Gödeli sõnastatud Gentzeni esimene aritmeetika konsistentsi tõestus: mittemidagiütlev tõlgendus”, Symbolic Logic Bulletin, 11 (2): 225–238.
• Troelstra, A. ja Schwichtenberg, H., 2000, Basic Proof Theory, Cambridge: Cambridge University Press, 2. trükk.

Akadeemilised tööriistad

	Kuidas seda sissekannet tsiteerida.
	Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
	Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojektilt (InPhO).
	Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

[Palun võtke soovitustega ühendust autoriga.]