A HILBERT-PROGRAM

ÉS GÖDEL NEM-TELJESSÉGI TÉTELEI

SIMONYI ANDRÁS

[ Cikk vége | Irodalom | Summary | Jegyzetek | Bezárás]

1. Bevezetés

Ha elfogadjuk azt az állítást, hogy a modern értelemben vett matematikafilozófia és szimbolikus logika Gottlob Frege munkásságával kezdődött,¹ akkor valószínűleg igaz az első pillantásra paradoxnak tűnő kijelentés is, hogy a két új terület iránti érdeklődés felkeltéséhez legalább akkora mértékben járult hozzá Frege programjának (legalábbis átmeneti) kudarca, mint annak pozitív eredményei. A Russell-paradoxon (1902) és a Cantor, illetve Burali-Forti által már korábban felfedezett egyéb antinómiák ismertté válása világossá tette, hogy Frege programjának kivitelezése, nevezetesen az aritmetika (és erre támaszkodva a valós számok elmélete) fogalmainak és tételeinek megalapozása logikai, illetve ismeretelméleti analízis révén, egyáltalán nem triviális feladat. Másrészt az a lehetőség, hogy "a matematika, [...] a megbízhatóság és az igazság mintaképe abszurditásokhoz vezethet",² bizonyos gyakorlati jelentőséget is kölcsönzött Frege kérdésfeltevéseinek.

Az ellentmondások feloldására kidolgozott első javaslatok többféle módon is támaszkodtak Frege eredményeire. Egyrészt elfogadták azt az episztemológiai mozgásteret, melyet Frege (Kantra támaszkodva) a matematika ismeretelmélete számára felvázolt, amikor azt állította, hogy matematikai ismereteink vagy tisztán logikai természetűek, vagy valamiféle intuícióra, illetve tapasztalatra is támaszkodnak. Másrészt a megoldási kísérletek közül néhány felhasználta Frege legfontosabb matematikai-logikai eredményeinek egy részét is, főképp Frege logikai kalkulusát, mely az első modern értelemben vett formális rendszernek tekinthető. Így Russell Frege rendszerének továbbfejlesztésével dolgozta ki a logicizmus egy olyan változatát, melyben nem jelentkeztek sem a halmazelméleti, sem a szemantikai paradoxonok,³ míg Brouwer és követői az aritmetika tételeit a tiszta időszemléletből származtatták, azokat bizonyos mentális konstrukciók létezését állító kijelentésekként értelmezve.

Bár mind az intuicionista matematika, mind Russell ágaztatott típuselmélete mentes volt az ismert paradoxonoktól, a klasszikus matematika meggyőző igazolását célul kitűző fregei program szemszögéből mindkét megoldásnak voltak hiányosságai. Russell rendszerében már a klasszikus matematika elemi tételei is csak vitatható axiómák segítségével voltak levezethetők, az intuicionista matematikában pedig sok klasszikus eredmény rekonstruálhatatlan, vagy egyenesen cáfolható volt.

A harmadik tradicionális matematikafilozófiai irányzat megoldáskísérlete — Hilbert finitista programja — eredeti szintézist próbált létrehozni az intuicionizmus szemléletre hivatkozó episztemológiája és a klasszikus matematika logicistáktól származó deduktív rekonstrukciója között. Bár a program filozófiai hátterének megfogalmazása jelentős változásokon ment keresztül, a vállalkozás matematikai célja változatlanul egy konkrét probléma, a klasszikus matematika legfontosabb területeinek bizonyíthatóan konzisztens formalizálása maradt. Dolgozatomban a Hilbert-program fejlődését próbálom meg rekonstruálni Gödel nem-teljességi tételeivel bezárólag, melyek a tradicionális értelmezés szerint a finitista program kivitelezhetetlenségét bizonyítják.

2. Hilbert programja

2.1 A program korai vázlata

Míg a logicizmus russelli változata és az intuicionizmus egy-egy olyan álláspontot képviselt a matematikai igazságok státusával kapcsolatban, melyet — különböző korszakaiban, illetve különböző területekkel kapcsolatban — Frege is részletes vizsgálatnak vetett alá, addig a matematika megalapozásának Hilberttől eredő bizonyításelméleti programja már kívül esik a Frege által komolyan számításba vett alternatívák keretein.⁴ Hilbert a geometria első modern axiómarendszerét ismertető Grundlagen der Geometrie című művében a valós számok aritmetikájának ellentmondás-mentességét feltételezve bizonyította az ott meg-adott axiómarendszer konzisztenciáját.⁵ Egy évvel e könyv megjelenését követően javasolt egy axiómarendszert a valós számok elméletének megalapozására,⁶ és a matematikusok Párizsban rendezett konferenciáján általa felsorolt problémák közé felvette a valós számok elméletének ellentmondás-mentességét is.⁷ Mindez azt mutatja, hogy Hilbert a valós aritmetikát, melyben a relatív konzisztencia bizonyításához használt modellt megalkotta, a geometriához hasonlóan további megalapozást igénylő területnek tartotta már a halmazelméleti és logikai antinómiák megjelenése előtt is. Azt a jelentőséget azonban, melyet 1904-es, a logika és a matematika alapjairól tartott előadásában⁸ tulajdonított a probléma általa javasolt megoldásának, minden bizonnyal a Frege, Cantor és Dedekind rendszereiben kimutatott ellentmondások magyarázzák. Bár az előadásmód meglehetősen vázlatos (később maga Hilbert is kiérleletlennek minősítette első próbálkozásait), a program néhány központi eleme már ekkor megjelenik. Hilbert csak jóval később (1917-ben illetve a húszas években) tért vissza újra az ekkor felvetett problémákhoz és megoldásokhoz, azokat több ponton módosítva és részletesen kidolgozva. A javaslat első formája igazolja, hogy Hilbert — legalábbis kezdetben — a geometria megalapozása során általa alkalmazott axiomatikus módszer logikus folytatásának tekintette programját. Az előadásban megfogalmazott legfontosabb tézisek a következőkben foglalhatók össze:

(1) Mind a valós és a cantori transzfinit aritmetika (halmazelmélet), mind a természetes számok aritmetikája olyan megalapozásra, illetve igazolásra szorul, mely elkerüli az ellentmondásokat, és megvilágítja a látszólagos paradoxonok eredetét.

(2) A megalapozás módszere nem lehet kizárólag logikai. Bizonyos redukálhatatlan matematikai fogalmakat is fel kell tételezni, így például a halmaz, illetve a szám fogalmát.

(3) A megalapozáshoz elégséges megmutatni, hogy a vizsgált elméletek axiomatizálhatók és formalizálhatók oly módon, hogy az axiómákból nem lehetséges ellentmondást levezetni.

(4) Az ellentmondás-mentesség bizonyítása nem történhet egy modell megadásával, ahogyan az a geometriában szokásos, hanem csakis direkt módon.

(5) A kérdéses elméletek axiomatizált változatainak ellentmondás-mentességére ténylegesen adható direkt bizonyítás.

(1) természetesen megegyezik a logicisták helyzetértékelésével, de szembenáll mind azoknak a véleményével, akik közvetlenül adottnak és igazolásra nem szorulónak tekintik például a természetes számok fogalmát és tulajdonságait (Hilbert dogmatikusnak nevezi ezt az álláspontot, és Kroneckert tartja fő képviselőjének), mind azokéval, akik elvetik a fenti elméletek valamelyikét (itt szintén Kronecker említhető példaként). (2) a logicizmustól is elhatárolja Hilbertet, mivel azt állítja, hogy az aritmetika és a logika eszközeinek egy része együttesen szükséges a megalapozáshoz. Arra, hogy Hilbert pontosan milyen eszközökre gondol, csak következtetni lehet az általa alkalmazott módszerek, és a vállalkozás céljai alapján: az aritmetika megalapozásához nyilván nem használható a teljes aritmetika.

(3) Hilbertnek az axiomatika szerepéről vallott felfogását fejezi ki, összhangban a Fregével folytatott vitában elfoglalt álláspontjával. Új elemnek tekinthető, hogy Hilbert tudatosan a Cantortól származó konzisztens, illetve inkonzisztens sokaság megkülönböztetéshez kapcsolódik nézetei kifejtésekor. Mivel az előadás elején külön kiemeli, hogy bár Cantor felismerte az ellentmondásokat, és ezért tette meg e distinkciót, mégsem "adott precíz kritériumot a megkülönböztetéshez",⁹ ezért valószínűsíthető, hogy Hilbert az axiomatikus módszer használatával vélte pontosíthatónak e fogalmakat. A cantori terminológiát használva Hilbert azt állítja, hogy egy konzisztens axiómarendszer definiálja a benne szereplő fogalmakat, és biztosítja, hogy a rendszer által leírt tartomány konzisztens totalitásként létezik.

(4) és (5) mutatja egy alapvetően új szemléletmód megjelenését: az axiomatikus módszer használatán Hilbert nem a tradicionális értelemben vett axiomatizálást, hanem az elméletek teljes formalizálását érti. Hilbert nem definiálja, hanem egy példán mutatja be a konzisztencia direkt bizonyításának módszerét, melynek alapján szerinte könnyen konstruálható hasonló bizonyítás az (1)-ben felsorolt elméletekre is. A példa egy nagyon egyszerű formalizmust használ, amely csak a logikai konstansok, a természetes számok, a rákövetkezés, az egyenlőség és egy végtelen halmaz jeleit tartalmazza. Az axiómarendszerből, mely a Peano-axiómák egy részét és az egyenlőségre vonatkozó logikai axiómákat fogalmazza meg, helyettesítéssel és leválasztással vezethetők le következmények. A rendszer konzisztenciáját Hilbert kizárólag a formális rendszer szintaktikai tulajdonságaira hivatkozva bizonyítja: azt mutatja meg, hogy mind az axiómák, mind következményeik egy egyszerű szintaktikai tulajdonsággal bírnak, mellyel a szóba jöhető ellentmondó formulák nem rendelkeznek.¹⁰ Hilbert, miközben hangsúlyozza a bizonyítás újszerűségét, nem érvel a mellett a kijelentése mellett, hogy a "megfelelő specializáció vagy a példák konstruálásának módszere, mely egyébként használatos a hasonló bizonyításoknál — különösen a geometriában —, szükségképpen használhatatlan ebben az esetben".¹¹ E megjegyzés alapján a "direkt bizonyítás" fogalmának két lehetséges értelmezését különböztethetjük meg. Az első szerint a konzisztencia direkt bizonyítása a szintaktikai bizonyítással egyenértékű — szemben a modell megadásának szemantikai módszerével —, míg a második értelmezésben a direkt bizonyítás azt jelentené, hogy a vizsgált elmélet konzisztenciáját nem egy másik, szintén problematikus elmélet konzisztenciájára vezetjük vissza. Hilbert valószínűleg az utóbbi jelentésben használja a fogalmat, de úgy gondolja, hogy egy ilyen bizonyítás csakis szintaktikai jellegű lehet. Ebből arra következtethetünk, hogy a felhasználni kívánt matematikai illetve logikai eszközök nem adnak lehetőséget végtelen modellek konstruálására.

