|
A szemináriumon szétosztott handout. *** 1. oldal *** Cantor, Russell, Gödel – avagy maga borotválkozik-e Russel fodrásza? Vitaindító hozzászólás a ’Gödel vitához’, ELTE, TTK, Tud. Fil Tanszék szemináriuma Geier János, ELTE, BTK. Pszich. 2002.04.08. http://www.geier.hu A Gödel tétel levezetése – más egyebek mellet – G. Cantor közel 130 évvel ezelőtti találmányán, az ún. diagonalizáción alapul. Ezzel bizonyította be Cantor az akkor nagy port felkavart tételét, miszerint a valós számok halmaza nem ekvivalens a természetes számok halmazával. Azóta több tétel és még több paradoxon (antinómia) látott napvilágot, melyek bizonyítása (ill. paradoxonok esetén kimondása) egyaránt a diagonalizációt használja fel. Diagonalizáción alapuló tételek: · Cantor tétele a valós számok nem megszámlálhatóságáról (kb. 1873); · Cantor tétele hatványhalmaz számosságáról (kb. 1873); · Gödel első nemteljességi tétele (1931); · Az univerzális Turing gépekre vonatkozó megállási tétel (1936); Diagonalizáción alapuló paradoxonok: · Richard paradoxon a Cantor levezetés paródiájaként (1905); · Russell paradoxon az összes halmazok halmazáról (1901); · Richard paradoxona a természetes számok tulajdonságainak kapcsán (?); · A falusi borbélyról szóló paradoxon aki „azokat és csak azokat a falujabeli férfiakat borotválja, akik nem maguk borotválkoznak” (Russell 1919). A következő kérdést teszem fel: Hogyan lehet az, hogy ugyanazt a fő lépést tartalmazó gondolatmenet egyszer paradoxont, máskor bizonyítást eredményez? Az elemzést a borbély paradoxon, mint „állatorvosi ló” alapján fogom elvégezni. Közönséges, de precíz matematikai lépésekkel formalizálom, majd „megoldom a szöveges feladatot”, és ki fog derülni: a levezetés nem vezet ellentmondásra, így szó sincs paradoxonról. Látni fogjuk ennek következtében, hogy a borbély paradoxon egy ügyes beugratás: a hallgatónak nem azt a kérdést teszi fel, ami a lényeg. (Sok ilyen társasági találós kérdés ismert.) A borbély paradoxon látszólagos paradoxon; csak annak számára valódi, aki úgy gondolja, hogy ha egy bizonyos tulajdonságú dologról beszélni tudunk (állítást tudunk róla megfogalmazni), ettől az ilyen tulajdonságú dolog már létezik is. Korrekt matematikai levezetéssel be fogom bizonyítani: a diagonalizáció nem vezet ellentmondára, ezért nem használható se antinómia készítésére, se indirekt bizonyításra. Az alkalmazott matematikai levezetés megfogalmazása olyan lesz, hogy az összes fent említett paradoxonra alkalmazható, továbbá az összes fent említett tétel levezetésére is alkalmazható. Ennek pedig az a meglepő következménye, hogy nemcsak a paradoxonok, hanem a tétel levezetések is csak „látszólagosak”. A Cantor-féle átló eljárásról fogom elsőként kimutatni, hogy az nem bizonyítás; a diagonalizáció nem bizonyítja, amit Cantor tétel kimond. Ennek mintájára a többi tétel (Gödel, Turing) levezetéséről ugyanezt a következtetést tudjuk majd levonni. Kérem a részvevőt, a közös nyelv kialakítása érdekében gondolkodjon el a következő kérdéseken. 1. Bármit meg lehet-e konstruálni? (Javasolt válasz: nem. „A konstruálhatóság szükséges feltétele a létezhetőség.” Pl. perpétum mobilet nem lehet konstruálni, mert előre tudjuk, hogy nem létezhet.) 2. Mit nevezünk tulajdonságnak? (Javasolt válasz: A H halmazon értelmezett tulajdonságoknak nevezzük a T:H®{igaz, hamis} leképezéseket, ahol H előre adott tetszőleges nem üres halmaz. Ha valamely xÎH esetén T(x)=igaz, akkor azt mondjuk, hogy x rendelkezik a T tulajdonsággal, vagy másképp: T érvényes x-re.) 3. Lehet-e (értelmes módon) definiálni olyan tulajdonságot, ami sohasem lehet igaz? (Javasolt válasz: igen. Pl. lehet beszélni „pepita mintázatú perpétum mobile”-ről. Ez egy jóldefiniált tulajdonság az ember alkotta gépezetek H halmazán. Jellemzője: tetszőleges konkrét ember alkotta szerkezetet is tekintünk, előre tudhatjuk, hogy arra ez a tulajdonság nem lesz érvényes. T = azonosan hamis függvény. De ettől még jóldefiniált, sőt!) 4. Lehet-e tulajdonsággal felruházni olyan dolgot, mely nem létezik? (Javasolt válasz: nem. Ami nincs, az nem képes kielégíteni a T tulajdonságot, bárhogyan legyen is megadva a T. Egyszerűen nincs mit behelyettesíteni a T argumentumába (a tulajdonság leírásába), így nincs mód megvizsgálni és eldönteni, igaz-e vagy sem.) 5. Létezik-e valami puszán annak következtében, hogy felruházzuk egy jóldefiniált tulajdonsággal? (Javasolt válasz: természetesen nem. A „felruházás” előfeltétele, hogy létezzen is az a dolog.)
6.
Ha élőszóban egy ’dologról’
állítunk ’valamit’, mikor mondjuk, hogy ez egy ’értelemes’ állítás?
*** 2. oldal *** A Richard paradoxon, Írta Geier János, 2002.04.08 Az alábbi logikai paradoxont Jules Richard francia matematikus 1905-ben készítette Tegyük fel, hogy el szeretnénk készíteni a természetes számok tulajdonságinak egy listáját. Először készítsünk egy listát a tulajdonságokról - olyanokról, mint pl. páros, páratlan, 7 többszöröse, teljes négyzetszám, stb. Ezután írjuk le e tulajdonságok definícióit magyar nyelven, hozzá véve a matematikai jelöléseket. Például az előző tulajdonságok definícióit a következőképp adhatjuk meg. ( ':=:' rövidítése az 'akkor és csak akkor, ha' -nak. Az x, y stb. természetes számot fognek jelölni.) 1. Az x páros :=: x maradék nélkül osztható 2-vel. 2. Az x 7 többszöröse :=: x 7-tel osztható. 3. Az x páratlan :=: x -et 2-vel osztva 1 a maradék. 4. Az x négyzetszám, :=: van olyan y szám, melynek önmagával való szorzata egyenlő x-szel, azaz ha van olyan y, hogy x=y*y 5. Az x ikerprím első tagja :=: x is és x+2 is prímszám 6. Az x …… Nevezzük e definíciókat tulajdonságdefiníciónak. Nyilvánvaló, hogy a tulajdonságdefiníciók nem mások, mint valamely rögzített ábécé (bele véve ebbe a matematikai jelöléseket is) segítségével mondjuk magyar nyelven megfogalmazott mondatok. Azaz egy tetszőleges tulajdonságdefiníció azonos egy véges ábécé karaktereiből alkotott véges hosszúságú karaktersorozattal. Valamilyen szabály alapján rendezzük sorba az összes tulajdonságdefiníciót. Legegyszerűbb módja ennek, hogy sorra vesszük a rögzített ábécénk véges hosszúságú összes karaktersorozatait (stringek), először az összes 1 hosszúságú, utána névsorba rakva az összes 2 hosszúságú, majd ugyancsak névsorba rendezve 3, 4, stb hosszúságú stringeket, és sorra véve csak azokat hagyjuk meg, melyek természetes számok tulajdonságát definiálják. A többi (értelmetlen, vagy nem természetes szám tulajdonságára vonatkozó) stringet kihagyjuk, és a sorszámozást összébb tömörítjük, hogy ne legyenek hézagok a sorszámozásban. Ezáltal biztosak lehetünk abban, hogy minden tulajdonságdefiníció a fenti felsorolásban szerepelni fog, továbbá minden tulajdonságdefinícióhoz fog tartozni egy és csak egy természetes szám, az ő sorszáma. Természetesen más megoldás is elfogadható, csak az a fontos, hogy minden tulajdonságdefiníció kapjon egy egyértelmű sorszámot, és viszont: minden sorszámhoz tartozzon egyértelműen egy tulajdonságdefiníció. Csak a magyarázat kedvéért vegyük úgy, hogy a teljes lista a fenti számozással kezdődik. Ha most tekintünk egy tetszőleges természetes számot, mondjuk 142-t, akkor megállapíthatjuk, hogy rendelkezik-e mondjuk a 3. számú tulajdonsággal; azaz érvényes-e rá a 3. számú tulajdonságdefiníció. Erre a konkrét példára megállapíthatjuk, hogy nem érvényes rá, mivel a 3. definíció a 'páratlan' tulajdonságot definiálja, a 142 pedig nem páratlan. Általában igaz, hogy tekintve egy tetszőleges i természetes számot és egy tetszőleges j sorszámú tulajdonságdefiníciót, mindig egyértelműen megállapítható, hogy az i természetes szám rendelkezik-e a j sorszámú tulajdonsággal. Mindig a két lehetőség egyike lesz igaz: vagy érvényes, vagy nem. És most definiáljunk egy új tulajdonságot: Definíció: Egy x Richardszerű :=:az x sorszámú tulajdonságdefiníció nem érvényes x-re. Csak a magyarázat kedvéért például, ha a fenti számozással kezdődne a teljes lista, akkor az 1 és a 2 természetes számok Richardszerűek lennének, a 3 és a 4, és az 5 természetes számok pedig nem. (Tessék meggondolni! Pl. a 4 természetes szám azért NEM Richardszerű, mert a 4 sorszámú definíció a négyzetszámokat definiálja, de a 4 maga is négyzetszám, tehát a 4-hez tartozó tulajdonság-definíció érvényes a 4-re. Hasonlóképp a fenti felsorolásban az 1 és a 2 egyaránt Richardszerű, a 3 és az 5 viszont nem amint azt az olvasó egyszerűen maga is végiggondolhatja.) Mivel a sorba rendezési módszerünk biztosította, hogy minden tulajdonságdefiníciónak van sorszáma, ezért a fenti Definíció -nak is kell, hogy legyen sorszáma, hiszen ez is egy egyértelműen eldönthető tulajdonságát definiálja a természetes számoknak. Jelöljük r- rel a Definíció sorszámát. ( A fentiek alapján r biztosan létezik, de általunk nem feltétlenül ismert.) Kérdés: r Richardszerű vagy sem? Ha feltesszük, hogy r Richardszerű, akkor (a Richardszerű tulajdonság definíciója szerint) nem érvényes rá a hozzá rendelt tulajdonságdefiníció, tehát akkor nem igaz, hogy r Richardszerű. Ha ellenben feltesszük, hogy r nem Richardszerű, akkor (a Richardszerű tulajdonság definíciója szerint) a hozzá rendelt tulajdonságdefiníció érvényes rá, tehát akkor mégis csak igaz, hogy r Richardszerű. (ugorj az elejére…) Ez a Richard paradoxon: a kérdés nem dönthető el. A Richard paradoxonra a mai napig nincs egyértelműen elfogadott feloldás, magyarázat, amit az is bizonyít, hogy elemzéséről szóló egészen friss cikkeket lehet találni. (pl. [2]) Ugyanakkor: ez a Gödel tétel gondolatmenete is. Gödel nem tett mást, mint hogy a Richard paradoxon levezetését és gondolatmenetét a magyar (francia,német, angol..) nyelv helyett a Principia Mathematica formális nyelvén mondta el. Gödel a "tulajdonságdefiníció" helyett "egy szabad változót tartalmazó formulá"-t, az "érvényes rá" kifejezés helyett " levezethető" -t mond, és ezeket formalizálja. Kérdés: Ha a Richard paradoxon paradoxon, akkor a Gödel tétel miért tétel? Mi változik meg attól, hogy ugyanazt egyszer (korrekt, matematikai!) élő nyelven, másszor pedig formálisan mondjuk el? Állítás: Amíg a Richard paradoxon nincs kellőképp tisztázva, addig a Gödel tétel levezetésének helyessége is megkérdőjelezhető. |