Ha halmazelmélettel most ismerkedsz, akkor talán a Komjáth Tanár Úr tanárszakosoknak írt ilyen témájú jegyzete az jó kiindulópont. Van logika jegyzete is. Ezek nem túl hosszúak, érdekesek és kellően részletesen magyaráznak. Mindkettő fönt a szerző honlapján. (A logika 39, a Halmaz 63 oldal)
Ezt elhiszem nektek, mint hozzáértőknek, de szeretném megismerni ezt a nyelvet annyira, hogy magam is meg tudjak benne fogalmazni állításokat. Mintha új programnyelvet tanulnék. Mit javasolsz, hogyan induljak el (milyen irodalommal)? Ha látnám a 'G gráf teljes' állítást ezen a nyelven, szerintem jobban érezném a dolgot.
A gráfok szokásos elsőrendű nyelvén nem formalizálható, hogy út van két pont között. Ezt mutatja az az ultraszorzatos konstrukció, amit néhány hozzászólással ezelőtt írtam. ZFC-ben viszont eddig úgy tűnik, hogy minden kényelmesen formalizálható, még ZFC konzisztenciája is megfogalmazható.
"Én ZFC-beli formalizálásról beszéltem. A gráfok elsőrendű elméletében valószínűleg nem formalizálható minden gráfelméleti állítás"
Én sajnos csak a gráfok elsőrendű elméletét ismerem, mint gráfokról szóló állítások nyelvét: ebben a nyelvben meg is tudok fogalmazni sokmindent, amit szóban.
Pl. egy G gráf összefüggő, az ugye így megy:
Minden x,y,G-re: Ha x eleme G és y eleme G, akkor élvan(G,x,y)
Kiváncsi lennék, hogy hozzávetőlegesen hogy nézhet ki a 'G gráf összefüggő' állítás ZFC-ben.
Érdekesség: Van egy magyar származású kanadai matematikus (Makkai Mihály), aki a sztenderd logikának és halmazelméletnek nagyon komoly és elismert szakértője, mégis a matematika megalapozásának ZFC helyett egy teljesen újfajta kategóriaelméleti toposzelméleti megközelítését dolgozta ki. Van is ebből könyve, de állítólag még halmazelmélet-logika szaktereületű kutatóknak is egy nehéz olvasmány.
"Nem tudom, mi a szokásos "kétvonalas" definíció."
Amit Te is mondtál (egy elméletben valamit pontosan akkor mondunk igaznak, ha az összes elméletet kielégítő modelben igaz). Ha az elméletben levezethető valami az az "egyvonalas" igazság. (És persze teljesség miatt a kettő egybeesik)
Szerencsésebb lett volna az elmélet szemantikai illetve szintaktikai következményeinek mondanom.
"hiszen előfordulhat, hogy a "minden n eleme omega: P(n)" állítás nem tétel annak ellenére, hogy P(0), P(1), P(2), stb. mindegyike az"
Ez ahhoz hasonló, hogy a halmazelmélet bármely véges része esetén tétel, hogy az konzisztens, de az nem tétel, hogy minden véges része konzisztens. Mindenesetre a fenti inkonzisztencia elég zavaró lenne.
Ami még érdekes dolog, hogy ZFC nem tudja eldönteni a saját konzisztenciáját. Itt is úgy érezheti az ember mint a Turing gépes esetben: ha le tudnánk vezetni belőle ellentmondást az rögtön eldöntené a kérdést. Persze ha ellentmondásos, akkor úgyis mindegy, hogy miket bizonyítottak belőle.
No igen, de akkor milyen igazságfogalom szerint "igaz"?
A modellbeli igazság az egy definiált fogalom a matematikában. Aszerint "igaz" valami a modellben.
Valamint az is egy önkényes választás, hogy mely modellre mondom, hogy az az "igazi" számokat írja le, és mely modell ami csupán kielégíti az axiómarendszert, de mégsem az "igazi" számokat írja le.
Van egy olyan lehetőség, hogy egyik sem az "igazi" számokat írja le. Attól függ, hogy az "igazi" számok kívül esnek-e a matematikán vagy sem. Ha nem esnek kívül, akkor definiálhatjuk őket, mint ZFC is teszi. A halmazelméletben a természetes számnak és a rá vonatkozó alapműveleteknek van egy definíciója, ezek alkotják a PA standard modelljét. Mondhatod persze, hogy egy definíció önkényes.
Kicsit olyan érzésem van, mintha az ingoványos szubjektív igazágtartalmú érvek kiküszöbölésére bevezettük volna a szigorú formális levezetős rendszert, de aztán ha nem úgy van valami ahogy szeretnénk, akkor inkább mégsem ragaszkodunk a precízen fölépített igazságfogalmunkhoz.
Szerintem mindig ragaszkodhatunk a halmazelméletben precízen fölépített igazságfogalmunkhoz. Egy X állításról akkor mondjuk, hogy egy axiómarendszerben tétel, ha X levezethető az axiómarendszerből. Tudjuk azt is, hogy az utóbbi ekvivalens azzal, hogy X az axiómarendszer minden modelljében igaz. Egyszerűen arról van szó, hogy az axiomatikus módszer nem alkalmas a dolgok definiálására, a nemteljesség miatt. A definícióhoz más utat kell választani, pl. ZFC-ben megmondod, hogy mit jelent a 3-as szám vagy a szorzás, tehát definiálod őket mint halmazokat. A modellek az axiómarendszerről tudnak érdekes dolgokat mondani, nem pedig egy konkrét struktúráról, ami az axiómákat inspirálta. Úgy is mondhatnánk, hogy az axiómák használata az első próbálkozás volt a matematika precízzé tételére, a halmazelméletre való alapozás pedig a második. Persze a halmazelméletet is axiomatikusan építjük fel, de amint a halmazok intuitív fogalmában megbízunk, minden más precízen definiálható, beleértve az igazság fogalmát is. Ennek nem mond ellent az, hogy a halmazelmélet axiómáinak is sokféle modellje van, és ezek között nincs standard modell, hogy is lehetne.
Ha az igazságot a szokásos "kétvonalas" definícióval definiáljuk
Nem tudom, mi a szokásos "kétvonalas" definíció. Én a Csirmaz-jegyzetben definiált igazságfogalomról beszélek.
Már régebben meg szerettem volna kérdezni: mi az omega-konzisztenciája ZFC-nek?
A ZFC omega-inkonzisztenciája azt jelenti, hogy ha minden n eleme omega esetén ZFC-ben tétel a P(n) állítás, akkor nem lehet tétel az, hogy "van n eleme omega, hogy P(n) hamis". A furcsaság az, hogy az omega-inkonzisztenciából nem feltétlenül következik az inkonzisztencia, hiszen előfordulhat, hogy a "minden n eleme omega: P(n)" állítás nem tétel annak ellenére, hogy P(0), P(1), P(2), stb. mindegyike az.
"akkor egyes PA-modellekben van rá ellenpélda, annak ellenére hogy a sejtés maga igaz (az "igazi számokra")"
No igen, de akkor milyen igazságfogalom szerint "igaz"? Valamint az is egy önkényes választás, hogy mely modellre mondom, hogy az az "igazi" számokat írja le, és mely modell ami csupán kielégíti az axiómarendszert, de mégsem az "igazi" számokat írja le.
Kicsit olyan érzésem van, mintha az ingoványos szubjektív igazágtartalmú érvek kiküszöbölésére bevezettük volna a szigorú formális levezetős rendszert, de aztán ha nem úgy van valami ahogy szeretnénk, akkor inkább mégsem ragaszkodunk a precízen fölépített igazságfogalmunkhoz.
"Azt persze nem kell és nem is lehet elvárni, hogy ami igaz, az levezethető is legyen, hiszen nem kell a ZFC-nek "mindent tudni"."
Ha az igazságot a szokásos "kétvonalas" definícióval definiáljuk, akkor tanulja az ember az iskolában, hogy joggal elvárhatja, hogy ez működjön. Ha egy esetleg valóságból jövő intuició szerint "igaz" valami, annak persze nem várhatjuk a levezethetőségét.
Már régebben meg szerettem volna kérdezni: mi az omega-konzisztenciája ZFC-nek?
Szerintem erre az a megnyugtató válasz, hogy egy ZFC-modell "csak egy ZFC-modell". Egy modell nagyon más is lehet, mint amit intuitíve elvárnánk tőle. Például a PA-nak is vannak olyan modelljei, amiben a "számok" nem igazán számok, és ennek megfelelően furcsaságokat produkálnak. Tehát ha mondjuk a Goldbach-sejtés nem vezethető le PA-ban, akkor egyes PA-modellekben van rá ellenpélda, annak ellenére hogy a sejtés maga igaz (az "igazi számokra"). Az egyes modellekben fellépő ellenpéldák csak amolyan fantomok, a PA "megengedő voltának" következményei, de nem igazi számok.
Mi abban bízunk, hogy a ZFC kellően adekvátan képezi le az "objektív valóságot", tehát ha valami minden modelljében igaz, akkor az "tényleg igaz". Persze valami akkor igaz minden modellben, ha ZFC-ben formálisan levezethető, tehát az elvárásunk csupán az, hogy ha valami levezethető, akkor az úgy is van. Azt persze nem kell és nem is lehet elvárni, hogy ami igaz, az levezethető is legyen, hiszen nem kell a ZFC-nek "mindent tudni".
Előző dologra visszatérve, ha egy Turing gép megállna véges sok lépésben azt be tudnánk bizonyítani, tehát ha ezt nem lehet bebizonyítani, akkor intuitíve azt gondolnánk, hogy nem áll meg. Másrészt ha a nem megállást sem lehet bizonyítani, akkor bizonyos ZFC modellekben megáll másokban nem. Ez engem kicsit zavar, hogy ilyen "objektív valóságok" ZFC modelltől függhetnek. Van erre valami megnyugtató "válasz"?
"Kapásból nem látom, hogy az nem elég, hogy "zárt az izomorfiára és az ultraszorzatra", tehát nem tudok példát ilyen osztályra, ami nem axiomatizálható"
Mondok egy pici segítséget: elemien ekvivalens struktúrák méretei lehetnek nagyon különbözőek, ultraszorzással a méretet nem tudod csökkenteni.
(konkrét megoldást ne írd be, mert még aktív HF az egyik tárgyból)
Igen. Én nem akartam említeni ezt a variánst, mert kicsit mesterkéltnek találtam. Úgy értem, ultrahatvánnyal tökéletes lenne, de ultragyökvonással már nem hangzik olyan jól. Kapásból nem látom, hogy az nem elég, hogy "zárt az izomorfiára és az ultraszorzatra", tehát nem tudok példát ilyen osztályra, ami nem axiomatizálható. (Nincs időm gondolkodni rajta, el vagyok maradva a rendes dolgaimmal.)
"akkor és csak akkor axiomalizálható, ha zárt az elemi ekvivalenciára és az ultraszorzatra"
Sőt Keisler-Shelah Izomorfizmustétel egyszerű következménye, hogy elemi ekvivalencia helyett ultragyökvonást mondva is igaz marad a fenti (aximoatizálhatóság alatt persze elsőrendű formulákkal való aximatizálhatóságot értve).
Emiatt például véges gráfok nem axiomatizálhtók, mert ultraszorzatuk könnyen lehet végtelen gráf vagy egyre nagyobb páratlan körök ultraszorzata ha jól emlékszem kontinuum sok diszjunkt út így speciel körmentes stb
Igen. Általánosan igaz az, hogy adott típusú struktúrák egy osztálya akkor és csak akkor axiomalizálható, ha zárt az elemi ekvivalenciára és az ultraszorzatra (Csirmaz-jegyzet 8.17 tétel).
"(Sajnos az ottani diszkusziót nem teljesen értem, ezért nem vagyok biztos benne 100%-ig, hogy az összefüggőség tényleg nem elsőrendben megfogalmazható tulajdonság, de 99%-ig azért biztos vagyok benne.)"
Nyilván nem formalizálható a gráfok elsőrendű elméletében, hisz még azt sem tudod mondani, hogy két csúcs között vezet út. Ez onnan (is) látszik, hogy veszed azokat a gráfokat, hogy az n-edik az n hosszú út. Ezeknek veszed egy nemfő ultraszűrő szerinti ultraszorzatát. Tekinted az utak egyik végpontjai által definiált ekvivalencia-osztályt meg a másik végpontok általit. Ha lehetne mondani, hogy út van 2pont között akkor Los-lemma miatt lenne út az ultraszorzatban, de ha bármely konkrét n-t veszek akkor ultrasok koorninátán nincs n hosszú út, így az ultraszorzatban sincs. (Ezt ma hallottam, elég frappáns)
Én ZFC-beli formalizálásról beszéltem. A gráfok elsőrendű elméletében valószínűleg nem formalizálható minden gráfelméleti állítás. Egyébként ha az axiómarendszer kellően gazdag, akkor több, minden formalizálható benne, mint elsőre látszik. Pl. a Collatz-sejtés (lásd http://en.wikipedia.org/wiki/Collatz_conjecture) megfogalmazható a Peano-aritmetikában (erre Komjáth Péter hívta fel a figyelmemet éppen egy itteni hozzászólásom kapcsán).
Annyival egészíteném ki, hogy abban sem vagyok biztos, hogy az adott állítás másodrendben megfogalmazható (azzal tévesztettem, össze, hogy nyilván megfogalmazható olyan nyelvben, ami elsőrendű + használni lehet benne a tranzitív lezárt operátort. Ilyen különféle erejű nyelvekről akkor olvastam, amikor a P vs. NP kapcsán belenéztem a Finite Model Theoryba.)