A legproblematikusabb és kidolgozatlanabb pont Hilbert vázlatában a megalapozni (igazolni) kívánt elméletek és az ellentmondás-mentesség bizonyításához felhasznált formális rendszerek (3)-ban említett viszonya. Hilbert következetesen interpretált elméletként kezeli a példaként felhozott formális elméletet, hiszen azt írja, hogy a jelek bizonyos gondolati tárgyakat, a jelek kombinációi pedig kijelentéseket jelölnek. A gondolati tárgyak tulajdonságai azonban tökéletesen megegyezni látszanak az őket jelölő szintaktikai objektumok tulajdonságaival. Az egyetlen jellel jelölt tárgyakat Hilbert egyszerűeknek, míg a jelek kombinációival jelölteket — mint például a kijelentéseket — összetetteknek tekinti. Paradox módon igaz ez a végtelen halmazra is: ez egyszerű objektum, szemben az 1-gyel jelölt tárgy kombinációival reprezentált természetes számokkal. E furcsa párhuzamosság valószínűleg arra vezethető vissza, hogy Hilbert nem teljesen interpretált formulák konzisztenciáját szeretné belátni (hiszen ebben az esetben elég lenne az adott kijelentések igazságértékeit megvizsgálni), de azt is el próbálja kerülni, hogy a formulák tökéletesen interpretálatlan szintaktikai objektumok legyenek, mivel objektív, logikai következtetési szabályok szempontjából vett konzisztenciát szeretne bizonyítani, és logikai viszonyok csak kijelentések között állhatnak fent. Ezen a ponton azonban fölmerül a kérdés, hogy pontosan milyen következményfogalomnak kell megfelelnie a használt formális következmény-relációnak, azazhogy milyen informális következményfogalmat kell reprezentálnia a használt formalizmusnak. Ha a modern szemantikai következményfogalomra gondolunk, akkor a konzisztencia bizonyításának feladata ekvivalens lesz annak bizonyításával, hogy az elméletnek van modellje — Hilbert azonban nem ilyen bizonyítást kíván adni. A másik lehetséges értelmezés egy a szemantikai következményfogalomnál szűkebb következmény-interpretáció lehet: például a gyakorlatban használt következtetési módok, vagy az összes számunkra lehetséges következtetési mód¹² szempontjából vizsgálhatjuk az ellentmondás-mentességet. Egy ilyen szempontból vett konzisztencia-bizonyítás viszont nem garantálja modell létezését, csak azt, hogy nem juthatunk ellentmondásra a szokásos illetve lehetséges következtetési módokat használva. Persze elképzelhető, hogy a szemantikai következményreláció megegyezik egy a gyakorlatban használt, illetve általunk alkalmazható következményrelációval, azonban ez távolról sem magától értetődő.¹³ Ezeket a problémákat a konzisztencia bizonyításának modell megadásával történő módszere természetesen elkerüli, a "direkt" eljárás meggyőző alkalmazásához azonban meg kell oldani őket.

Az eddig elmondottak alapján összefoglalhatók azok a filozófiai és matematikai feladatok, melyeket a program kielégítő továbbviteléhez mindenképpen meg kell oldani. Egyrészt pontosítani kell a felhasználható eszközök körét, érvelve amellett, hogy ezek az eszközök ismeretelméletileg kitüntetettek, tehát megbízhatóbbak, evidensebbek a megalapozandó elméletek eszközeinél. Meg kell magyarázni, hogy miért elégséges egy elmélet konzisztenciájának bizonyítása az elmélet megalapozásához, és ezzel összefüggésben tisztázni kell a formalizálandó következményreláció természetét is. Hilbert kezdeti álláspontja szerint az ellentmondásmentesség garantálja, hogy az elmélet által leírt tartomány létezik, tehát a konzisztencia biztosítja az elmélet interpretációját és igazságát. Végül kielégítő formalizációját kell nyújtani a kérdéses elméleteknek és következményrelációnak, majd a megengedett eszközökkel bizonyítani, hogy az elmélet ellentmondásmentes. A következőkben látni fogjuk, hogy a Hilbert-program érett változata az első és az utolsó feladatra az itt tárgyaltakhoz hasonló, míg a másodikra azoktól alapvetően eltérő úton keresi a megoldást.

2.2 Az érett Hilbert-program

Hilbert a húszas években megjelent írásaiban újszerű megoldást adott arra a problémára, hogy milyen módon alapozható meg egy matematikai elmélet pusztán konzisztenciájának bizonyításával. Ez a megoldás egy olyan előfeltevés elvetésével járt, amelyet mind a logicisták, mind az intuicionisták osztottak: eszerint egy elmélet igazolásához illetve megalapozásához mindenképpen meg kell adni az elmélet állításainak egy interpretációját, megmutatva, hogy tételei és axiómái teljesülnek a megadott tartományon. Hilbert ezzel szemben elégségesnek tartja az adott terület parciális interpretációját: a megalapozandó elméletekben megkülönböztet valós és ideális kijelentéseket. A valós kijelentésekhez hagyományos interpretáció rendelhető azokkal a módszerekkel, melyeket Hilbert szerint mindenképpen fel kell tételezni, míg az ideális kijelentések szerepe megegyezik azzal, amilyen szerepet az ideális elemek a matematikában játszanak: "az [...] ideális elemek előnye, hogy a rendszer összefüggéseit a lehető legegyszerűbbé és áttekinthetőbbé teszik".¹⁴ Az ideális kijelentések segítségével — éppen egyszerűsítő szerepük miatt — rövidebb és elegánsabb bizonyítások adhatók olyan valós kijelentésekre, melyek csak valós kijelentésekből álló bizonyítása rendkívül hosszú és bonyolult lenne. Az ideális elemek bevezetésének Hilbert szerint egyetlen fontos feltétele van:

"egyetlen feltétel van — de ez az egy abszolút szükséges —, melynek az ideális elemek használatának meg kell felelnie: ez a konzisztencia bizonyítása; mert az ideális elemekkel való bővítés csak akkor jogos, ha ezáltal nem keletkezik ellentmondás a régi, szűkebb tartományon, azaz ha az ideális elemek törlése után a régi elemek közt adódó relációk érvényesek az eredeti tartományon".¹⁵

A konzisztencia tehát biztosítja, hogy az ideális kijelentések használatával bizonyított valós eredmények nem fognak ellentmondani egy valós módszerekkel bizonyított eredménynek sem. Az előbbi idézet utolsó mondata azonban értelmezhető úgy is, hogy a konzisztenciánál többet követel: azt, hogy az ideális elemek használatával bizonyított valós kijelentések igazak legyenek, vagy azt, hogy csak olyan valós kijelentések legyenek bizonyíthatók a bővített elméletben, amelyek valós eszközökkel is igazolhatók (konzervatív bővítés). Bármelyik értelmezést fogadjuk is el, egy elmélet megalapozásának ilyen felfogása alapvetően instrumentalista szemléletű: azt kell igazolni, hogy az elmélet ideális része, mint instrumentum megbízható valós eredményeket szolgáltat.

Bár Hilbert megoldása a konzisztencia és a megalapozás kapcsolatának problémájára választ ad a korai program talán legfontosabb kérdésére, új feladatokat is felvet. A legsürgősebb ezek közül a megalapozni kívánt klasszikus elméletek instrumentális hasznossága melletti érvek kidolgozása. Ezek hiányában ugyanis könnyen elképzelhető, hogy bár az adott klasszikus elméletek nem vezetnek hamis valós következményekre, de fölöslegesek abban az értelemben, hogy az általuk elérhető valós eredmények ugyanolyan hatékonyan (tehát gyorsan, egyszerűen stb.) megkaphatók kizárólag valós módszerek alkalmazásával is. Az új szempontok megjelenése mellett is elmondható, hogy a korai változat centrális elemei, és ezek összefüggései változatlanok maradtak. Most röviden megvizsgáljuk, hogy az instrumentalista irányban módosított Hilbert-program milyen megoldásokat ad a korai változattól örökölt, és az újonnan felmerült problémákra.

2.3 A finit matematika

Már láttuk, hogy a program mindkét változatának lényeges részét képezte egy ismeretelméletileg kitüntetett matematikai módszercsoport illetve evidenciális alap feltételezése, melyre támaszkodva a konzisztencia bizonyítása és ezen keresztül az igazolás elvégezhető. A módosított programban erre a területre — melyet Hilbert finit matematikának nevez — hárul a részleges interpretáció feladata is. A finit matematika eszközeinek két ellentétes irányú követelménynek kell egyszerre megfelelniük. Egyrészt a lehető leggyengébb és kétségbevonhatatlanabb matematikai előfeltevéseket szabad csak felhasználniuk, hogy az igazolás valóban konklúzív legyen, másrészt viszont alkalmasnak kell lenniük a konzisztencia — esetenként egyáltalán nem triviális — tényének bizonyítására.

A "finit álláspont" legfontosabb jellegzetességének Hilbert szerint az tekinthető, hogy

"megfontolásai konkrétan adottnak feltételezett tárgyakon végzett gondolatkísérletek formáját öltik. A számelméletben a számokat, míg az algebrában bizonyos betűkből álló kifejezéseket tekintünk adottnak, melyek számegyütthatókkal vannak ellátva. [...] A számelméletben egy kiindulási tárgy, és a továbblépés folyamata adott. Mindkettőnek határozottan rögzítve kell lennie szemléletileg. A rögzítés különös módja lényegtelen, de a választást a teljes elméletre nézve meg kell tartani."¹⁶

A fenti idézet alapján a finit matematika legalapvetőbb sajátosságainak a konstruktivitást és a konstrukciók, illetve a konstrukciók alapjául szolgáló tárgyak áttekinthetőségét és ebből adódó végességét nevezhetjük. Bár mindezekkel a tulajdonságokkal az intuicionista matematikafelfogás is rendelkezik, két jelentős eltérés is említhető az irányzatok között. Az első, hogy a finitista megközelítés a tanulmányozott konstrukciókat nem tartja szükségszerűen mentális természetűnek, a felhozott példák általában interszubjektív konstrukciók, jelkombinációk típusai. A második, hogy a vizsgált tárgyak az intuicionizmusban lehetnek intencionális jellegűek is, például propozíciók, bizonyítások (ezt jól mutatja a logikai konstansok intuicionista értelmezése), míg a finitista matematika ezeket csak mint szintaktikai objektumokat vizsgálhatja. A konzisztencia bizonyítására való alkalmasság követelményének megfelelően a finit matematika keretei között mód kell nyíljon bizonyos típusú univerzális állítások igazolására is, hiszen egy elmélet konzisztenciájának állítása ekvivalens egy egzisztenciális állítás tagadásával. Ennek megfelelően a finit módszerek között (az intuicionista interpretációhoz hasonló megfontolások alapján) Hilbert helyet biztosít a paradigmatikus esetre történő bizonyításnak is, a teljes indukciót ennek egy változataként értelmezve.

A finit matematika által tanulmányozott konstrukciók, illetve konstrukciós eljárások tulajdonságai közül ismeretelméleti szempontból a végesség a legalapvetőbb, mivel ez biztosítja, hogy a gondolatkísérletekben olyan tárgykombinációkkal foglalkozunk, amelyek elvben az általunk tapasztalható valóságban is előfordulhatnak, és olyan eljárásokat használunk fel a konstrukció során, melyeket elvben mi is végrehajthatnánk véges sok lépésben. Ennek megfelelően Hilbert a finit matematika ismeretelméleti státusát műveiben mindig egy-egy a tapasztalat végességét és kitüntetettségét hangsúlyozó filozófiai irányzat terminológiájával próbálja meg leírni. A korai művekben ez a filozófia a kantianizmus, míg később inkább a logikai pozitivizmus elemei dominálnak. Közös vonása a két irányzatnak, hogy mindkettő éles határvonalat húz azok között a dolgok illetve szituációk között, melyek elvben tárgyai lehetnek egy tapasztalatnak, és azok között, melyekről elvileg sem lehetséges tapasztalatot szerezni. Hilbert az ideális elméletekben szereplő, aktuális végtelenre vonatkozó kijelentések igazságtartalmát természetesen az utóbbi kategóriába sorolja, sőt azt állítja, hogy az aktuális végtelen nem csupán a tapasztalatban, de még a modern fizikai világképben sem található meg, mivel mindkettő alapvetően diszkrét és véges.¹⁷ Bár az ideális (nem tapasztalati) kijelentések státusát Hilbert más-más módon interpretálja a kantiánus illetve az empirista keretben, közös a két interpretációban az ilyen kijelentések problematikussága, mind igazságtartalmukat, mind a belőlük a tapasztalati tényekre levonható következtetéseket illetően. A kantiánus ismeretelméleti modellen belül Hilbert az aktuális végtelenre hivatkozó ideális kijelentések státusát a kanti észideákról tett kijelentések analógiájára értelmezi:

