A matematikai állítások megértéséhez a turing-gépes felfogás nem visz közelebb.
Talán csak egy olyan érzetet adhat egy laikusnak is, hogy a matematikai igazságok objektívek, embereken kívülállóak.
A logikai tautológiákat, következtetési szabályokat az emberk még mindig hajlamosak emberinek gondolni: gondolkodásunk elemei, papírral ceruzával emberek írják le... Ráadásul az axiómarendszerek olyan megfoghatatlanok, relatívnak tűnnek: egymásban is modellezhetők...
Ha valaki elé raknak egy mechanikai szerkezetet, meg egy szalagot, és azt mondják, hogy az állítás az, hogy ez a gép meg fog állni, az ad az egésznek egy kőkemény objektivitás érzetet. Megértést viszont nem, ebben egyetértek.
Mint mondtam, ezzel együtt kell élni. Homályos fogalmakból és gondolatokból kiindulva érjük el a "matematikai precizitást". Fogd fel egyfajta evolúciónak az agyban: ahogy a gügyögésből egyszer csak költészet lesz, úgy a "sok-kevés, enyém-tied" fogalmakból egyszer csak ZFC lesz.
De amikor emberekkel beszélgetünk, akkor nem használjuk direkte a gügyögést. Elvileg a matematika egy olyan dolog, ami sokat fejlődött, sokat kell tanulni stb., de amikor készen van, onnantól kezdve elvileg nem kell a gügyögés.
Azt mondod, hogy miután megvan a ZFC, azután precízen fel lehet vele építeni mindent. De nekem pont ez a bajom, hogy amikor már felépítettük ZFC-t, akkor a precíz igazságdefiníció (ami nem használja mondjuk a 17. századi matematikát) mindig csak egy metanyelvben ellenőrizhető (ami itt szerintem nem a gügyögés, mert az is egy felépített ZFC). És abba, hogy algoritmikusan valamit ellenőrizni tudj, nem fér bele, hogy végtelensok ZFC-t kiértékelj.
Nekem ezzel is az a bajom, hogy amikor megalkotjuk pl. a Turing-gép fogalmát, akkor szükségképpen használunk egy olyan metanyelvet, ami nem matematikai precizitású. És bármilyen absztrakt matematikai definíciót alkotunk (elsőrendű nyelv, Turing-gép), mindig használjuk a "bizonyításainkban" ezt a nyelvet. (Pl: egy bővebb halmazon kvantifikálunk, mint amiről beszélni szeretnénk).
Nem hiszem, hogy a Turing-gép fogalma egyszerűbb lenne, mint a természetes számoké. Más szóval a természetes számokról nem nehezebb kialakítani az egyezményes intuíciót, mint a Turing-gépről, sőt. Nem véletlen, hogy a matematika története a geometria és a számelmélet történetével kezdődött: ezek a legkézenfekvőbb fogalmak, amiket az életből megismerünk és matematikailag vizsgálhatunk. Egyébként a matematika formalizmusa nem áll távol a Te elképzelésedtől. Az axiómákból formálisan generálhatók (megadott logikai szabályok szerint) a tételek, és ezek halmaza az elmélet. A ZFC tételeit is pontosan így lehet generálni, tehát egy megfelelő programmal végtelen sok időben megtalálható az összes ZFC-tétel. Ez teljesen korrekt. De: nekem problémás, ha valaki a formalizmust az elé kívánja helyezni, aminek leírására az hivatott. A kotta nem helyettesíti a zenét, és nem is alapvetőbb nála. A ZFC-t nem kötelező használni. Aki nem érti és nem tudja használni a ZFC-t, az nem érti a matematikát. Attól, hogy odaadjuk neki a Turing-gépet, ami legyártja a ZFC tételeit, még nem fogja érteni a ZFC-t. Mint ahogy Mozart zenéjét se érti valaki, ha a kottát elérakjuk és elmagyarázzuk, hogy a kotta jelölései mit takarnak. Előbb van a zene, utána a kotta.
Igen, nem látom át, hogy ez a felfogás milyen problémákhoz vezethet...
Pl. ami a legzavaróbb, hogy a Goldbach sejtést fel lehet írni olan programként is, ami megy végig a páros számokon, és nézi, hogy van-e felbontás...
De fel lehet írni úgy is, mint az előző hozzászólásomban mondtam: megy végig a ZFC beli bizonyításokon, és nézi, hogy melyik a bizonyítása a Goldbach tételnek.
Namost pl. nem tirvi, hogy milyen szabályok alapján mondjuk, hogy két állítás ekvivlens. A normál matematikai logikában ha ekvivalens két állítás, akkor elemi lépésekkel egymásba vihetők. Itt ez nem tűnik tlejesen triviálisnak.
Még annyit, hogy amit pl. én írtam az nem korlátozza le, hogy mivel foglalkozhat a matematika, csak ad egy intuitív alapot mindennek (ezért lehet, hogy üres filozofálgatás).
Ugyanis bármilyen elvont ZFC beli állítás amit a matematikusok kitaláltak is modellezhető Turing gép programjaként:
Azt a programot vesszük, ami megy végig a ZFC beli bizonyításokon és megáll, ha az adott bizonyítás a megfelelő ZFC beli tétel egy bizonyításának bizonyul.
Én régebben azon gondolkodtam, hogy ha már valamit intuitívan el kell fogadnunk, mi lenne az, ami a leg 'objektívebb' lenne. Mindegy milyen nehézkes formalizmus, csak tűnjön nagyon objektívnak.
Nem gondoltam bele rendesen, de olyanra gondoltam, hogy számomra a 'legobjektívebb' az lenne, ha egy egyszerű működésű gépet fogadnánk el abszolút alapnak. Mondjuk egy egyszerű Turing gépet.
Minden állítást Turing gépbeli programként írnánk le, és akkor lenne abszolút IGAZ egy állítás, ha arra mint bemenetre megállna az a Turing gép.
Pl. a Goldbach sejtés az egy olyan program, ami megy végig a páros számokon, és ha valamelyik nem áll elő két prím összegeként, akkor megáll.
Ha ez a program megáll, akkor a Goldbach sejtés IGAZ.
Egy Turing gép felfogható és meg is építhető egy mechanikai szerkezetként, így legalábbis egy laikus számára megofoghatóbb mint pl. a ZFC.
Persze ezt messze nem gondoltam át mélyebben, nincs is meg hozzá a halmazelméleti, matematikai logikai képzettségem.
Mintha olvastam volna valamit arról, hogy voltak matematikusok akiket ez a dolog annyira aggasztott, hogy azzal próbálkoztak hogy csak olyan dolgokat fogadnak el amit sikerül valamiféle módon mechanikusan modellezni. :-)
Szerintem te azt szeretnéd, hogy a matematika teljesen precízen legyen felépítve a nulláról. Csakhogy nem lehet, és ebbe bele kell törődni. Ahogy az emberek megtanulnak járni, beszélni stb. "a nulláról", úgy megtanulják a ZFC-t is használni (előtte megoldanak egy csomó haladóbb feladatot stb.). Ha már valaki tudja a ZFC-t használni, akkor felépíthet benne mindent teljesen precízen.
Az a gond, hogy én sem tudom pontosan, hogy mi a gond:D
Tegyük fel, hogy adva van a ZFC szintaktikájának a felépítése. Ehhez használtuk a halmazelméletet, így használtuk ZFC-t (mivel azt mindig elé tesszük), de ez nem lehet ugyanaz a ZFC (vagy igen?), hanem egy "meta" ZFC, legyen mondjuk ez ZFC2. De ZFC2-n mik az igaz formulák? Ennek a precíz meghatározásához szükség van egy ZFC3-ra. És így tovább... Tehát akkor:
1. Vagy van egy olyan legelső ZFC, amelyiknél nincsen igazság-fogalom, csak levezethetőség-fogalom, vagy
2. Végtelen sok ZFC-t kell axiomatizálni, és az ottani formulák igazsága mindig egy "előző" ZFC-től függ.
Engem mindkettő zavar valamennyire... mert ha az 1. az igaz, akkor a metanyelven nincs igazságfogalom, ha meg 2. igaz, akkor precízen definíció szerint csak úgy tudjuk megmondani egy formuláról, hogy igaz-e, hogy végtelensok ZFC-t ellenőrzünk. (Vagy nem?)
Várom a törpés feladatra a megoldást mert nagyon érdekes:D
Egyébként sajnos tényleg nem volt jó a "bizonyítás" a ZFC inkonzisztenciájára. Az alap ötletem az volt, hogy vettem a Berry paradoxont:
"Bertrand Russell G. G. Berrynek, az oxfordi egyetem könyvtárosának tulajdonítja a legkisebb olyan pozitív egész szám, amely nem nevezhető meg kevesebb, mint harminc szótaggal problémáját. A szóban forgó számot viszont épp a fenti kifejezés nevezi meg - huszonkilenc szótag felhasználásával."
És valamilyen Gödel-számozás segítségével próbáltam rekonstruálni a paradoxont. Sajnos a megoldás valahol mindig kicsúszik a kezeim közül, dehát ügyes dolog ez a PA.
Másik dolog: Az igazságnak az igazságértékeléses definíciója nem használ másodrendű halmazelméletet? Mert amikor alkotunk egy struktúrát, az csak egy naiv halmazelméleti dolog, elé kell még rakni ZFC-t, hogy teljesen korrekt legyen. Viszont ha vesszük a ZFC-n igaz mondatokat, akkor ZFC alaphalmaza egy halmaz lesz. Akkor most mi van?
Átgondoltam megszámlálhatóan végtelen színnel. Ekkor könyebb mint a véges eset.
Ekvivalenciaosztáky a szokásos. Leghátsó törpe megnézi, hogy hol van az utolsó eltérés, mondjuk az n. helyen. Ekkor ő a Prod (i=1...n) (p_i)^(k_i) számnak megfelelő színt mondja, ahol p_i az i-edik prím és k_i az i-edik törpe színének száma.
Gondolkoztam a kszí szín és kappa törpe esetén. Azt hiszem, ha kappa rákövetkező számosság és cf(kszí)>=kappa, akkor GCH mellett megoldható, de nem akarok butaságot mondani ezért inkább még átgondolom.
Továbbgondoltam a megoldásodat k színre, remélem immárom jól.
Színekhez rendeljük a 0,1,...,k-1 számokat. A véges sok helyen különböző sorozatok legyenek az ekvivalenciaosztályok, ahonnan választunk reprezentást. A leghátsó törpe öszegzi törpénként a sapkakiosztás számainak a reprezentánstól való eltéréseit mod k és megmondja a kijövő számnak megfelelő színt. Ebből aztán sorban ki tudják számolni a sajátjukat.
nálam két sorozat akkor ekvivalens ha van olyan n,m hogy az egyik első n tagját és a másik első m tagját elhagyva egyenlőek lesznek
Ezen a reláción én is gondolkodtam, és hasonlóan gyártottam egy hibás megoldást. Érzésem szerint a hibás megoldás orvosolható, szétválasztva a periodikus és aperiodikus sorozatokat. Aztán megoldottam véges sok törpére a feladatot, amikor is a törpék kiszámolhatják az általuk látott véges sorozat paritását. Ez inspirált a végleges megoldásomra, nevezetesen igyekeztem a végtelen esetben is egy véges részt hozzárendelni a törpékhez, aminek már ki tudják számolni a paritását.
"ekvivalenciaosztályokat (ugyanazok mint a Tieid)"
Jobban átgondolva ez nem igaz, mert nálam két sorozat akkor ekvivalens ha van olyan n,m hogy az egyik első n tagját és a másik első m tagját elhagyva egyenlőek lesznek.
Azaz az én ekvivalenciaosztályaim bővebbek általában.
Közben rájöttem, hogy megszámlálhatóan végtelen szín esetén is működik a dolog, ugyanúgy lényegében mint végesre.
Az nem gond, hogy - ha jól értem a megoldásokat - a törpéknek a teljes végtelen sorozatot kellene kiértékelniük? Erre Chuck Norris is böszke lenne, nem?
"Ha egy rekurzív formula igaz omegán, akkor az igazsága bizonyítható PA-ban"
Ez így nem teljesen jó. Helyesen ha egy rekurzív formula igaz omegán valamely értékadással, akkor bizonyítható PA-ban (sőt Q-ban), hogy ez a formula az adott számokra igaz.
"Sigma_1-formula igaz omegán az is bizonyítható PA-ban"
Most látom, hogy véges sok sapkaszínre is megoldható, például ha az én megoldásomban f:{0,1,...k-1}^omega -->{0,1,...k-1} függvényt keresek, a szabály pedig f(ls)=l+f(s) mod k. Ahol l in {0,1,...k-1}, s in {0,1,...k-1}^omega, az egymásmelléírás pedig a megfelelő szín hozzáillesztése a sorozat elejére.
A függvény keresése pedig történhet úgy, hogy tekintem az ekvivalenciaosztályokat (ugyanazok mint a Tieid), mindegyikből kiveszek egy tetszőleges elemet és ezeken előírom f-et tetszőlegesen. Ekkor a fenti szabály egyértelműen előírja az összes többi helyen az értékeit.
Én kicsit másképp csináltam. Kimutattam, hogy van olyan f:{0,1}^omega -->{0,1} függvény ami értéket vált ha egy 1est írunk az input sorozat elé és értket tart ha 0-át.
Két sapkasorozatot nevezzünk ekvivalensnek, ha csak véges sok helyen különböznek. A törpék válasszanak minden ekvivalencia-osztályból egy reprezentánst. Amikor felállítják őket, mindegyik törpe be tudja azonosítani a kitalálandó sorozattal ekvivalens reprezentáns sorozatot, és így azt is, hogy a két sorozat páros vagy páratlan számú elemben különbözik-e az általa látott részben. Nevezzük ezt a számot az adott törpe paritásának. A legelső törpe árulja el a saját paritását így: fekete = páros, fehér = páratlan. Ebből az információból a második törpe ki tudja találni a saját sapkája színét, hiszen az ő paritása pontosan akkor egyezik meg az előző paritással, ha a fején olyan sapka van, mint a reprezentáns sorozatban. A második törpe árulja el a sapkája színét, ekkora harmadik törpe rekonstruálni tudja a második törpe paritását, amiből pedig ki tudja találni a saját sapkája színét, és így tovább.
Remélem jó, mert elég álmos vagyok és más dolgok járnak a fejemben.
Mondtam régebben egy törpés példát, amit féligmeddig ismertél és tetszett. Ma hallottam egy frappáns általánosítását. Sikerült megoldanom, szerintem jópofa:
Van megszámlálhatóan végtelen sok törpe. Összebeszélhetnek, majd utána sorbaállítják őket és mindegyik kap egy sapkát a fejére. Vagy feketét vagy fehéret. Mindenki csak az előtte lévőkét látja és nem kommunikálhatnak. Ezután a leghátsótól kezdve sorban tippelnek a saját sapkájuk színére. Adj olyan stratégiát, amellyel legfeljebb egy törpe hibázik.
Ha egy rekurzív formula igaz omegán, akkor az igazsága bizonyítható PA-ban, sőt ha egy ugynevezett Sigma_1-formula igaz omegán az is bizonyítható PA-ban. Sőt PA-ban bizonyítható az, hogy a fentiek bizonyíthatók PA-ban.
Ez útóbbit úgy hívják, hogy "provable Sigma-1-completeness" és a Gödel második nemteljeségi tételénél jön elő.
A fentiek első fele a Csirmaz-jegyzetben teljes részleteséggel igényesen le van írva.
A provable Sigma-1-completeness az Boolos-nak a Logic and Provability könyvében hasonlóan élvezhető kivitelezésben.