"A végtelen számára maradó szerep inkább pusztán egy idea szerepe — ha Kant szavaival összhangban ideán egy olyan észfogalmat értünk, mely minden tapasztalaton túl van és melyen keresztül a konkrét befejezett totalitást alkot."¹⁸

Hilbert a logika szerepét is kanti szellemben interpretálva amellett érvel, hogy a logika bármilyen tartalmas használatának előfeltétele, hogy a vizsgált tartalom a szemléletben adott legyen (ezért volt Hilbert szerint Frege logicista kísérlete kudarcra ítélve), és ezért az ideális kijelentésekre nem alkalmazhatók a logika törvényei a valós kijelentéseknél megszokott, tartalmas módon.¹⁹ Egy kantiánus ismeretelmélet természetesen a finit matematika kitüntetettségét is könnyen biztosíthatja a tiszta szemléletre való hivatkozással.

A neokantiánus szemléletű írásoknál jóval későbbi (1934-ben megjelent) Grundlagen der Mathematik I. kötetének logikai pozitivista modelljében²⁰ az ideális matematikai elméletek státusa lényegesen közelebb kerül az empirikus tudományokhoz, különösen a fizikához. Itt a fizikai elméletek a véges és diszkrét tapasztalat idealizáló és egyszerűsítő extrapolációiként jelennek meg, melyeknek nem szabad ellentmondásba kerülniük a rendelkezésre álló érzetadatokkal vagy megfigyelési állításokkal. Mivel a fizikai elméletek felhasználják a matematika bizonyos eredményeit és fogalmait, ezért elengedhetetlen, hogy az alkalmazott ideális matematikai elméletek a maguk részéről ne vezethessenek ellentmondásra. Az ideális matematikai elméletek ebben a felfogásban tulajdonképpen a véges tapasztalat bizonyíthatóan megbízható tudományos extrapolációinak tekinthetők.²¹ Bár az instrumentalista szemlélet jóval explicitebb a későbbi írásokban, Hilbert már az érett program kezdeményezésekor is a hasznosságot tekinti az ideális elméletek létjogosultságát biztosító legfontosabb feltételnek. A kanti ismeretelméleten belüli lokalizáció inkább az instrumentális hasznosság antropológiai magyarázatául szolgál.

A finitizmus követelményeinek megfelelő tartalmas matematikai elméletek között kitüntetett szerep illeti meg a finit vagy elemi számelméletet, mivel ennek az (informális) területnek a segítségével adható az ideális elemeket is tartalmazó elméletekre részleges interpretáció. A megalapozni kívánt elméleteket Hilbert úgy tekinti, mint amelyek a finit számelmélet ideális kijelentésekkel bővített változatai. Ennek megfelelően a klasszikus számelméletben — mely a legegyszerűbb az iskola által vizsgált klasszikus területek között — Hilbert jelentéssel rendelkezőnek tekinti az eldönthető predikátumok számokra történő alkalmazásával kapható atomi kijelentéseket, tagadásukat és az ezek igazságfüggvények alkalmazásával nyerhető kombinációit. Az így kapható kijelentések mindegyike eldönthető, és érvényesek rájuk a klasszikus logika azon alaptörvényei is, melyek általános érvényét az intuicionisták tagadták (tehát például a kizárt harmadik elve). Ezeket a kijelentéseket nevezhetjük szigorúan finit állításoknak. A finit szemszögből problematikus mondatok közé a "transzfinit szimbólumokat", vagyis kvantorokat tartalmazók tartoznak, mivel ezek aktuálisan végtelen sokaságokra utalnak. Hilbert az ilyen típusú állítások közül egyedül a śx₁,..,śx_kA(x₁,..,x_k) alakú kijelentéseket sorolja a valósak közé, ahol A eldönthető predikátumot jelöl. Ezek a mondatok finitista értelmezés szerint hipotetikusak: egy törvényt mondanak ki, mely szerint ha adott a₁,..,a_k, akkor A(a₁,..,a_k) teljesülni fog. A hipotetikus értelmezés lehetőségének formális szempontból az felel meg, hogy az ilyen kijelentések kvantorok nélküli, csak szabad változókat tartalmazó sémákkal is reprezentálhatók, melyek akkor igazak, ha a változók bármely helyettesítése esetén igaz mondatot kapunk. Az univerzális kijelentések bizonyítására szolgáló legfontosabb számelméleti eszköz, a teljes indukció használható a finit keretek között is, természetesen eldönthető predikátumokra megszorítva. Bár az egzisztenciális kvantort tartalmazó mondatok bizonyos esetekben szintén értelmezhetők konstruktívan (parciális ítéletekként, melyeknek teljes alakja megad egy megfelelő tulajdonságú számot, vagy egy eljárást ilyen számok előállítására),²² Hilbert ezeket az ideális elemek közé sorolja, mint általános esetben eldönthetetlen végtelen alternációkat.

A valós mondatok így definiált halmaza nem zárt a negációképzésre nézve, és ezért ezen a területen nem érvényesülnek a klasszikus logika azon törvényei, melyek a szigorúan finit kijelentésekre még teljesültek. Éppen ez a helyzet teszi elengedhetetlenül szükségessé Hilbert szerint az ideális mondatok bevezetését:

"A finit kijelentések tartományán [...] érvényesülő logikai kapcsolatok rendkívül nehezen áttekinthetők [...] a logikai törvények, melyeket az emberiség azóta használ, mióta gondolkodni kezdett — Arisztotelész törvényei —, nem teljesülnek. Persze megpróbálhatnánk meghatározni a finit kijelentések tartományán érvényes logikai törvényeket, de ez sem segítene, mert nem kívánjuk feladni az arisztotelészi logika egyszerű törvényeinek használatát, és senki sem tarthatja vissza az embereket — szóljon bár az angyalok nyelvén — attól, hogy tetszőleges kijelentések tagadásait és részleges ítéleteket fogalmazzanak meg, vagy hogy használják a kizárt harmadik elvét."²³

Az ideális kijelentések használatával tehát visszaállítható a szigorúan finit területen érvényesülő egyszerű szabályok érvényessége. Ez egyben Hilbert legfontosabb érvének tekinthető az ideális elméletek instrumentális hasznossága mellett. Az ideális módszereknek és a klasszikus logika következtetési módjainak a valósakhoz viszonyított egyszerűsége és hatékonysága természetesen további indoklásra szorulhat. Hilbert írásaiban empirikus tényként fogadja el, hogy a matematikával foglalkozók gyakran egyszerűbbnek találják és előnyben részesítik ugyanazon valós állítások ideális bizonyításait a csak valós eszközöket alkalmazókkal szemben. Másrészt valószínűsíthető, hogy mélyebb, antropológiai okokat is látott e preferenciák mögött, amelyek mind a kantiánus felfogásban, mind a késői Grundlagen modernebb fogalmi keretében elhelyezhetők: az utóbbi esetben esetleg a természetes kiválasztódás folyamatára hivatkozva, mely alapvetően a szigorúan véges tartományokkal kapcsolatos következtetésekre kellett hogy alkalmassá tegyen minket.²⁴

Az ideális és reális kijelentések közt meghúzott választóvonal ismeretében értelmezhető a konzisztencia és az instrumentális megbízhatóság kapcsolata is. Az könnyen látható, hogy ha egy ideális I elmélet (1) konzisztens és (2) bizonyítható benne az összes szigorúan finit igaz kijelentés, akkor csak helyes valós eredményeket szolgáltathat. A szigorúan finit kijelentések esetében ez nyilvánvaló. Ha viszont bizonyítható lenne I-ben egy hamis a śx₁,..,śx_kA(x₁,..,x_k) szerkezetű valós kijelentés, akkor (2) miatt bizonyíthatónak kellene lennie egy ~A(n₁,..,n_k) alakúnak is, ahol A argumentumai természetes számok. Ez azonban természetesen inkonzisztenciához vezet, ha feltételezzük, hogy I-ben alkalmazhatók a klasszikus elsőrendű logika következtetési szabályai. Tehát az ellentmondás-mentesség valóban biztosítja a tökéletes instrumentális megbízhatóságot.

Az ideális bővítés konzervativitásának kérdése már jóval összetettebb probléma annak helyességénél. Hilbert minden bizonnyal úgy gondolta, hogy az ideális kijelentések segítségével bizonyítható valós kijelentések bizonyíthatók kizárólag az adott elmélet valós kijelentéseinek használatával is. Emellett szól, hogy a konzisztencia bizonyításának hilberti stratégiája a transzfinit szimbólumokat tartalmazó bizonyítások valós bizonyításokba való transzformációján alapult (?-elimináció), és hogy mind ő, mind a Hilbert-program más résztvevői gyakran beszélnek úgy az ideális bizonyításokról, mintha azok egyszerűen a valós bizonyítások rövidített, egyszerűsített változatai lennének.²⁵

2.4 A formalizáció szerepe

Bár a Hilbert-programban központi szerepet játszottak bizonyos formális rendszerek vizsgálatai, a formalizált elmélet mai fogalma — mely többek között előfeltételezi az algoritmikus eldönthetőség szabatos definícióját is — az érett program megfogalmazásakor még nem állt rendelkezésre. A program azon követelménye, hogy a vizsgált ideális terület konzisztenciáját finit eszközökkel kell bizonyítani, természetesen szükségessé tette a megalapozandó elmélet kijelentéseinek, axiómáinak és bizonyításainak finit matematikai reprezentálhatóságát. Ezt a célt szolgálta finit objektumokká, jelkombinációkká történő transzformációjuk, és a következtetések formális operációkká történő redukciója. Mivel az informális ideális elméletek finit eszközökkel kezelhető reprezentációi modern értelemben vett formális rendszerek voltak, ezért fogalmazhatunk úgy, hogy a program a matematika vizsgált területeinek, illetve módszereinek formalizációját igényelte.

Az érett program az instrumentalista szemléletnek megfelelő választ ad arra a korai változattal kapcsolatban már említett kérdésre, hogy a finit reprezentációnak milyen informális következményfogalmat kell formalizálnia. Hilbert egyértelműen a megalapozni kívánt elmélet sikeres és elfogadott matematikai gyakorlatában használt bizonyítási módszerek szempontjából vett konzisztenciát vizsgálja:

"Gondosan tanulmányozni fogjuk a fogalomalkotás és a bizonyítás gyümölcsöző módszereit; ápolni, támogatni fogjuk ezeket, és használhatóvá tesszük őket minden olyan esetben, ahol a leghalványabb esély van a sikerre."²⁶

Az érett program szemszögéből tehát az ideális kijelentésekre vonatkozó levezetési módszerek, és az ezeket leíró logikai kalkulus ugyanúgy a vizsgált elméletek ideális alkotóelemeit képezik, mint az ideális kijelentések, és együtt vizsgálandók a valós megbízhatóság szempontjából. Így Hilbert mint a megalapozni kívánt matematikai területek szerves részét használja fel az elsőrendű predikátumkalkulust is, amit a matematikai gyakorlatban használt következtetések helyes reprezentációjának tekint. Ez a tény rávilágít arra, hogy bár a konzisztencia bizonyításának szempontjából célszerű különbséget tenni a megalapozni kívánt "informális" ideális elmélet, és ennek formális, finit eszközökkel vizsgálható szintaktikai reprezentációja között, valójában már a Hilbert által vizsgált ideális elméletek elfogadott matematikai gyakorlata is megkövetelte a formalizálhatóságot (sőt bizonyos esetekben az aktuális formalizáltságot) az előfeltevésmentesség és a matematikai szigor korabeli normáinak megfelelően. Hilbert ezért általában a vizsgált ideális elméletek széles körben elfogadott axiomatizációinak formális nyelvi fordításait egészítette ki egy logikai kalkulussal, ezt tekintve az adott ideális elmélet adekvát reprezentációjának. Mivel a rendelkezésre álló logikai kalkulusok általában a logicisták által konstruált, a lehető legkevesebb levezetési szabályt tartalmazó rendszerek voltak, ezért állítható, hogy Hilbert elfogadta a logicista alapkutatás egyik legfontosabb eredményét, bár azokat nem a valódi, tartalmas logika, hanem a gyakorlat logikája helyes leírásának tekintve.

2.5 Eredmények az érett program megvalósításában

Bár a húszas évek folyamán Hilbertnek és munkatársainak sikerült bizonyos formális rendszerek konzisztenciáját finit módszerekkel bizonyítaniuk, ezek a rendszerek a klasszikus aritmetika, illetve analízis axiómáinak és levezetési szabályainak csak egy részét tartalmazták. Így Ackermann 1924-es bizonyítása²⁷ az analízis konzisztenciájára megszorításokat tartalmazott az alkalmazható helyettesítésekre nézve és Neumann 1927-ből,²⁸ valamint Herbrand 1931-ből származó bizonyításai²⁹ az aritmetika konzisztenciáját olyan formalizmusokra mutatták meg, melyek az indukció alkalmazását csak kvantorokat nem tartalmazó formulákra engedélyezték.

A konkrét eredmények megszületésével párhuzamosan fontos változások következtek be a program legcélszerűbb kivitelezésének módszerére vonatkozó nézetekben, és precízebbé vált a finit matematika, illetve számelmélet fogalma is. Az utóbbit egyre inkább az először Skolem által 1923-ban tanulmányozott primitív rekurzív aritmetikával³⁰ kezdték azonosítani, melynek formulái — Hilbert elvárásainak megfelelően — nem tartalmazhattak kötött változókat, viszont a kvantorok hiányát a primitív rekurzív függvények és predikátumok definiálásának lehetősége, valamint a teljes indukció primitív rekurzív predikátumokra való alkalmazhatósága kompenzálta. Megfelelően definiált primitív rekurzív függvények, illetve predikátumok segítségével ugyanis lehetőség nyílik a rendszerben olyan kijelentések kifejezésére, melyekben a kvantorok véges tartományokra vonatkoznak. A valós kijelentések finitista interpretációjával összhangban a primitív rekurzív aritmetika tételei olyan kijelentések vagy kijelentéssémák, melyek verifikálhatóak, tehát a kijelentések, és a sémák különböző helyettesítései a rekurzív definíciók feloldása után ellenőrizhetően igaz finit kijelentésekbe mennek át. Szintén megfelel az általános kijelentések konstruktív értelmezésének, hogy egy séma bizonyítása egyúttal a sémából helyettesítéssel nyerhető minden egyes kijelentés szigorúan finit bizonyításának sémáját is adja. A primitív rekurzív aritmetika azon tulajdonságát felhasználva, hogy minden levezethető formula verifikálható, könnyen igazolható az ilyen rendszerek konzisztenciája is, hiszen ezek szerint például a '0=1' nem szerepelhet a tételek között.³¹

A program végrehajtási tervében történt fontos változásnak tekinthető az elsőrendű elméletek, ezek közül is a klasszikus számelmélet középpontba kerülése. Míg Hilbert korábbi írásai az analízis és a halmazelmélet konzisztenciáját is finit módszerekkel próbálták meg igazolni, addig a Grundlagen der Mathematik első kötete csak a klasszikus aritmetikára nézve tartja szükségesnek az ellentmondás-mentesség finit bizonyítását. A többi megalapozni kívánt formális rendszer ellentmondástalanságát a klasszikus számelméletben megalkotott modellekkel, tehát relatív konzisztencia-bizonyítással kívánták bizonyítani. A klasszikus számelmélet axiómarendszere Hilbert és Bernays szerint

"olyan áttekinthető szerkezettel rendelkezik, hogy ellentmondástalanságát [...] be tudjuk bizonyítani, másrészt viszont olyan gazdag, hogy kielégíthetőségének feltételezésével [...] levezethető a geometriai és fizikai tudományok axiómarendszereinek kielégíthetősége is".³²

Érdekes kérdés, hogy milyen megfontolások támaszthatják alá azt a feltételezést, hogy a klasszikus számelméletben modell adható az analízis illetve a halmazelmélet axiómarendszereire. A Grundlagen szerzői valószínűleg a Löwenheim—Skolem tételre, valamint az elsőrendű kalkulus Gödel által 1930-ban bizonyított teljességére³³ alapozhatták feltételezésüket. Ennek a két tételnek együttesen következménye, hogy minden konzisztens elsőrendű formulahalmaznak van modellje a természetes számok halmazán, sőt az is igazolható, hogy mindig létezik olyan modell is, melynek predikátumai aritmetikai predikátumok.³⁴ Ez a tétel azonban természetesen gyengébb annál az állításnál, hogy minden konzisztens elsőrendű elmélet tételeinek megadható olyan aritmetikai fordítása, mely az adott elmélet minden tételéhez a Peano által axiomatizált aritmetika egy-egy tételét rendeli, mivel az elsőrendű Peano-aritmetika nem teljes (és nem is bővíthető teljessé), tehát nem áll az, hogy minden igaz aritmetikai formula tétel volna. A relatív konzisztencia bizonyításához azonban az utóbbi teljesülése is szükséges lenne.³⁵

Az elsőrendű kalkulus teljességének bizonyítását gyakran szokták a Hilbert-program szerves részét képező eredménynek tekinteni más szempontból is. E szerint az értelmezés szerint Gödel szabatos logikai eszközökkel bizonyította, hogy egy matematikai fogalom (objektum) létezéséhez elégséges, hogy a fogalom létezésének feltételezése ne vezessen ellentmondásra. Valójában azonban Hilbert finitista megközelítésében a teljességi tétel, mely nem csak konstruktív eszközöket használ (például alkalmazza a König-lemmát), ideális eredmény, és csak akkor fogadható el helyesnek, ha a felhasznált eszközök konzisztenciája már finit módszerekkel bizonyított. A teljességi tétel bizonyításában konstruált struktúrák létének elfogadása tehát előfeltételezi a természetes számok halmazának létezőként való elfogadását. Ez utóbbi feltevés viszont — legalábbis a Hilbert-program szemszögéből — csakis egy finitista konzisztencia-bizonyításra és arra hivatkozhat, hogy a konzisztencia elégséges feltétele a fogalom (vagy modell) létezésének. Ezért a teljességi tétel nem alapozhatja meg a konzisztencia és a kielégíthetőség kapcsolatát, bár — mint Hilbert és Bernays írja a szemantikai megfontolásokról — hasznos heurisztikus segédeszköze lehet a finit módon is bizonyítható eredmények kutatásának.³⁶

3. Gödel nem-teljességi tételei

Herbrand konzisztencia-bizonyításával azonos évben, 1931-ben jelent meg Gödel írása a "Principa Mathematica és hasonló rendszerek formálisan eldönthetetlen állításairól".³⁷ A cikkben található legfontosabb eredmények — bizonyítás nélkül — egy rövid közleményben már 1930-ban bejelentésre kerültek.³⁸ Az írásokban szereplő metamatematikai tételek közvetetten Gödelnek abból a sikertelen próbálkozásából eredtek, hogy a Hilbert-programmal összhangban megpróbálja az analízis relatív konzisztenciáját bizonyítani a klasszikus számelmélethez képest. Mint Wang írja:

"[Gödel] a valós számokat számelméleti formulákkal reprezentálta, és úgy találta, hogy az analízis helyettesítési axiómájának igazolásához fel kell használnia a számelméleti mondatok igazságának fogalmát. Hamarosan az igazsággal és definiálhatósággal összefüggő paradoxonokba ütközött (különösen a Hazug és a Richards paradoxonba). Felismerte, hogy terve kivitelezhetetlen, mivel a számelméleti igazság nem definiálható a számelméletben."³⁹

Feferman nyomán a következőképpen rekonstruálhatjuk a gondolatmenetet:⁴⁰ Gödel valószínűleg egy olyan másodrendű aritmetikával reprezentálta a valós számok elméletét, ahol a halmazváltozók az elsőrendű aritmetikában definiálható halmazokat vehettek fel értékül. Mivel az elsőrendű aritmetikában csak számok fölött lehet kvantifikálni, ezért logikus lépés, hogy az egy szabad változót (például x-et) tartalmazó formulákat megszámozzuk, és a halmazok fölötti kvantifikációt ily módon a természetes számok fölötti kvantifikációként interpretáljuk. A másodrendű számelmélet eleme relációjának elsőrendű aritmetikai fordítása így egy olyan kétargumentumú predikátum lenne, mely akkor és csak akkor igaz egy m, n párra, ha az m sorszámú formulában x helyére n-et helyettesítve igaz formulát kapunk. Az eleme reláció aritmetikai fordításához tehát az igaz formula vagy a kielégítés fogalmának elsőrendű aritmetikai definiálhatóságára lenne szükség. Azonban éppen az igazság és a definiálhatóság fogalmával kapcsolatban lépett föl a legtöbb szemantikai paradoxon. Miután Gödel meggyőződött róla, hogy az igazság vagy kielégítés aritmetikai kifejezhetőségét feltételezve valóban rekonstruálhatók egyes paradoxonok (a Richards által is alkalmazott diagonális módszerrel), levonta a következtetést, hogy ezek kifejezhetetlenek a rendszeren belül. Mivel viszont a bizonyíthatóság, illetve a levezethető kielégítés már definiálható az elsőrendű aritmetikában, ezért megállapítható, hogy az igaz mondatok és a levezethető mondatok halmaza nem eshet egybe. Ezért ha a vizsgált rendszer helyes, akkor szükségképpen lesznek eldönthetetlen állítások.

Gödel az előbbi informális megfontolásokat úgy tette precízzé és még finitista szempontból is elfogadhatóvá, hogy a rendszer helyességének szemantikai feltételét az w-konzisztencia szintaktikai feltételével helyettesítette, és a diagonális módszernek a bizonyíthatóságra történő alkalmazásával konkrét eldönthetetlen mondatot konstruált (első nem-teljességi tétel). Később felismerte, hogy mivel az eredmény igazolásához elégségesek a klasszikus aritmetika módszerei, ezért a teljes bizonyítás formalizálható magában a vizsgált rendszerben is. Ebből adódóan, ha a konzisztencia aritmetikai fordítása levezethető lenne, akkor levezethető lenne az eldönthetetlen mondat is. Tehát a formalizált aritmetika konzisztenciáját kifejező mondat nem lehet igazolható a vizsgált formális rendszerben (második nem-teljességi tétel).

Bár Gödel eredményeit kezdetben nem értelmezte úgy, hogy azok a Hilbert-program (eredeti formában történő) kivitelezhetetlenségét vagy egyes feltételezéseinek hibás voltát igazolják,⁴¹ később ez az interpretáció — különösen a második nem-teljességi tétel vonatkozásában — szinte kizárólagosan uralkodóvá vált. Hilbert már 1934-ben, a Grundlagen der Mathematik első kötetének rendkívül rövid bevezetésében szükségesnek találta megjegyezni, hogy "az a jelenleg elterjedt nézet, mely szerint Gödel bizonyos újabb eredményeiből bizonyításelméletem kivitelezhetetlensége következik, tévesnek bizonyult".⁴² A következőkben megvizsgáljuk, hogy a két nem-teljességi tétel milyen pontokon kérdőjelezheti meg az érett Hilbert-program bizonyos matematikai, illetve filozófiai feltevéseit.

3.1 Az első nem-teljességi tétel és a Hilbert-program

A Gödel által kimondott első nem-teljességi tételt — attól eltekintve, hogy az eredeti változat nem elsőrendű nyelvet használt, hanem a Principa mathematica formális nyelvének egy változatát⁴³ — a következőképpen fogalmazhatjuk meg:⁴⁴

Legyen L egy klasszikus elsőrendű nyelv a 0 konstansjellel és az S egyargumentumú, valamint a +, H kétargumentumú függvényjelekkel. Ekkor (G1) ha P egy L nyelvű elsőrendű elmélet, mely (1) axiomatizálható, (2)  w-konzisztens és (3) tételként tartalmazza a klasszikus aritmetika összes igaz S₀ mondatát, akkor P nem teljes. Speciálisan P-ben eldönthetetlen⁴⁵ egy śxA(x) alakú formula, ahol A eldönthető predikátum.

Rosser 1936-ban megmutatta,⁴⁶ hogy ha a (3) feltételben azt kötjük ki, hogy P tartalmazza Q-t (az elsőrendű Peano-aritmetika egy R. M. Robinsontól származó részelméletét), akkor (2)-ben elég a puszta konzisztenciát megkövetelnünk P nem-teljességének bizonyításához:

(GR) Ha P egy L nyelvű elsőrendű elmélet, mely (1) axiomatizálható, (2) konzisztens (3) tételként tartalmazza Q összes tételét, akkor P nem teljes. Speciálisan P-ben eldönthetetlen egy śxA(x) alakú formula, ahol A eldönthető predikátum.

Az első nem-teljességi tétel itt bemutatott változatai Gödel eredeti tételével megegyezően egy konkrét nyelven megfogalmazható elméletekre lettek kimondva. Azonban Gödel már az eredmény bejelentésekor hangsúlyozta, hogy a tétel valódi tartalma ennél jóval általánosabb, és a klasszikus matematika formális rekonstrukciójára alkotott más rendszerekre (többek között a halmazelmélet Zermelo, illetve Neumann által alkotott axiómarendszereire) is érvényes. Általánosságban valószínűsíthető, hogy a fenti tételek megfelelően módosított változatai minden olyan effektív eszközökkel kezelhető formális rendszerre nézve bizonyíthatók, mely tartalmazza az elsőrendű Peano-aritmetika kijelentéseinek megfogalmazásához és bizonyításához szükséges eszközöket. Effektíven kezelhetőnek tekinthetünk egy formális rendszert abban az esetben, ha kifejezései egy véges ábécé betűinek véges sorozatai, és algoritmikusan eldönthető minden kifejezésről, hogy beletartozik-e bizonyos kategóriákba (pl. mondat, nyitott mondat, változó, axióma, bizonyítás) vagy hogy bizonyos szintaktikai relációk fennállnak-e köztük (pl. p bizonyítás s kijelentést bizonyítja, s mondat p nyitott mondatból v változó helyére n természetes szám helyettesítésével nyerhető). Ennek alapján (GR) egy némileg általánosított és erősen informális változata fogalmazható meg:

(GR*) Legyen S egy effektív eszközökkel kezelhető formális rendszer, melyben megfogalmazhatók a természetes számokról az L nyelven tehető kijelentések és az összes L-ben kifejezhető aritmetikai tulajdonság és reláció. Ha S-ben bizonyítható az elsőrendű Peano-aritmetika összes tételének fordítása,⁴⁷ és megengedettek az elsőrendű következtetések S-beli megfelelői, akkor amennyiben S konzisztens, nem lehet teljes. Speciálisan S-ben eldönthetetlen egy śxA(x) alakú kijelentést kifejező formula, ahol A eldönthető predikátum.

Bár hasonló módon (G1) is általánosítható lenne, valószínűleg (GR*) a legalkalmasabb arra, hogy a Hilbert-program szempontjából felmerülő problémákat felvesse. Az első feltehető kérdés természetesen az lehet, hogy következik-e (GR*)-ból a klasszikus aritmetikát tartalmazó ideális elméletek konzisztens finit reprezentációinak elkerülhetetlen nem-teljessége. Erre a kérdésre minden valószínűség szerint igenlő választ kell adnunk. Egyrészt az effektív kezelhetőség mindenképpen szükségesnek látszik ahhoz, hogy a rendszer egy ideális elmélet finit reprezentációjának legyen tekinthető. Másrészt a formalizálandó ideális elméletek mindegyike ki képes fejezni az aritmetika kijelentéseit és relációit, alkalmazhatók benne az elsőrendű következtetések megfelelői, és tételként tartalmazza a Peano-axiómákból levezethető tételek fordításait. Ennél jóval nehezebben dönthető el (GR*) igazságának kérdése. Mindenképpen fontos mellette szóló érv lehet, hogy ha elfogadjuk a Church-tézist és feltételezzük, hogy a rendszer kifejezései kölcsönösen egyértelműen leképezhetők a természetes számok egy rekurzív halmazára, akkor (GR*) feltételei szabatosan megfogalmazhatók, és így (GR*) bizonyítható matematikai állítássá alakítható.⁴⁸ Mivel (GR*) igazsága ily módon összefüggésbe hozható a Church-tézis igazságával, ezért az utóbbi mellett felhozható tipikus érvek (GR*) mellett is szólnak. Így elmondható, hogy az eddig ismert effektíven kezelhető rendszerek esetében az állítás kivétel nélkül igaznak bizonyult, és hogy az effektív számítási folyamatok különböző analízisei is támogatják a tételt. Ha azt is figyelembe vesszük, hogy a finit számelmélet eszközeit a Hilbert-iskola a primitív rekurzív aritmetikával azonosította, és hogy a finit matematika objektumai reprezentálhatóak természetes számokkal,⁴⁹ akkor jó alapunk van azt állítani, hogy a finit eszközökkel kezelhető formalizmusoknak az effektivitás rekurzív értelmében is effektíven kezelhetőknek kell lenniük. A fentiek alapján tehát arra következtethetünk, hogy (GR*) igaz, és érvényes az ideális elméletek finit reprezentációira.

Az ideális elméletek konzisztens formális reprezentációinak szükszégszerű nem-teljességét feltételezve a Hilbert-program több implicit feltevése is problematikussá válik. Az ellenvetések első típusának közös premisszája, hogy a konkrétan megkonstruálható eldönthetetlen mondat a szándékolt interpretációban igaz, és hogy igazsága könnyen be is látható. Ennek alapján először is felvethető, hogy a (G1) alapján konstruálható w-inkonzisztens, de konzisztens elméletek cáfolják Hilbert tételét, mely szerint egy elmélet konzisztenciája garantálja az elmélet által leírt fogalom létezését a szándékolt tulajdonságokkal.⁵⁰ Ebből az következne, hogy nem elég egy elmélet konzisztenciáját bizonyítani az elmélet igazságának illetve "valódi ellentmondástalanságának" bizonyításához. Megállapítható, hogy ez a kritika legfeljebb a Hilbert-program korai változatával szemben állja meg a helyét, mivel az érett program nem a szándékolt modellen való igazságot, hanem csak a valós helyességet (esetleg adekvátságot) tartja a konzisztenciából következőnek, és a formális reprezentációtól nem az igazság, hanem a gyakorlat reprezentációját várja el. Azt is érdemes megjegyezni, hogy a kérdéses mondatok igazsága akkor látható be könnyedén, ha feltételezzük a kérdéses formális rendszer (?-) konzisztenciáját, illetve helyességét, márpedig éppen ez igényel részletes bizonyítást finit szemszögből.

Komolyabb akadályt jelenthet a Hilbert-program kivitelezhetőségének szempontjából az eldönthetetlen mondat igazságánál annak feltételezett beláthatósága. Hogyha ugyanis elfogadjuk, hogy egy vizsgált ideális elmélet gyakorlatában (például mert (GR*) konkrét alkalmazása része annak) az informális elmélet bármely helyes finit reprezentációjához található olyan kijelentés, mely az ideális elméletben bizonyítható vagy belátható, de a reprezentáló rendszerben nem levezethető, akkor az ideális elmélet nem lehet teljesen reprezentálható egy formális elmélettel, és így megalapozható sem. A finitista program védelmezője számára két stratégia kínálkozik e probléma megoldására. Először is tagadhatja, hogy a megalapozni kívánt ideális elméletek gyakorlatának része lenne (GR*) alkalmazása a gyakorlat egy részét helyesen reprezentáló formalizmusokra. Bár ezt teheti egyszerűen az "empirikus adatokra" hivatkozva is (a számelmélet tételei közé nem szokták felvenni a nem-teljességi tételek alapján konstruált eldönthetetlen mondatokat), hivatkozhat a tudományos szigor követelményeire is, azt állítva, hogy a helyes tudományos gyakorlatnak nem lehet része a gödelizáció. Érvelhet amellett is, hogy az ideális elméletek nem egy standard modellt, hanem egy olyan axiomatizálható struktúraosztályt vizsgálnak, melyen bizonyos mondatok nem dönthetők el.

A második lehetséges stratégiát követve a hilbertiánus elismerheti, hogy az ideális elméletek teljes gyakorlata nem reprezentálható finit módon, és úgy módosíthatja a Hilbert-programot, hogy az csak az ideális gyakorlat egy részének instrumentális megbízhatóságát próbálja megalapozni. Tipikus választás lehet az ideális elmélet már ismert és klasszikus eredményeinek igazolásához szükséges bizonyítási módszerekre és tételekre korlátozni az instrumentális megbízhatóság igazolásának célkitűzését. Ez a lépés természetesen megfosztja a Hilbert-programot az ideális elméletek "egyszer és mindenkorra" történő megalapozásának lehetőségétől, nagymértékben csökkentve annak a szkeptikusokkal szembeni meggyőző erejét. Különösen Kreisel és Prawitz hangsúlyozta Gödel első nem-teljességi tételének azt a következményét a programra nézve, hogy meggyőzően le kell határolnia a gyakorlat egy bizonyos részét, melyet igazolni kíván.⁵¹

A finit reprezentációk nem-teljességéből eredő eddig említett problémák függetlenek voltak attól, hogy a formálisan eldönthetetlen mondatok a megalapozandó elméletek ideális, vagy valós, interpretálható részéhez tartoznak-e. Azonban újabb kérdéseket vethet fel az a tény, hogy a nem-teljességi tétel bizonyításakor konstruált formulák valós kijelentéssémáknak felelnek meg, hiszen az univerzális kvantor csak a formulák legelején szerepel. Hogyha a finit számelmélet rendelkezésére álló eszközöket azonosítjuk a primitív rekurzív aritmetika lehetőségeivel,⁵² vagy legalább azt feltételezzük, hogy adható olyan (konzisztens) formális rendszer, melynek tételei között megtalálhatók lesznek a finit számelmélet tételei is, akkor az előző bekezdésben mondottak mintájára felvethető, hogy lesznek olyan valós sémák, melyek igazak (verifikálhatók), igazságuk belátható, azonban mégsem igazolhatók finit módszerekkel (és persze nem is cáfolhatók). Ez viszont ellentétben áll a finit matematika konstruktivitásával. Ráadásul a finit módon eldönthetetlen valós igazságok léte fenyegeti a Hilbert-program azon feltevését is, mely szerint az ideális rendszerek az elemi számelmélet konzervatív bővítései. Ugyanis ha adott egy konzisztens, és (többek között) Q tételeit levezető I formális rendszer, melynek tételei között szerepel a finit számelmélet összes bizonyítható tétele, akkor a (GR*) szerint létező eldönthetetlen śxA(x) alakú állítást kifejező tétellel bővített I* rendszer már biztosan nem lesz konzervatív bővítése a finit számelméletnek, ha śxA(x) finit igazság.⁵³

A finitista — csakúgy mint az előző esetekben — többféle stratégiát is választhat e problémák megoldására. Elvileg tagadhatja a finit számelmélet formalizálhatóságát, ezzel lehetővé téve a valós igazságok finit levezethetőségét és az ideális bővítések konzervativitását. Alapvető probléma ezzel a válasszal, hogy ellentétben áll a finit matematika konstruktivitásának és episztemológiai kitüntetettségének igényével. Ha ennyire tágan értelmezzük a finit számelméletet, akkor kérdésessé válhat az egész hilberti program ismeretelméleti jelentősége is, hiszen a konzisztencia bizonyítása bizonyos eszközökkel triviális. Járhatóbbnak tűnik az az út, mely formalizálhatónak tartja a finit aritmetikát, viszont tagadja, hogy a (GR*) alapján konstruálható mondatok minden esetben finit igazságok lennének. Ez azt jelentené, hogy egy séma esetleges verifikálhatósága (klasszikus igazsága) egyáltalán nem jelenti finit igazságát: ezt csakis finit bizonyíthatósága garantálná, összhangban a finitizmus konstruktív jellegével. Megemlíthető ezzel a megoldással kapcsolatban, hogy a finit igazság ilyen értelmezése mellett egy ideális bővítés konzisztenciája definíció szerint nemcsak valós helyességét, illetve megbízhatóságát, hanem egyben konzervativitását is maga után vonja, hiszen a valós igazság ilyen meghatározása szerint nem létezhetnek valós eszközökkel bizonyíthatatlan valós igazságok.

3.2 A második nem-teljességi tétel és a Hilbert-program

Az előző szakaszban láttuk, hogy az első nem-teljességi tétel két ponton követelheti meg az eredeti Hilbert-program módosítását. Egyrészt lemondva arról, hogy egy informális ideális elmélet gyakorlatát teljesen és "egyszer és mindenkorra" formalizálja, a hilbertiánus arra kényszerülhet, hogy csak a megalapozni kívánt ideális elmélet egy (bár nagyon átfogó) részének instrumentális megbízhatóságát próbálja meg igazolni. Másrészt a verifikálható, de bizonyos rendkívül erős formális rendszerekben sem bizonyítható számelméleti kijelentéssémák esetleges létezése a finit számelméleti igazságnak a finit számelméleti bizonyíthatósággal való teljes azonosítása mellett szólhat.

Gödel második nem-teljességi tétele a tradicionális értelmezés szerint lényegesen nehezebbnek látszó probléma elé állítja a Hilbert-programot, mivel interpretálható úgy, mint ami azt állítja, hogy egy bizonyos mennyiségű aritmetikát (például a Peano-aritmetika tételeit) levezetni képes konzisztens formális rendszer eszközeivel nem bizonyítható az adott rendszer konzisztenciáját kifejező aritmetikai állítás. Ez pedig azt jelentené, hogy még az igazolni kívánt ideális gyakorlat eszközein is túlmenő bizonyítási módszerekkel kellene rendelkeznie a "finit" matematikának (sőt számelméletnek) ahhoz, hogy az ideális gyakorlat konzisztenciáját igazolni tudja. A következőkben először megfogalmazzuk a második nem-teljességi tételt, majd megpróbáljuk rekonstruálni a tételből a Hilbert-program megvalósíthatatlanságára következtető érvet és (röviden) a lehetséges finitista válaszokat is.

A második tétel az előző szakasz L nyelvére így mondható ki⁵⁴ (feltételezzük, hogy L-lel adott L kifejezéseinek egy tetszőleges olyan Gödel-számozása is, mely kölcsönösen egyértelműen minden L-beli e kifejezéshez egy [e] természetes számot rendel, és melyre nézve L szintaktikai alapkategóriái és alaprelációi eldönthető aritmetikai predikátumokkal és relációkkal fejezhetők ki):

(G2) Tegyük fel, hogy P egy L nyelvű elsőrendű elmélet, mely kielégíti (GR) feltételeit, és z P egy cáfolható mondata. Ekkor ha B(x) olyan predikátum L-ben, melyre L minden x, y mondatára teljesül, hogy

(1) ha x tétele P-nek, akkor B([x]) is az,

(2) B([xey])e(B([x])eB([y])) tétele P-nek,

(3) B([x])eB([B([x])]) tétele P-nek,

akkor L-ben nem vezethető le ~B([z]).

A (GR) esetében alkalmazott megfontolások alapján (G2)-nek is megfogalmazható egy olyan általánosított változata, mely effektíven kezelhető formális rendszerekre, és azok kifejezéseinek egy effektív Gödel-számozására hivatkozik. Effektív számozáson egy rendszer kifejezéseinek olyan kölcsönösen egyértelmű leképezését érthetjük a természetes számok halmazára, melynél minden számról effektíven eldönthető, hogy száma-e egy kifejezésnek, és a rendszer kifejezéseinek effektíven kezelhető szintaktikai alapkategóriái és alaprelációi eldönthető aritmetikai predikátumoknak felelnek meg. A (GR*) esetében felhozott érvek alapján a továbbiakban feltesszük, hogy (G2) általánosított változata, (G2*) érvényes minden olyan effektíven kezelhető formális rendszerre, mely egy ideális elméletet elfogadhatóan reprezentál.

(G2*) alapján a következő, tradicionálisnak nevezhető érv hozható fel a finitista programmal szemben:⁵⁵

(1) Megfelelő effektív Gödel-számozás mellett minden, egy effektíven kezelhető I rendszerről finit módon bizonyítható metamatematikai állítás kifejezhető egy finiten bizonyítható aritmetikai kijelentéssel.

(2) Minden olyan effektíven kezelhető rendszerben, mely egy ideális elméletet elfogadhatóan formalizál (röviden: elfogadható rendszerben), megfogalmazható az összes finit aritmetikai kijelentés, és a finit igazságokat kifejező mondatok le is vezethetők.

(3) (1) és (2) alapján minden elfogadható I rendszerben, melynek konzisztenciája bizonyítható finit módon, megfogalmazható és levezethető egy finit aritmetikai állítás, mely egy effektív Gödel-számozás mellett I konzisztenciáját fejezi ki.

(4) (G2*) szerint egy konzisztens és elfogadható I rendszerben nem vezethető le egy effektív Gödel-számozás szerint I konzisztenciáját kifejező ~B([z]) állítást megfogalmazó mondat sem.

(5) (3) és (4) alapján egy konzisztens és elfogadható I rendszer konzisztenciája sem bizonyítható finit módon.

Mivel a Hilbert-program az ideális elméletek elfogadható és konzisztens formalizációinak konzisztenciáját szeretné finit módon bizonyítani, ezért (5)-ből valóban a program kivitelezhetetlenségére következtethetünk. Kérdés, hogy az érv egyes premisszái és következtetései elfogadhatók-e.

(1) mellett részben (GR*) kapcsán már említett érveket lehet felhozni. Ha feltesszük, hogy a finit metamatematika által vizsgált nyelvek véges ábécével rendelkeznek, akkor egy vizsgált nyelv szavai megszámozhatók úgy, hogy az összes eldönthető szintaktikai alapkategória és alapreláció kifejezhető lesz eldönthető aritmetikai predikátumokkal és relációkkal.⁵⁶ Ezért ha egy szintaktikai kategória vagy reláció effektíven eldönthető, akkor ennek aritmetikai kifejezői is azok lesznek. Megfelelő számozással tehát valóban minden, adott nyelvre vonatkozó metamatematikai állítás lefordítható egy aritmetikai állításra oly módon, hogy a finit módon bizonyítható metamatematikai állítások finit módon bizonyítható aritmetikai állításokba mennek át (természetesen feltéve, hogy a megengedhető logikai következtetések ugyanazok a két területen). Megemlíthető még, hogy (1)-et a Hilbert-program munkatársai is kivétel nélkül elfogadták, miután az aritmetizáció módszere ismertté vált.⁵⁷

(1)-hez hasonlóan (2) is megalapozottnak tűnik, mivel azok az érvek, melyek (GR*) érvényessége mellett szóltak, mutatják, hogy egy elfogadható rendszernek "tartalmaznia" kell az elsőrendű Peano-aritmetikát. A finit számelmélet hagyományos (azt a primitív rekurzív aritmetikával azonosító) értelmezése szerint pedig teljesül, hogy minden finit számelméleti állítás megfogalmazható és bizonyítható az elsőrendű Peano-aritmetikán belül.

A tradicionális érv első két premisszájával szemben (4) rendkívül problematikus, és legalább kétféleképpen értelmezhető. Az első interpretáció szerint azt állítja, hogy ha egy konzisztens I-ben B(x) olyan predikátum, melyre teljesülnek (G2*) feltételei (röviden: levezethetőségi predikátum) és z cáfolható I-ben, akkor a ~B([z]) mondat kifejezi I konzisztenciáját (az adott számozás mellett), de nem vezethető le. Ez azonban (amellett hogy egyáltalán nem vitathatatlan),⁵⁸ nem elég erős állítás ahhoz, hogy belőle (3) segítségével (5)-re következtethessünk. A következtetés helyességéhez az lenne szükséges, hogy bármely elfogadható I-ben, effektív számozás mellett I konzisztenciája csak olyan finit aritmetikai állításokat megfogalmazó mondatokkal lehessen kifejezhető, melyekből I-ben levezethető egy ~B([z]) alakú mondat is, ahol B már levezethetőségi predikátum. A tradicionális érv negyedik premisszáját ezért helyettesíteni kell a következőkkel:

(4.1) Ha s mondat egy I elfogadható rendszerben olyan finit aritmetikai állítást fogalmaz meg, mely egy effektív számozás mellett I konzisztenciáját fejezi ki, akkor I-ben s-ből levezethető egy ~B([z]) alakú mondat is, ahol B és z eleget tesz (G2*) előírásainak (speciális esetben s maga ilyen mondat).

(4.2) (G2*) alapján egy konzisztens és elfogadható I elméletben nem vezethető le egy ~B([z]) alakú mondat sem, ahol B és z eleget tesz (G2*) előírásainak.

(4.3) (4.1) és (4.2) alapján egy konzisztens és elfogadható I rendszerben nem vezethető le egy olyan mondat sem, mely egy effektív számozás mellett I konzisztenciáját kifejező finit aritmetikai állítást fogalmaz meg.

Ezzel a változtatással az érv logikailag helyesnek tekinthető, tehát aki a konklúziót vitatja, annak valamelyik premissza igazságát kell megcáfolnia. Bár a tradicionális érvet nem rekonstruálták explicit módon, első előfordulását mégis valószínűleg a Hilbert és Bernays által írt Grundlagen der Mathematik második kötetének 1939-es megjelenéséhez köthetjük. Ebben a szerzők egyrészt kimondták a nem-teljességi tételek erősen általánosított alakjait, másrészt tényként fogadták el, hogy Gödel tételeinek fényében felül kell vizsgálni a finit matematika által használható eszközökre vonatkozó nézeteket.⁵⁹ Ennek megfelelően a Hilbert-program módosított változata finit eljárásnak tekintette a transzfinit indukció bizonyos (nem túl nagy rendszámokig történő) alkalmazásait, így finitként fogadva el Gentzen már 1936-ban megjelent konzisztenciabizonyítását az elsőrendű Peano-aritmetika egy változatára.⁶⁰ A Hilbert-program új formájára tehát már nem volt érvényes a rekonstruált érv második premisszája. Azonban éppen ez a tény tette rendkívül kétségessé a módosított Hilbert-program filozófiai tarthatóságát.

Az alkalmazott eszközök ugyan bizonyos szempontból továbbra is konstruktívnak voltak tekinthetők,⁶¹ de egyértelműen túlmenni látszottak a program háttérepisztemológiája által megengedett határokon, azzal veszélyeztetve a vállalkozást, hogy körbenforgóvá válik. Mivel valószínűsíthető, hogy a program távolabbi céljának, az analízis megalapozásának eléréséhez legalábbis a transzfinit indukció még erősebb alkalmazásai lennének szükségesek,⁶² ezért érthető, hogy a módosított Hilbert-program megfogalmazása óta az a szinte egyöntetű vélemény alakult ki, hogy a finit metamatematika mind eredeti, mind tágan értelmezett formájában alkalmatlan a klasszikus eredményeknek a szkeptikust meggyőző megalapozására.⁶³

A tradicionális érv súlyos következményeit figyelembe véve meglepő, hogy Hilbert és Bernays könyvükben egyáltalán nem térnek ki a tradicionális értelmezés legsebezhetőbbnek tűnő pontjára, (4.1)-re. Azt feltételezve, hogy egy olyan formulából, mely egy ideális elmélet formalizált változatában a rendszer konzisztenciáját fejezi ki, levezethető kell legyen egy ~B([z]) alakú formula, ahol B a rendszerben való bizonyíthatóságot reprezentálja, (4.1) megalapozásához elég igazolni, hogy minden, a bizonyíthatóságot kifejező predikátum eleget tesz (G2) kikötéseinek. A tradicionális érvet elfogadó későbbi szerzők — például Kreisel — úgy érvelnek (G2) követelményeinek szükségessége mellett, hogy azok metamatematikai megfelelőit ugyanúgy be kell tudnia látnia a finitistának az ideális elmélet megalapozásához, mint a konzisztenciát.⁶⁴ Gödel második tétele ebben az értelmezésben azt mondja ki, hogy egy konzisztens ideális rendszerről sem bizonyítható egyszerre konzisztenciája, zártsága a leválasztásra nézve (2. követelmény) és részleges teljessége (3. követelmény). Kérdéses azonban, hogy miért ne bizonyíthatná a finitista ezeket a tényeket más-más bizonyítási relációk használatával. Ahhoz, hogy egy ilyen jellegű érv valóban meggyőző legyen, valószínűleg a finitista metamatematikai bizonyítások, és azok aritmetikai megfelelői közt fennálló összefüggések további részletes vizsgálatára lenne szükség.

4. Befejezés

A Hilbert-program és a nem-teljességi tételek kapcsolatának vázlatos áttekintése után érdemes megemlíteni, hogy Hilbert bizonyításelméleti kezdeményezését valószínűleg nem kizárólag a klasszikus matematika megalapozásának célja motiválta. Kreisel ezzel kapcsolatban a következő rendkívül érdekes megjegyzést teszi:

"Bár a Hilbert-program és a bizonyításelmélet céljai általában nem kapcsolódnak egymáshoz és gyakran konfliktusba kerülnek, ez nem jelenti azt, hogy Hilbert saját érdekeinek ellentmondanának. Mind írásaiból, mind lejegyzett beszélgetéseiből úgy tűnik, hogy — legalábbis egy korszakában — legfontosabb célja az volt, hogy a matematikusok figyelmét a bizonyításokra mint tanulmányozandó tárgyakra irányítsa: és a »nagy« program ehhez szolgált csalétekül."⁶⁵

Ha Hilbert programját ebből a tágabb perspektívából vizsgáljuk, akkor elmondható, hogy Gödel nem-teljességi tételei rendkívül fontos új kutatási területet nyitottak meg a bizonyításelmélet számára, megteremtve ezzel a formális rendszerek rekurzív függvényekre, illetve később algoritmuselméletre alapozott általános elméletének lehetőségét. Az is figyelemre méltó, hogy Hilbert több írásában hangsúlyozta: egy feladat megoldhatatlanságának bizonyítása legalább olyan jelentőségű lehet, mint a pozitív megoldás. Az aritmetika és az analízis konzisztenciájának bizonyítását célul kitűző Hilbert-program és Gödel tételeinek viszonyára ezért utólag rendkívül találónak tűnnek Hilbert saját szavai a Grundlagen der Geometrie végén:

"Amikor matematikai elmélkedéseink során találkozunk egy problémával vagy megsejtünk egy tételt, megismerési ösztönünk csak akkor elégül ki, ha vagy tökéletesen megoldjuk a problémát, illetve szigorúan bizonyítjuk a tételt, vagy világosan felismerjük a siker lehetetlenségét és a szükségszerű kudarc alapját. Így az újabb matematikában kiemelkedő szerepet játszik bizonyos feladatok megoldhatatlanságának kérdése, és az ilyen kérdések megválaszolására irányuló törekvés gyakran vezetett új és gyümölcsöző kutatási területek felfedezéséhez."⁶⁶

IRODALOM

[ Cikk eleje | Cikk vége | Summary | Jegyzetek ]

Ackermann, William, Begründung des "tertium non datur" mittels der Hilbertschen Theorie der Widerspruchfreiheit. Matematische Annalen 93 (1924), 1-36.

Detlefsen, Michael, Hilbert's program. Reidel, Dordrecht (1986).

Feferman, Solomon, Kurt Gödel: Conviction and caution, in S. G. Shanker (ed), Gödel's theorem in focus (1988), 96-114.

Feferman, Solomon, The arithmetization of metamathematics in general setting. Fundamenta Mathematicae 49 (1960), 35-92.

Frege, Gottlob, Begriffschrift, eine der aritmetischen nachgebildete Formelsprache des reinen denkens. Halle (1879).

Gentzen, Gerhard, Der Widerspruchfreiheit der reinen Zahlentheorie. Matematische Annalen 112 (1936), 493-565.

Gödel, Kurt, The completeness of the axioms of the functional calculus of logic, in J. van Heijenoort (ed), From Frege to Gödel, 581-591.

Gödel, Kurt, Some metamathematical results on completeness and consistency, in J. van Heijenoort (ed), From Frege to Gödel, 595-596.

Gödel, Kurt, On formally undecidable propositions of Principa Mathematica and related systems I, in J. van Heijenoort (ed), From Frege to Gödel, 596-616.

Herbrand, Jacques, On the consistency of arithmetic, in J. van Heijenoort (ed), From Frege to Gödel, 618-628.

Hilbert, David, Grundlagen der Geometrie. Leipzig (1899). 8. kiadás: Teubner, Stuttgart (1962).

Hilbert, David, Über den Zahlbegriff. Jahresbericht der Deutschen Mathematiker-Vereinigung 8 (1900), 80-194.

Hilbert, David, Mathematische probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongress zu Paris 1900. Archiv der Mathematik und Physik 3, 1 (1900), 44-63, 213-237.

Hilbert, David, On the foundations of logic and arithmetic, in J. van Heijenoort (ed), From Frege to Gödel, 129-138.

Hilbert, David, On the infinite, in J. van Heijenoort (ed), From Frege to Gödel, 367-392.

Hilbert, David, Bernays, Paul, Grundlagen der Mathematik I. Springer, Berlin (1934). 2. kiadás: Springer, Berlin (1968).

Hilbert, David, Bernays, Paul, Grundlagen der Mathematik II. Springer, Berlin (1939). 2. kiadás: Springer, Berlin (1970).

Hodges, Wilfrid, Elementary predicate logic, in D. Gabbay, F. Guenthner (eds), Handbook of philosophical logic I., Reidel, Dordrecht (1983).

Kreisel, Georg, What have we learnt from Hilbert's second problem?, in AMS proceedings of symposia in pure mathematics 28 (1976), 93-130.

Manyin, J. I.. Bevezetés a kiszámíthatóság matematikai elméletébe. Műszaki Könyvkiadó, Budapest (1985).

Neumann János, On the formalist foundations of mathematics, in P. Benacerraf, H. Putnam (eds), Philosophy of mathematics: Selected readings, Prentice Hall, Englewood Cliffs (1967).

Neumann János, Zur Hilbertschen Beweistheorie. Matematische Zeitschrift 26 (1927), 1-46.

Prawitz, Dag, Philosophical aspects of proof theory, in G. Flostad, G. H. von Wright (eds), Contemporary philosophy. A new survey, Martinus Nijhoff Publishers, The Hague (1981).

Resnik, Michael D., On the philosophical significance of consistency proofs, in S. G. Shanker (ed), Gödel's theorem in focus (1988), 96-114.

Rosser, John Barkley, Extensions of some theorems of Gödel and Church. The journal of symbolic logic 1 (1936), 87-91.

Russell, Bertrand, Mathematical logic as based on the theory of types. American journal of mathematics 30 (1908), 222-262.

Skolem, Thoralf, The foundations of elementary arithmetic established by means of the recursive mode of thought, in J. van Heijenoort (ed), From Frege to Gödel, 302-333.

Smullyan, Raymond M., Gödel's incompleteness theorems. Oxford University Press (1992).

van Heijenoort, Jean (ed), From Frege to Gödel: A source book in mathematical logic. Harvard University Press (1967).

Weyl, Hermann, Comments on Hilbert's second lecture on the foundations of mathematics, in J. van Heijenoort (ed), From Frege to Gödel, 482-484.

SUMMARY

[ Cikk eleje | Cikk vége | Irodalom | Jegyzetek ]

Hilbert's program and the incompleteness theorems

In the first part of the paper the author tries to reconstruct the development of Hilbert's program from the turn of the century to 1931 — the year when Gödel's famous paper on incompleteness appeared. Within this period we can distinguish a first, preliminary phase, characterized by unsolved methodological and philosophical problems, and a second, mature form of the program, which gave rise to a series of important technical results.

In the early formulations Hilbert accepts the logicist project of providing a foundation for classical arithmetic, set theory and analysis, but he rejects the logicist solution, claiming that certain mathematical concepts, like the concepts of number and set are not reducible to logical ones. He alsoclaims that we can justify the mathematical theories in question by formalizing them, and proving the consistency of the formal versions. In his view, such a proof can only be a direct one, as opposed to the indirect or relative consistency proofs, that presuppose the consistency of other theories. The central problem of the early program was that the exact nature of the invoked concepts of logical consequence and consistency was left unspecified: Hilbert had to propose a plausible analysis of these concepts with reasonable epistemological background.

Starting from the beginning of the 1920s, Hilbert in collaboration with P. Bernays developed the final form of the program. They distinguished the real or contentual part from the ideal part of the theories to be justified, arguing that only the real, finitary statements of a mathematical theory can have an interpretation, since ideal statements play a role similar to the rőle of ideal elements in mathematics, their sole function being to facilitate the formal manipulation of real statements and derivation of new real results. They also made clear that the final aim was to provide a finitary proof of the syntactical consistency of ideal formal systems, intended to represent the actual mathematical practice of the time. Promising technical results in this direction were obtained among others by W. Ackerman, J. von Neumann and J. Herbrand: they proved the consistency of formal systems of analysis and arithmetic, with certain restrictions on the applicable forms of mathematical induction and substitution.

In the second part of the paper an account of the various connections between the incompleteness theorems of Gödel and Hilbert's program is given. Firstly, the historical link is considered: Gödel was trying to prove the (relative) consistency of real analysis, when he discovered the necessary incompleteness of formal systems of arithmetic. As regarding the philosophical relation, the author examines the most widespread interpretation of the theorems according to which these results proved that Hilbert's program — at least in it's original form — cannot be carried out. After a discussion of the first incompleteness theorem's possible impact, a reconstruction of the standard argument against Hilbert's program is offered, which is based on the second theorem. As it turns out, this reconstructed traditional argument presupposes that every arithmetical representation of a system's probability predicate must satisfy the so-called derivability con-ditions of the second theorem — although this is a questionable assumption. The paper concludes with a brief account of the developments of the program after the incompleteness theorems.

JEGYZETEK

[ Cikk eleje | Cikk vége | Irodalom | Summary ]

1 Frege Fogalomírása 1879-ben jelent meg.vissza

2 Hilbert, On the infinite, 375. o. (Mivel a dolgozatban tárgyalt művek többségének még nem létezik magyar fordítása, ezért ezeket - ha ellenkezőjét nem jelzem - saját fordításomban idézem.)vissza

3 Lásd például Russell, Mathematical logic as based on the theory of types.vissza

4 A Frege által sokat vitatott formalizmusnak Hilbert programja nem egyszerűen leszármazottja, habár fennáll bizonyos kapcsolat.vissza

5 D. Hilbert, Grundlagen der Geometrie, 36. o.vissza

6 D. Hilbert, Über den Zahlbegriff.vissza

7 D. Hilbert, Mathematische probleme, 2. probléma.vissza

8 D. Hilbert, On the foundations of logic and arithmetic.vissza

9 D. Hilbert, On the foundations of logic and arithmetic, 130. o.vissza

10 Uo., 134. o.vissza

11 Uo., 135. o.vissza

12 Az így nyerhető relációk antropológiai sajátosságok miatt eltérhetnek a szemantikai következményrelációtól.vissza

13 Az elsőrendű logika esetében Gödel teljességi tétele szerint definiálható a szemantikai következményreláció pusztán szintaktikai eszközökkel is, de egyes magasabb rendű logikákban ez még elvileg sem megoldható. Hilbert konkrét példája az elsőrendű kalkulusnak csak egy töredékét alkalmazza.vissza

14 D. Hilbert, On the infinite, 373. o.vissza

15 Uo., 383. o.vissza

16 D. Hilbert, P. Bernays, Grundlagen der Mathematik I., 21. o.vissza

17 D. Hilbert, On the infinite, 372. o.vissza

18 Uo., 392. o.vissza

19 Uo., 376. o.vissza

20 A Grundlagen tudományfelfogása sok közös vonást mutat Carnap késői nézeteivel: a tapasztalattal teljes tudományos elméleteket szembesítünk, melyeken belül értelmezhető a létezés, illetve a logikai és analitikus igazság fogalma. Weyl már 1927-ben holistaként interpretálta Hilbert tudományfelfogását. Szerinte Hilbert hangsúlyozta, hogy az "elméleti fizika kijelentései nem egyenként, csak mint teljes rendszer szembesíthetők a tapasztalattal". (H. Weil, Comments on Hilbert's second lecture, 484. o.)vissza

21 D. Hilbert, P. Bernays, Grundlagen der Mathematik I., 16. o.vissza

22 Lásd uo. 32. o., illetve D. Hilbert, On the infinite, 378. o.vissza

23 Uo., 378. o.vissza

24 Úgy tűnik, hogy Weyl így interpretálta Hilbertet: "Mi késztet minket arra, hogy éppen a Hilbert által kifejlesztett axiómarendszereket vegyük alapul? [...] Egyelőre valószínűleg nem tudjuk megválaszolni ezt a kérdést, csak kifejezhetjük hitünket a történelem ésszerűségében, mely ezeket a struktúrákat alakította ki az intellektuális fejlődés folyamán." (H. Weyl, Comments on Hilbert's second lecture, 483. o.)vissza

25 Lásd például Neumann János, On the formalist foundations of mathematics.vissza

26 D. Hilbert, On the infinite, 376. o.vissza

27 W. Ackermann, Begründung des "tertium non datur" mittels der Hilbertschen Theorie der Widerspruchfreiheit.vissza

28 Neumann J., Zur Hilbertschen Beweistheorie.vissza

29 J. Herbrand, On the consistency of arithmetic.vissza

30 T. Skolem, The foundations of elementary arithmetic.vissza

31 Lásd D.Hilbert, P.Bernays, Grundlagen der Mathematik I., 294. o.vissza

32 Uo., 18. o.vissza

33 K. Gödel, The completeness of the axioms of the functional calculus of logic.vissza

34 Lásd például W. Hodges, Elementary predicate logic, 66. o.vissza

35 Az is igazolható, hogy ha az aritmetika szokásos axiómái mellé felvesszük egy az adott elmélet konzisztenciáját kifejező axiómát is, akkor az elmélet minden formulájának fordítása bizonyítható lesz a kapott rendszerben (lásd J. van Heijenoort, From Frege to Gödel, 583. o.). vissza

36 D. Hilbert, P. Bernays, Grundlagen der Mathematik I., 125. o.vissza

37 K. Gödel, On formally undecidable propositions of Principa Mathematica and related systems I.vissza

38 K. Gödel, Some metamathematical results on completeness and consistency.vissza

39 H. Wang, Some facts about Kurt Gödel. Idézi S. Feferman, Kurt Gödel: Conviction and caution, 105. o.vissza

40 Uo.vissza

41 Gödel a második nem-teljességi tétel bizonyításának vázlata után ezt írja: "Külön meg szeretném jegyezni, hogy a XI. tétel [...] nem mond ellent Hilbert formalista nézőpontjának, mivel ez csak azt feltételezi, hogy létezik kizárólag finit eszközöket alkalmazó konzisztencia-bizonyítás. Elképzelhető, hogy vannak olyan finit bizonyítások, melyek nem fejezhetők ki a P formalizmusban." (On formally undecidable propositions, 615. o.)vissza

42D. Hilbert, P.Bernays, Grundlagen der Mathematik I., VII. o.vissza

43 A Gödel által vizsgált formális nyelvben nem volt szükség az összeadás és a szorzás jeleire és axiómáira, mert ezek másodrendű változók segítségével kifejezhetők voltak.vissza

44 A következő tételek megfogalmazása R. M. Smullyan Gödel's incompleteness theorems című könyvét követi.vissza

45 Vagyis a formális rendszeren belül nem levezethető és nem is cáfolható. Az eldönthetetlenség itt (és a további tételek kimondásakor) alkalmazott fogalma különbözik az algoritmikus eldönthetetlenségtől.vissza

46 J. B. Rosser, Extensions of some theorems of Gödel and Church.vissza

47 Ez a követelmény gyengíthető lenne (vö. (GR)), de a Hilbert-program szempontjából az erősebb tétel sem jelentene eltérő megoldást igénylő problémát.vissza

48 (G1) és (GR) egy szabatos általánosított változatát adja a rekurzivitás fogalmának felhasználásával D. Hilbert, P. Bernays, Grundlagen der Mathematik II., 278-293. o. A Gödel-Tarski-tétel ilyen irányú általánosítását lásd például J. Manyin, Bevezetés a kiszámíthatóság matematikai elméletébe, 108. o.vissza

49 Lásd a következő szakaszt.vissza

50 Gödel például ezen az alapon kritizálta Hilbert programját. Lásd S. Feferman, Kurt Gödel: Conviction and caution, 102. o.vissza

51 Így például Prawitz a következőket írja: "[...] Kreisel megjegyezte, hogy a kodifikáció [= finit reprezentáció] kiválasztása központi problémává válik, mivel az szükségszerűen nem-teljes lesz. Azt lehet mondani, hogy a transzfinit gondolkodás igazolásának, vagy finit redukciójának elképzelése[...] kevésbé meggyőző, ha nem tehető meg egyszer és mindenkorra." D. Prawitz, Philosophical aspects of proof theory, 263. o. vissza

52 Lásd 2.5 szakasz.vissza

53 Már az elsőrendű Peano-aritmetikában is levezethetők olyan śxA(x) alakú "valós" mondatok, melyek a primitív rekurzív aritmetikában nem bizonyíthatóak.vissza

54 Itt is R. M. Smullyan Gödel's incompleteness theorems című könyvét követjük (lásd 106.o.). A tétel ebben a formában általánosabb a Gödel írásában kimondottnál, mivel ő nemcsak a nyelvet rögzítette le, hanem a számozást is, és erősebb követelményeket támasztott a B predikátummal szemben. A tétel ehhez hasonló alakban először D. Hilbert és P. Bernays Grundlagen der Mathematik II. című művében került kimondásra (293. o.).vissza

55 Vö. M. Detlefsen, Hilbert's program, 78. o.vissza

56 Például ha van olyan betű az ábécében, mellyel nem kezdődik kifejezés, és n az ábécé betűinek száma, akkor a nyelv minden kifejezése egy természetes szám n-es számrendszerben felírt alakjának tekinthető.vissza

57 Lásd például J. Herbrand, On the consistency of arithmetic, 628. o.vissza

58 Ha B eleget tesz (G2) első követelményének, és I egy konzisztens elfogadható rendszer, akkor ~B([z]) levezethetőségéből valóban következtethetünk ~B([z]) levezethetetlenségére. De ~B([z]) természetesen akkor is levezethető, ha I inkonzisztens.vissza

59 Így például rögtön az előszóban ezt olvashatjuk: "[A könyv] második főtémáját azoknak a tényeknek az ismertetése képezi, melyek [..] a »finit álláspont« eddigi kereteinek kiszélesítését teszik szükségessé. A tárgyalás középpontjában Gödel felfedezése áll [...]." (VII. o.) vissza

60 G. Gentzen, Die Widerspruchfreiheit der reinen Zahlentheorie.vissza

61 Az indukciót például - a Peano-aritmetikával ellentétben - nem alkalmazták kötött változókat is tartalmazó formulákra.vissza

62 Az analízis egyes részelméleteinek konzisztenciájára léteznek a transzfinit indukciót magasabb rendszámig használó bizonyítások (lásd D. Prawitz, Philosophical aspects of proof theory, 263. o.).vissza

63 Lásd például M. D. Resnik, On the philosophical significance of consistency proofs. Az ellenkező véleményt valló kisebbség egyik markáns képviselője M. Detlefsen (lásd Hilbert's program című esszéjét).vissza

64 Lásd G.Kreisel, What have we learnt from Hilbert's second problem?, 112. o. vissza

65 Uo., 128. o. vissza

66 D. Hilbert, Grundlagen der Geometrie, 124. o.vissza

[ Cikk eleje | Irodalom | Summary | Jegyzetek ]