Forszol´as Pint´er Gerg˝o
1.
A halmazelm´ elet r¨ ovid t¨ ort´ enete
˝ vette ´eszre, 1870-t˝ ol: Cantor halmazelm´ elete. A halmazelm´elet megalkot´oja Georg Cantor. O hogy az, hogy valamib˝ ol v´egtelen sok van, t¨obb dolgot is jelenthet, k¨ ul¨onbs´eget lehet tenni a v´egtelenek k¨ oz¨ ott: p´eld´ aul a racion´alis sz´amok ugyanannyian vannak, mint a term´eszetes sz´amok (ezt nevezz¨ uk megsz´ aml´ alhat´oan v´egtelennek), viszont a val´os sz´amok t¨obben vannak. Cantor defini´ alta prec´ızen, hogy mit is jelent v´egtelenek k¨oz¨ott a t¨obb/kevesebb/ugyanannyi, ´es meghat´ arozta a legalapvet˝ obb halmazok sz´amoss´ag´at. P´eld´aul: • K´et halmaz sz´ amoss´ aga egyenl˝o, ha az elemeik p´arba ´all´ıthat´oak egym´assal. • Megsz´ aml´ alhat´ oan v´egtelen halmazok: term´eszetes sz´amok; eg´esz sz´amok; p´aros sz´ amok; racion´ alis sz´ amok; egy s´ıkbeli, t´erbeli vagy tetsz˝oleges dimenzi´os r´acs pontjai; az eg´esz/ racion´ alis egy¨ utthat´ os polinomok (´es ´ıgy az algebrai sz´amok); a term´eszetes sz´amok v´eges r´eszhalmazainak a halmaza; ... • Kontinuum sz´ amoss´ ag´ u halmazok: val´os sz´amok; irracion´alis sz´amok; tetsz˝oleges (nem elfajul´ o) intervallum pontjai; a s´ık/t´er/tetsz˝oleges v´eges dimenzi´os t´er pontjai; a term´eszetes sz´ amok hatv´ anyhalmaza (¨ osszes r´eszhalmazainak a halmaza); ... Cantor ´eszrevette, hogy ”v´egtelen sok” k¨ ul¨onb¨oz˝o sz´amoss´ag van. P´eld´aul tetsz˝oleges halmaz hatv´anyhalmaza nagyobb sz´ amoss´ag´ u, mint maga a halmaz. 1900: Hilbert nevezetes probl´ em´ ai k¨oz¨ott els˝o helyen szerepelt a kontinuumhipot´ezis. A legkisebb v´egtelen sz´ amoss´ ag a megsz´aml´alhat´oan v´egtelen, de vajon mi a k¨ovetkez˝o? A kontinuumsejt´es szerint a kontinuum a k¨ovetkez˝o v´egtelen sz´amoss´ag, m´ask´epp fogalmazva: nincs olyan halmaz, ami nagyobb sz´ amoss´ag´ u volna, mint a term´eszetes sz´amok halmaza, de kisebb sz´amoss´ ag´ u, mint a val´ os sz´ amok. Ezt a sejt´est azonban nem tudt´ak bebizony´ıtani, ´es megc´ afolni sem siker¨ ult. 1901: Russel-paradoxon. Vegy¨ uk azokat a halmazokat, amik nem elemei ¨onmaguknak. Ezen halmazok halmaza eleme-e ¨ onmag´ anak? Form´alisan: R = {S | S ∈ / S}, a k´erd´es az, hogy R eleme-e ¨onmag´ anak? Ak´ ar igennel, ak´ ar nemmel v´alaszolunk, ellentmond´ast kapunk. Ez a paradoxon ´all´ıt´olag Zermelot´ ol sz´ armazik. Nem ez volt az els˝ o ellentmond´ as a halmazelm´eletben, p´ar ´evvel azel˝ott Cantor is r´aj¨ott, hogy ”az ¨osszes sz´ amoss´ agok halmaza” is ellentmond´ashoz vezet. M´as paradoxonok is megjelentek akkoriban. Az ellentmond´ asok kik¨ usz¨ ob¨ ol´es´ere t¨obb f¨ uggetlen project is l´etrej¨ott, a legsikeresebb a halmazelm´elet axiomatikus alapokra helyez´ese lett. E szerint a megk¨ozel´ıt´es szerint a paradoxonok gy¨okere az, hogy Cantor ”na´ıv” halmazelm´eletet csin´alt. Nem r¨ogz´ıtette le el˝ore, hogy egy´ altal´ an milyen halmazokat lehet gy´ artani. Tetsz˝oleges ”¨osszess´eg” halmaznak sz´am´ıtott, ez´ert ny´ılt lehet˝os´eg ¨ onhivatkoz´ o konstrukci´ ok gy´art´as´ara, amik azt´an ellentmond´asra vezettek. A ZFC-axi´ omarendszer az 1920-as ´ evekre kezdett ¨ossze´allni. Ez az axi´omarendszer v´eg¨ ul is egy receptgy˝ ujtem´eny, hogy m´ ar megl´ev˝o halmazokb´ol hogyan lehet u ´jakat gy´artani. Emellett mind¨ ossze egy halmaz l´etez´es´et garant´alja felt´etelek n´elk¨ ul. Az ellentmond´asokat ezzel u ´gy 1
sz¨ unteti meg, hogy az ellentmond´ast okoz´o halmazok egyszer˝ uen nem halmazok: imm´ ar t´etel, hogy nem l´etezik az ¨ osszes halmazok halmaza, az ¨osszes sz´amoss´agok halmaza, az ¨onmagukat nem tartalmaz´ o halmazok halmaza stb. Ez a megold´ as tal´ an er˝ oltetettnek t˝ unhet, de nem az: val´oj´aban a ZFC axi´omarendszerben az eg´esz matematik´ at f¨ ol lehet ´ep´ıteni, vagyis minden halmazt megenged, amire sz¨ uks´eg¨ unk van. Persze h´ atra volt m´eg annak a bizony´ıt´asa, hogy a ZFC ellentmond´asmentes. Azt is szerett´ek volna bebizony´ıtani, hogy ez az axi´omarendszer teljes, vagyis tetsz˝oleges halmazelm´eleti ´ all´ıt´ asr´ ol eld¨onthet˝ o, hogy igaz-e vagy sem (vagyis b´armilyen ´all´ıt´ast be lehet bizony´ıtani vagy meg lehet c´afolni). Ez adta az akkoriban sz¨ ulet˝o matematikai logika f˝o motiv´aci´oj´at. A Kiv´ alaszt´ asi axi´ oma k¨ or¨ uli vit´ ak. Zermelo 1904-ben bizony´ıtotta a J´olrendez´esi t´etelt, amely szerint minden halmaz j´ olrendezhet˝o. A t´etel bizony´ıt´as´ahoz kimondta ´es felhaszn´alta a Kiv´alaszt´ asi axi´ om´ at, ami a t´ amad´asok k¨oz´eppontj´aba ker¨ ult: el˝ofordulhat, hogy ez az axi´ oma hozza be az ellentmond´ asokat a halmazelm´eletbe? Zermelo v´alaszul megmutatta, hogy a Kiv´alaszt´ asi axi´ om´ at hallgat´ olagosan eddig is haszn´alt´ak, az anal´ızis legalapvet˝obb t´eteleihez is sz¨ uks´eg van r´ a (vagy gyeng´ebb v´altozataira). V´eg¨ ul az ´erdek gy˝ozedelmeskedett: az 1920as ´evekben Kuratovsky ´ altal f¨ olfedezett Zorn-lemm´ar´ol kider¨ ult, hogy ekvivalens a Kiv´ alaszt´ asi axi´om´ aval, ´es a matematika legk¨ ul¨onb¨oz˝obb ter¨ uletein n´elk¨ ul¨ozhetetlennek bizonyult a lemma, ´ıgy k´enytelenek voltak elfogadni a Kiv´alaszt´asi axi´om´at is. 1930-as ´ evek: G¨ odel teljess´ egi ´ es nemteljess´ egi t´ etelei. A matematikai logika legfontosabb eredm´enyei. A teljess´egi t´etel szerint ha egy ´all´ıt´as k¨ovetkezm´enye egy axi´omarendszernek, akkor bizony´ıthat´ o is. Ez j´ o, ezt v´ artuk, hogy ´ıgy legyen: ami igaz, azt be lehet bizony´ıtani. Egy m´asik megfogalmaz´ as m´ ar picit meglep˝obb: ha egy axi´omarendszer ellentmond´asmentes, akkor van modellje, vagyis olyan halmaz a megfelel˝o f¨ uggv´enyekkel ´es rel´aci´okkal ell´atva, amelyre igazak az axi´ om´ ak. A nemteljess´egi t´etelek kicsit megr´az´obbak: ha egy axi´omarendszer ellentmond´asmentes ´es megfelel˝ oen er˝os, akkor biztosan fell´ep benne eld¨onthetetlen ´all´ıt´as (vagyis olyan ´ all´ıt´ as, hogy sem ˝ o, sem a tagad´asa nem bizony´ıthat´o az adott axi´omarendszerben). A m´asodik nem teljess´egi t´etel szerint pedig maga az ellentmond´asmentess´eg(nek valamik´eppen megfelel˝ o formula) ilyen, azaz ha egy megfelel˝oen er˝os axi´omarendszer ellentmond´asmentes, akkor a rendszeren bel¨ ul nem bizony´ıthat´o az ellentmond´asmentess´ege. 1941: G¨ odel speci´ alis modellje. Felt´etelezve, hogy a halmazelm´elet (vagyis a ZFC axi´omarendszer) ellentmond´ asmentes, azaz van valamilyen modellje, G¨odel legy´artott egy m´asik modellt, amiben automatikusan teljes¨ ul a kontinuumhipot´ezis ´es a Kiv´alaszt´asi axi´oma. Ezzel bel´ atta, hogy a Kiv´ alaszt´ asi axi´ oma nem hoz ellentmond´ast a rendszerbe: ha t¨obbi axi´oma (ZF) ellentmond´ asmentes, akkor a Kiv´ alaszt´asi axi´oma hozz´av´etel´evel (ZFC) is az marad. M´ asr´eszt pedig a kontinuumhipot´ezis sem vezet ellentmond´asra, vagyis k´et dolog lehets´eges: vagy be lehet bizony´ıtani, vagy f¨ uggetlen ZFC-t˝ol. Az az egy nem fordulhat el˝o, hogy a kontinuumhipot´ezis ellenkez˝ oj´et be lehet bizony´ıtani. 1963: Paul Cohen f¨ olfedezte a forszol´ ast. Ezzel az u ´j elj´ar´assal bebizony´ıtotta, hogy a kontinuumhipot´ezis f¨ uggetlen a ZCF axi´omarendszert˝ol: se ˝o, se a tagad´asa nem bizony´ıthat´o ´es nem vezet ellentmond´ asra. A forszol´ as a halmazelm´elet eg´eszen u ´j fejezet´et nyitotta meg, kider¨ ult, hogy ennek seg´ıts´eg´evel rengeteg ´all´ıt´asr´ol be lehet bizony´ıtani, hogy nem vezet ellentmond´ asra. Ezek legt¨ obbje halmazelm´eleti illetve val´os f¨ uggv´enytani ´all´ıt´as.
2. 2.1.
A halmazelm´ elet axi´ om´ ai A ZFC axi´ omarendszer (Zermelo-Fraenkel + Axiom of choice)
A halmazelm´elet nyelve egy darab rel´ aci´ojelb˝ol, az ∈ jelb˝ol ´all. Ez azt jelenti, hogy az axi´om´ak logikai jelekb˝ol (∧: ´es, ∨: vagy, ∀: minden, =: egyenl˝o stb.) ´es az ∈ jelb˝ol ´all´o formul´ak. Minden v´ altoz´ ojel halmazt jel¨ol, m´ as objektumokra nincsen sz¨ uks´eg. 2
1. Meghat´ arozotts´ agi axi´ oma: Ha k´et halmaznak ugyanazok az elemei, akkor a k´et halmaz megegyezik. ∀x∀y (∀z(z ∈ x ↔ z ∈ y) → x = y) 2. P´ ar axi´ oma: Tetsz˝ oleges k´et halmazhoz van olyan halmaz aminek pontosan ezek az elemei. ∀x∀y∃z(w ∈ z ↔ (w = x ∨ w = y)) Azaz minden x, y halmazhoz l´etezik a z = {x, y} halmaz. 3. Uni´ o axi´ oma: Halmaznyi sok halmaz uni´oja is halmaz. ∀x∃y(z ∈ y ↔ (∃w(z ∈ w ∧ w ∈ x))) S Azaz minden x halmazhoz l´etezik az y = ∪x = w∈x w halmaz, az x (elemeinek az) uni´ oja. 4. Hatv´ anyhalmaz axi´ oma: Egy halmaz ¨osszes r´eszhalmazainak a halmaza is halmaz. ∀x∃y(z ∈ y ↔ (∀w(w ∈ z → w ∈ x))) Azaz minden x halmazhoz l´etezik y = P(x) = {z | z ⊆ x}, az x hatv´anyhalmaza. 5. R´ eszhalmaz axi´ omas´ ema: Egy halmaz bizonyos tulajdons´ag´ u elemei halmazt alkotnak. Minden φ formul´ ara: ∀~ p ∀x∃y(z ∈ y ↔ (z ∈ x ∧ φ(z, p~))) . Azaz (a p~ param´eterek tetsz˝ oleges r¨oz´ıt´ese mellett) minden x halmazhoz l´etezik y = {z ∈ x | φ(z, p~)}, az x ”φ tulajdons´ag´ u” elemeinek a halmaza. Ezen a ponton ´erdemes bevezetni a f¨ uggv´eny fogalm´at. Defini´aljuk el˝osz¨or a rendezett p´ art: (x, y) = {{x}, {x, y}}, vagy b´ armi olyan kifejez´es megfelel, amellyel (x, y) = (z, w) ↔ (x = z ∧ y = w) teljes¨ ul. Egy f halmaz f¨ uggv´eny, ha minden eleme rendezett p´ar ´es minden x-hez legf¨oljebb egy olyan y van, amellyel (x, y) ∈ f . Szok´ asosabb ´ır´asm´odban: f (x) = y. Az k¨ ul¨on bizony´ıt´ast ig´enyel, ´es az eddig f¨olsorolt axi´ om´ akb´ ol k¨ ovetkezik, hogy egy f¨ uggv´eny ´ertelmez´esi tartom´anya ´es ´ert´ekk´eszlete is halmaz. Vannak olyan hozz´ arendel´esek, amik nem f¨ ugv´enyek, mert az ´ertelmez´esi tartom´anyuk nem halmaz, p´eld´aul a mindenen ´ertelmezett x 7→ {x}. Ezeket oper´ aci´ oknak nevezz¨ uk. 6. P´ otl´ as axi´ omas´ ema: Egy oper´ aci´ot halmazra megszor´ıtva f¨ uggv´enyt kapunk. (M´ask´eppen: egy halmaz oper´ aci´ on´ al vett k´epe is halmaz.) Minden φ(z, w, p~) formul´ ara: ∀~ p (∀z∃!wφ(z, w, p~) → ∀x∃y(w ∈ y ↔ ∃z(z ∈ x ∧ φ(z, w, p~)))) . Azaz, ha a φ formula a p~ param´eterekkel oper´aci´ot defini´al, akkor minden x halmaznak ezen oper´aci´ o szerinti k´epe, y = {w | ∃z ∈ x, hogy φ(z, w, p~)} is halmaz. 7. V´ egtelens´ egi axi´ oma: Van v´egtelen halmaz. ∃x (∃w(w ∈ x ∧ ∀z(z ∈ / w)) ∧ ∀w(w ∈ x → ∃z(z ∈ x ∧ (y ∈ z ↔ (y ∈ w ∨ y = w))))) Azaz l´etezik az x = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . .} halmaz, a term´eszetes sz´amok halmaz´anak Neumann-f´ele modellje (0 = ∅, n + 1 = {0, 1, 2, . . . , n} = n ∪ {n}). 8. J´ olfund´ alts´ agi axi´ oma: Minden nem u ¨res halmaznak van t˝ole diszjunkt eleme. ∀x (∃w(w ∈ x) → ∃y(y ∈ x ∧ ∀z(z ∈ / x∨z ∈ / y))) 9. Kiv´ alaszt´ asi axi´ oma: Ha egy halmaz elemei nem u ¨res halmazok, akkor van olyan f¨ uggv´eny, amely mindegyik¨ ukb˝ ol kiv´ alaszt egy elemet. ∀x (∀y(y ∈ x → ∃z(z ∈ y)) → ∃f ((f : x → ∪x f¨ uggv´eny) ∧ ∀y(y ∈ x → f (y) ∈ y))) 3
2.2.
Megjegyz´ esek
• Ez v´egtelen sok axi´ oma: a k´et axi´omas´ema minden formul´ara egy-egy axi´oma, formul´akb´ ol pedig (megsz´ aml´ alhat´ oan) v´egtelen sok van. • A R´eszhalmaz axi´ omas´ema k¨ ovetkezik a P´otl´asb´ol, teh´at azt f¨ol¨osleges k¨ ul¨on f¨oltenni. • Ha azonban m´egis f¨ oltessz¨ uk, akkor az Uni´o, a Hatv´anyhalmaz ´es a P´otl´as axi´om´akat is gyeng´ıthetj¨ uk: el´eg az ezen axi´ om´ akban szerepl˝ o y-n´al b˝ovebb halmaz l´etez´es´et f¨oltenni, hiszen ebb˝ol m´ar k¨ ovetkezik az y l´etez´ese is a R´eszhalmaz axi´omas´ema miatt. • A P´otl´ as ´es a R´eszhalmaz axi´ omas´em´akban a p~ t¨obb v´altoz´ot jel¨ol(het), ezek u ´gymond param´eterek. Bizonyos tulajdons´ agoknak eleget tev˝o halmazok ”¨osszess´eg´et” oszt´ alynak nevezz¨ uk, vagyis egy adott φ(x, p~) formul´ at (r¨ogz´ıtett param´eter´ert´ekek mellett) kiel´eg´ıt˝o x-ek oszt´ alyt alkotnak. A R´eszhalmaz axi´ omas´em´at ´ıgy is fogalmazhatjuk: halmaz ´es oszt´aly metszete halmaz. • Egyetlen axi´ oma van, amely egy halmaz l´etez´es´et mondja ki, a v´egtelens´egi axi´oma. A t¨ obbi axi´oma (a Meghat´ arozotts´ ag kiv´etel´evel) mind arr´ol sz´ol, hogy m´ar megl´ev˝o halmazokb´ol milyen u ´j halmazokat lehet el˝ o´ all´ıtani. • A J´olfund´ alts´ ag csak egy technikai f¨oltev´es, ezzel kiz´arjuk p´eld´aul azt, hogy egy halmaz eleme lehessen ¨ onmag´ anak, vagy hogy x ∈ y ´es y ∈ x is f¨onn´allhasson. • A kumulat´ S ıv hierarchia: minden rendsz´amhoz defini´alunk egy halmazt. V0 = ∅, Vα+1 = P(Vα ) ´es Vα = β<α Vβ , ha α limeszrendsz´am. A J´olfund´alts´agi axi´oma ekvivalens azzal, hogy minden halmaz benne van a kumulat´ıv hierarchi´aban, vagyis minden x-hez van olyan α rendsz´am, hogy x ∈ Vα . M´ ask´epp sz´ olva, minden halmaz f¨ol´ep´ıthet˝o az u ¨res halmazb´ol.
3.
Forszol´ as: hozz´ aval´ ok
(M, ∈) megsz´ aml´ alhat´ o tranzit´ıv epszilon-modellje ZFC-nek. Azaz: • (M, ∈) ZFC-modell : M egy halmaz, ∈ egy 2-v´altoz´os rel´aci´o M -en, amely teljes´ıti a ZFC axi´om´ akat (szok´ asos jel¨ ol´es: (M, ∈) |= ZFC). Szeml´eletesen (M, ∈) egy olyan gr´af, amelyre teljes¨ ulnek a ZFC formul´ akban megfogalmazott gr´aftulajdons´agok. (G¨odel teljess´egi t´etele szerint ilyen l´etezik, ha ZFC ellentmond´asmentes.) • |M | = ℵ0 . (Megsz´ aml´ alhat´ o modell a lesz´all´o L¨owenheim-Skolem t´etel miatt van.) • (M, ∈) epszilon-modell : ∈ az ”eleme” rel´aci´o M elemei k¨oz¨ott. • (M, ∈) tranzit´ıv : ha x ∈ M ´es y ∈ x, akkor y ∈ M . (Az utols´o k´et feltev´es jogoss´ag´at nehezebb garant´ alni.) A feltev´esekb˝ ol k¨ ovetkezik p´eld´ aul, hogy M minden eleme megsz´aml´alhat´o halmaz. K´ enyszerk´ epzet: egy (P, ≤) ∈ M r´eszbenrendezett halmaz, amelynek van legnagyobb eleme (ezt 1-gyel jel¨ olj¨ uk), ´es nincs minim´ alis eleme. Praktikus elnevez´esek: (p, q ∈ P ) p ≤ q: p kiterjeszti q-t. p ´es q kompatibilisek, ha van k¨ oz¨ os kiterjeszt´es¨ uk, ´es inkompatibilisek, ha nincs. P el´ agaz´ o, ha minden elemnek vannak inkompatibilis kiterjeszt´esei. S ⊂ P s˝ ur˝ u halmaz, ha minden p ∈ P -hez van olyan q ∈ S, hogy q ≤ p. G ⊂ P generikus filter, ha • G f¨ olsz´ all´ o : ha p ∈ G ´es p ≤ q, akkor q ∈ G. • G kompatibilis: ha p ∈ G ´es q ∈ G, akkor van r ∈ G, hogy r ≤ p ´es r ≤ q 4
• G generikus: minden M -beli s˝ ur˝ u halmazba belemetsz, vagyis, ha S ∈ M , S ⊂ P s˝ ur˝ u, akkor S ∩ G 6= ∅. Generikus filter mindig l´etezik: M -ben csak megsz´aml´alhat´o sok s˝ ur˝ u r´eszhalmaza van P -nek, ezek S0 , S1 , S2 , . . .. V´ alasszunk ki ezekb˝ol sorban pi ∈ Si elemeket u ´gy, hogy pi ≤ pj , ha i ≥ j. Ezt a halmazok s˝ ur˝ us´ege miatt megtehetj¨ uk. K¨onny˝ u ellen˝orizni, hogy {q ∈ P | ∃i q ≥ pi } ⊂ P generikus filter. Azonban, ha P el´ agaz´ o, akkor nincs M -beli generikus filter. Tegy¨ uk fel indirekt, hogy van: G ∈ M , G ⊂ P generikus filter. Minden p ∈ P elemnek vannak inkompatibilis kiterjeszt´esei, v´alasszunk egy ilyen p´art, mondjuk p1 ´es p2 . K¨ oz¨ ul¨ uk legf¨oljebb egy lehet G-ben. Gy´artsuk le a k¨ovetkez˝o halmazt: egy elemet bevesz¨ unk, ha az valamilyen p ∈ P elem kiv´alasztott inkopatibilis kiterjeszt´esei k¨ oz¨ ul a nem G-beli. Ezzel egy M -beli s˝ ur˝ u halmazt kapunk, ami diszjunkt G-t˝ol, ez ellentmond´as. Prec´ızebben: Legyen Np a p ∈ P elem inkompatibilis kiterjeszt´eseinek a halmaza, vagyis {p1 , p2 } ∈ Np , ha S p1 ´es p2 inkompatibilis kiterjeszt´esei p-nek. A Kiv´alaszt´asi axi´oma szerint van f ∈ M , f : P → uggv´eny, hogy f (p) ∈ Np . Ekkor az p∈P Np f¨ S = {q ∈ P | q ∈ / G ´es ∃p ∈ P ´es ∃r ∈ P : {q, r} ∈ f (p)} ⊂ P s˝ ur˝ u halmaz, a defin´ıci´ oja miatt M -beli ´es S ∩ G = ∅. B˝ ov´ıt´ es: Ha van egy (P, ≤) ∈ M el´agaz´o k´enyszerk´epzet, abban egy G ⊂ P generikus filter, ezzel b˝ov´ıthetj¨ uk a modellt: M [G]. • τ ∈ M n´ev, ha τ minden eleme (σ, p) alak´ u, ahol σ ∈ M n´ev ´es p ∈ P . • τ G = {σ G | ∃p ∈ G : (σ, p) ∈ τ } a τ ´altal a G szerint elnevezett halmaz. (Ezek a defin´ıci´ ok kumulat´ıv hierarchia szerinti transzfinit rekurzi´oval ´ertelmesek.) • M [G] = {τ G | τ ∈ M n´ev}. M [G] val´ oban egy b˝ ovebb halmaz ´es tartalmazza G-t: • M ⊂ M [G], mert ha x ∈ M , az x ˆ = {(ˆ y , 1) | y ∈ x} az x egy neve (vagyis x ˆG = x). • G ∈ M [G], mert G˙ = {(ˆ p, p) | p ∈ P } a G egy neve. M [G] egy u ´j megsz´ aml´ alhat´ o tranzit´ıv epszilon-modell, az egyetlen nem trivi´alis dolog, hogy M [G]-ben val´ oban teljes¨ ulnek a ZFC axi´om´ak. Persze n´eh´any axi´oma teljes¨ ul´ese nyilv´anval´o, p´eld´ aul ´ van, amit k¨onny˝ a Meghat´arozotts´ ag ´es a V´egtelens´egi axi´oma automatikusan teljes¨ ul. Es u igazolni, p´eld´aul a P´ ar axi´ om´ at: ha x, y ∈ M [G] az azt jelenti, hogy vannak σ, τ ∈ M nevek, hogy σ G = x ´es τ G = y. Az {x, y} halmaz egy neve {(σ, 1), (τ, 1)} ∈ M , ez´ert {x, y} ∈ M [G]. A t¨obbi axi´ om´ at a ”forszolja” rel´ aci´ o seg´ıts´eg´evel lehet bizony´ıtani (de erre itt nem fog sor ker¨ ulni). Legyen φ egy k v´ altoz´ os halmazelm´eleti formula. Azt mondjuk, hogy a p ∈ P elem forszolja a φ formul´at a τ1 , . . . , τk nevekkel, ha p ∈ G eset´en az M [G] modellben igaz φ(τ1G , . . . , τkG ). Jel¨ol´ese: p φ(τ1 , . . . , τk ). A legfontosabb tulajdons´ agok: • M [G] |= φ(τ1G , . . . , τkG ) pontosan akkor, ha van p ∈ G, hogy p φ(τ1 , . . . , τk ). Vagyis, ha M [G]-ben igaz egy formula, akkor van olyan eleme G-nek, ami ezt forszolja. • Az, hogy ”p φ(τ1 , . . . , τk )”, M -ben defini´alhat´o. Ez prec´ızen azt jelenti, hogy minden φ kv´altoz´ os halmazelm´eleti formul´ ahoz van egy Φ (k + 2)-v´altoz´os halmazelm´eleti formula, hogy Φ(P, p, τ1 , . . . , τk ) pontosan akkor igaz M -ben, ha p φ(τ1 , . . . , τk ). • Ha p φ(τ1 , . . . , τk ) ´es q < p, akkor q φ(τ1 , . . . , τk ). 5
• Ha p φ ∨ ψ, akkor van q < p, hogy q φ vagy q ψ. A m´asodik tulajdons´ ag voltak´epp a forszol´as f˝ot´etele. A bizony´ıt´asa magasan meghaladja e cikk kereteit ´es hivat´ as´ at. Az els˝ o ´es a negyedik tulajdons´ag a m´asodik bizony´ıt´asa sor´an kij¨on, a harmadik pedig k¨ozvetlen¨ ul ad´ odik a defin´ıci´ ob´ ol, hiszen, ha q eleme egy generikus filternek, akkor - a generikus filter felsz´all´ os´ aga miatt - a n´ ala nagyobb p is. Az els˝o k´et ´ all´ıt´ ast u ´gy lehet ¨ osszefoglalni, hogy a forszol´as seg´ıts´eg´evel M -b˝ol ir´any´ıthat´ o, hogy mik lesznek az igaz ´ all´ıt´ asok M [G]-ben.
4.
Rendsz´ amok ´ es sz´ amoss´ agok
Rendsz´ amok: A term´eszetes sz´ amok Neumann-f´ele modellje szerint 0 = ∅, n + 1 = n ∪ {n}. Ennek az ´altal´anos´ıt´ as´ aval kapjuk a rendsz´ amokat: α = {β | β ≤ α}. (Ez az ¨osszef¨ ugg´es defin´ıci´onak nem alkalmas!) Rendsz´amok p´eld´ aul: a term´eszetes sz´amok, a term´eszetes sz´amok halmaza: ω = {0, 1, 2, 3, . . .}, ω + 1 = ω ∪ {ω} = {0, 1, 2, 3, . . . , ω}, ω · 2 = {0, 1, 2, 3, . . . , ω, ω + 1, ω + 2, ω + 3, . . .}, ω 2 = ω · ω = {0, 1, 2, 3, . . . , ω, ω + 1, ω + 2, ω + 3, . . . , ω · 2, ω · 2 + 1, ω · 2 + 2, ω · 2 + 3, . . . , . . .}. K´et fontos tulajdons´ aguk: • A rendsz´ amok nem alkotnak halmazt. Oszt´ alyt alkotnak. • ”Minimalit´ as”: tetsz˝ oleges tulajdons´ag´ u rendsz´amok k¨oz¨ott van legkisebb. Az rendsz´ amok igazi defin´ıci´ oja: 1. Egy (H, <) rendezett halmaz j´ olrendezett, ha minden K ⊂ H r´eszhalmaznak van legkisebb eleme. Ez ekvivalens azzal, hogy nincsen H elemeib˝ol ´all´o h0 > h1 > h2 > . . . v´egtelen cs¨okken˝ o l´ anc. 2. α rendsz´ am, ha (α, ∈) j´ olrendezett ´es tranzit´ıv (γ ∈ β ∈ α → γ ∈ α). 3. Be lehet l´ atni, hogy minden (H, <) j´olrendezett halmazhoz egy´ertelm˝ uen l´etezik olyan α rendsz´ am, ´ hogy (α, ∈) ´es (H, <) izomorfak (vagyis van k¨ozt¨ uk rendez´estart´o bijekci´o). Igy egy rendsz´ am ”izomorf j´ olrendezett halmazok k¨oz¨os tulajdons´aga”. Term´eszetesen teljes¨ ul, hogy α = {β | β < α}. Sz´ amoss´ agok: A v´eges sz´ amoss´ agok a term´eszetes sz´amok. A megsz´aml´alhat´oan v´egtelen azonos´ıthat´o ω-van: ℵ0 = ω. A j´ olrendez´esi t´etel szerint minden halmaz j´olrendezhet˝o, teh´at van nemmegsz´aml´alhat´ o rendsz´ am, ´ıgy a minimalit´as miatt van legkisebb nem-megsz´aml´alhat´o rendsz´ am, ez a k¨ovetkez˝o sz´ amoss´ ag: ℵ1 = ω1 = {α | α rendsz´am ´es |α| = ℵ0 }. Ugyan´ıgy k´epezhet˝ ok az ℵ1 = ω1 , ℵ2 = ω2 , . . . , ℵω = ωω stb. sz´amoss´agok (´es rendsz´amok, amivel azonos´ıtjuk ˝ oket). ´ Altal´ aban a κ rendsz´ am sz´ amoss´ ag, ha κ nagyobb sz´amoss´ag´ u az ¨osszes n´ala kisebb rendsz´ amn´ al. Vagyis ha α < κ eset´en nincsen κ → α injekci´o (nincs α → κ sz¨ urjekci´o). Egy H halmaz sz´ amoss´ aga az a legkisebb κ rendsz´am, amelyhez van a H-nak olyan j´olrendez´ese, amelynek a rendsz´ ama ´eppen κ. Vagyis H lehets´eges j´olrendez´eseinek a rendsz´amai k¨oz¨ ul a legkisebb. A j´olrendez´esi t´etel ´es a rendsz´ amok minimalit´asi tulajdons´aga miatt ez ´ertelmes defin´ıci´o, ´es k¨ onny˝ u meggondolni, hogy ez a κ rendsz´ am val´oban sz´amoss´ag. Ez ¨osszhangban van a Cantor-f´ele ”na´ıv” defin´ıci´oval: ha a H ´es K halmazok egyenl˝ o sz´ amoss´ ag´ uak (ami nem jelent t¨obbet, mint hogy van H → K bijekci´ o), akkor H sz´ amoss´ aga egyenl˝o K sz´amoss´ag´aval. (Vigy´azat, ez nem tautol´ogia!) Rendsz´ amok ´ es sz´ amoss´ agok M -ben: M minden eleme megsz´aml´alhat´o halmaz, ´ıgy a rendsz´ amok is. A rendsz´ amok defin´ıci´ oja ´es a modellre tett f¨oltev´esek miatt viszont az M -beli rendsz´ amok a rendsz´amok egy kezd˝ oszelet´et alkotj´ ak, vagyis {M -beli rendsz´amok} = {β | β rendsz´am ´es β < α0 } 6
valamilyen α0 megsz´ aml´ alhat´ o rendsz´ ammal. Az M -beli rendsz´amok k¨oz¨ ul azok a sz´amoss´agok, amiknek nincs injekci´ oja M -ben n´ aluk kisebb rendsz´amba: A κ < α rendsz´ am sz´ amoss´ ag M -ben, ha β < κ ´es f : κ → β injekci´o eset´en f ∈ / M . A term´eszetes sz´amok ´es ω ugyanazok M -ben, mint a val´os´agban, viszont ω1 m´ar biztos, hogy nem az, hiszen a val´odi ω1 benne sincs M -ben. Bel´athat´ o, M [G]-ben ugyanazok a rendsz´amok, mint M -ben, vagyis a b˝ov´ıt´es sor´an u ´j rendsz´ am nem ker¨ ul be a modellbe. A sz´ amoss´ agok viszont v´altozhatnak, hiszen egy κ ∈ M sz´amoss´ag megsz˝ unik sz´amoss´ag lenni (”meghal”), ha a b˝ ov´ıt´es sor´an beker¨ ul a modellbe egy f : κ → β injekci´o valamilyen ´ β < κ rendsz´ amba. Uj sz´ amoss´ ag viszont nem keletkezhet: ha egy β rendsz´am nem sz´amoss´ag M -ben, akkor az ezt mutat´ o β → γ injekci´ o M [G]-ben is mutatja, hogy β nem sz´amoss´ag.
5.
A kontinuumhipot´ ezis ´ es a tagad´ asa
A kontinuum sz´ amoss´ agra u ´gy gondolhatunk, mint a term´eszetes sz´amok hatv´anyhalmaz´anak a sz´ amoss´ ag´ ara: c = |P(ω)| = |{x | x ⊂ ω}|. Term´eszetesen c > ℵ0 , vagyis c ≥ ℵ1 . A kontinuumhipot´ezis (a tov´abbiakban: KH) szerint nincs olyan sz´amoss´ag, ami nagyobb, mint a megsz´aml´alhat´oan v´egtelen, ´es kisebb, mint a kontinuum. Vagyis c az ℵ0 ut´an k¨ovetkez˝o sz´amoss´ag: c = ℵ1 . Be szeretn´enk bizony´ıtani, hogy a KH nem bizony´ıthat´o ´es nem is c´afolhat´o a ZFC axi´omarendszerben. G¨odel teljess´egi t´etele alapj´ an ezt u ´gy tehetj¨ uk meg, ha keres¨ unk egy olyan ZFC-modellt, amelyben teljes¨ ul a KH, ´es egy olyat is, amelyben nem teljes¨ ul. Ezeket a modelleket egy tetsz˝oleges M megsz´aml´alhat´ o tranzit´ıv epszilon-modellb˝ol kiindulva gy´artjuk le forszol´assal. Tegy¨ uk fel, hogy M -ben nem teljes¨ ul a KH, vagyis M -ben c > ℵ1 . Szeretn´enk egy b˝ ovebb modellt u ´gy, hogy abban m´ ar teljes¨ ulj¨ on, mit kell tenn¨ unk? Tudjuk, hogy az M -beli c ´es az M -beli ℵ1 val´oj´aban megsz´ aml´ alhat´ o rendsz´ amok, ez´ert van k¨oz¨ott¨ uk egy bijekci´o (ami persze nincs M -ben). Teh´at azt kellene el´ern¨ unk, hogy egy ilyen bijekci´o beker¨ ulj¨on a b˝ovebb modellbe, ezzel a kontinuumot leomlasztjuk ℵ1 -re. Most tegy¨ uk fel, hogy M -ben teljes¨ ul a KH, vagyis M -ben c = ℵ1 . Mit kellene tenn¨ unk, hogy a b˝ovebb modellben a kontinuum nagyobb legyen? Az M -beli c az M -beli P(ω) sz´amoss´ aga. Az M -beli P(ω) pedig ω M -beli r´eszhalmazainak a halmaza. Semmik´eppen sem tartalmazhatja ω ¨ osszes r´eszhalmaz´at, hiszen - mint minden M -beli halmaz - val´oj´aban megsz´aml´alhat´o. Ez´ert az a terv, hogy az u ´j modellbe bevessz¨ uk ω-nak j´ o sok nem M -beli r´eszhalmaz´at, ezzel a kontinuumot f¨ olduzzasztjuk.
5.1.
A KH forszol´ asa
Megadjuk, hogy mi legyen a k´enyszerk´epzet: P = {p : ω1 → c megsz´aml´alhat´o tart´oj´ u parci´alis f¨ uggv´enyek} = = {p | p f¨ uggv´eny, Dp ⊂ ω1 , |Dp | ≤ ℵ0 , Rp ⊂ c} . Itt ω1 ´es c a megfelel˝ o M -beli halmazokat jel¨olik, ´es a defin´ıci´o is az M modellben ´ertend˝ o. Meg kell adni a rendez´est is: p ≤ q, ha p, mint f¨ uggv´eny, kiterjeszti q-t (vagyis Dq ⊂ Dp ´es p|Dq = q). ´ k´enyszerk´epzet, vagyis ≤ r´eszbenrendez´es, Az ´ıgy defini´ alt (P, ≤) eleme M -nek a konstrukci´o miatt. Es nincs minim´ alis elem (hiszen tetsz˝ oleges p megsz´aml´alhat´o tart´oj´ u f¨ uggv´enyt ki tudunk terjeszteni egy β ∈ ω1 − Dp elemre), ´es van legnagyobb elem: ∅ ∈ P , az u ¨resf¨ uggv´eny. S˝ot, minden elemnek vannak inkompatibilis kiterjeszt´esei is, vagyis (P, ≤) el´agaz´o. Vizsg´ aluk meg, mit jelent, hogy k´et elem, p ´es q kompatibilisek (azaz van k¨oz¨os kiterjeszt´es¨ uk)! A kiterjeszt´es egy Dp ∪ Dq -n´ al b˝ ovebb halmazon ´ertelmezett f¨ uggv´eny, amely Dp -re megszor´ıtva megyegyezik p-vel, Dq -ra megszor´ıtva pedig q-val. Ilyennek a l´etez´ese ekvivalens azzal, hogy p|Dp ∩Dq = q|Dp ∩Dq , vagy m´ask´eppen azzal, hogy p ∪ q is f¨ uggv´eny.
7
Vegy¨ unk egy G ⊂ P generikus filtert, ´es gy´artsuk le az M [G] b˝ovebb modellt. Legyen F = M [G] a generikus filter elemeinek az uni´oja.
S
G∈
´ ıt´ All´ as: F : ω1 → c sz¨ urjekci´ o. Bizony´ıt´ as: 1. F f¨ uggv´eny, hiszen G elemei kompatibilisek (mivel G filter), ´ıgy az uni´ojuk f¨ uggv´eny. 2. DF = ω1 . Ennek a bizony´ıt´ as´ ahoz bel´atjuk, hogy minden α ∈ ω1 rendsz´amra az Sα = {q ∈ P | α ∈ Dq } ∈ M halmaz s˝ ur˝ u P -ben. Vagyis minden p ∈ P f¨ uggv´enynek vagy olyan kiterjeszt´ese, aminek az ´ertelmez´esi tartom´ any´ aban benne van α. ´Igy m´ar nyilv´anval´o: vagy p maga ´ertelmezve van α-ban, vagy, ha nincs, kiterjeszthetj¨ uk α-ra tetsz˝oleges c-beli ´ert´ekkel (´es term´eszetesen a tart´oja megsz´ aml´ alhat´ o marad). Mivel G generikus, minden M -beli s˝ ur˝ u halmazba belemetsz, speci´alisan az Sα halmazokba is, ´ıgy az uni´o minden α ∈ ω1 rendsz´amon ´ertelmezett. 3. RF = c. Ugyan´ ugy, mint az el˝ obb: minden β ∈ c rendsz´amra defini´alhatjuk a Zβ = {q ∈ P | β ∈ Rq } ∈ M halmazokat, ezek s˝ ur˝ uek P -ben (hiszen tetsz˝oleges p ∈ P -t kiterjeszthet¨ unk egy α ∈ ω1 − Dp rendsz´ amra u ´gy, hogy az α-ban f¨ olvett ´ert´eke β legyen), ´ıgy G mindegyik Zβ -ba belemetsz, ez´ert az uni´ o ´ert´ekk´eszlete az eg´esz c. M [G]-ben teh´ at van egy sz¨ urjekt´ıv lek´epez´es¨ unk ω1 -r˝ol c-re, ami azt jelenti, hogy M [G]-ben c ≤ ω1 . Ez a k¨ovetkeztet´es (valamilyen ´ertelemben) helyes is, de ezzel nem vagyunk k´esz! Ugyanis c ´es ω1 az M -beli c illetve az M -beli ω1 : c az M -beli P(ω) M -beli sz´amoss´aga, ω1 pedig a legkisebb olyan rendsz´am, aminek M -ben nincsen bijekci´oja ω-ra. ”c ≤ ω1 ” teh´at mind¨ossze azt fejezi ki, hogy az M -beli c szerep´et j´ atsz´ o rendsz´ am M [G]-beli sz´amoss´aga legfeljebb akkora, mint az M -beli ω1 szerep´et j´atsz´o rendsz´ am M [G]-beli sz´ amoss´ aga! Hogy viszonyulna ezek az M [G]-beli c-hez ´es ω1 -hez? (M [G])
• ω1
(M )
≥ ω1
(M )
. Nagyobb u ´gy tud lenni, ha a b˝ov´ıt´es sor´an beker¨ ul egy ω1
→ ω bijekci´ o.
• P (M [G]) (ω) ⊃ P (M ) (ω). Szigor´ uan b˝ovebb u ´gy tud lenni, ha a b˝ov´ıt´es sor´an beker¨ ulnek ω-nak u ´j r´eszhalmazai. • Ha P (M [G]) (ω) = P (M ) (ω), akkor c(M [G]) ≤ c(M ) . Hiszen c(M ) az a legkisebb κ rendsz´am, amihez van M -beli f : P (M ) (ω) → κ bijekci´o. Ez az f M [G]-ben is ott van, teh´at |P (M [G]) (ω)| ≤ κ. Teh´at el´eg bel´ atnunk, hogy a b˝ ov´ıt´es sor´an nem ker¨ ulnek be a modellbe ω-nak u ´j r´eszhalmazai. Ekkor ugyanis (M [G]) (M ) (M [G]) ω1 ≤ c(M [G]) ≤ c(M ) ≤ ω1 ≤ ω1 , vagyis mindenhol egyenl˝ os´eg ´ all, ´es az els˝o egyenl˝os´eg szerint M [G]-ben teljes¨ ul a KH. ´ ıt´ All´ as: Ha A ∈ M [G], A ⊂ ω, akkor A ∈ M . Bizony´ıt´ as: A ∈ M [G] azt jelenti, hogy van olyan τ ∈ M n´ev, hogy τ G = A. M [G] |= (A ⊂ ω), ez´ert van p ∈ G, hogy p (τ ⊂ ω ˆ ). (L´ asd a ”b˝ov´ıt´es” ´es a ”forszolja” hozz´aval´ok defin´ıci´oit). Bel´ atjuk, hogy az ˆ = τ )} S = {q ∈ P | ∃X ∈ M : q (X halmaz M -beli ´es – ha nem is s˝ ur˝ u, de – s˝ ur˝ u p alatt, ami azt jelenti, hogy minden q ≤ p-hez van 0 r ≤ q, hogy r ∈ S. Ekkor az S = S ∪ {q ∈ P | p ´es q inkompatibilisek} halmaz k¨onnyen l´athat´ oan s˝ ur˝ u, ez´ert G belemetsz. De akkor G az S-be metsz bele, mert nem tartalmazhat p-vel inkompatibilis ˆ = τ ), akkor M [G]-ben A = τ G = X, ez´ert A ∈ M , teh´at k´eszen elemet. Ha pedig q ∈ S ∩ G, q (X lesz¨ unk. 8
S ∈ M az´ert igaz, mert S a P M -beli halmaz ” ” seg´ıts´eg´evel defini´alt r´eszhalmaza, ´es ” ” M -ben defini´ alhat´ o. (Jegyezz¨ uk meg, hogy S defin´ıci´oj´aban ”∃X ∈ M ” helyett ´ırhaunk egyszer˝ uen ”∃X”-et, hiszen M -beli defin´ıci´ o eset´en a kvantor automatikusan M elemein fut.) A s˝ ur˝ us´eghez legyen q ≤ p, tal´ alnunk kell egy megfelel˝o r-et. q [(ˆ0 ∈ τ ) ∨ (ˆ0 ∈ / τ )], hiszen (0 ∈ A) ∨ (0 ∈ / A) minden modellben igaz. A ”forszolja” tulajdons´agai szerint ekkor van q0 ≤ q, hogy q0 (ˆ0 ∈ τ ) vagy q0 (ˆ 0∈ / τ ). Persze q0 [(ˆ1 ∈ τ ) ∨ (ˆ1 ∈ / τ )], ez´ert van q1 ≤ q0 , hogy q1 (ˆ 1 ∈ τ) ´ ˆ vagy q1 (1 ∈ / τ ). Igy indukci´ oval legy´arthatjuk a q ≥ q0 ≥ q1 ≥ q2 . . . elemeit P -nek u ´gy, hogy minden n ∈ ω-ra qn (ˆ n ∈ τ ) vagy qn (ˆ n∈ / τ ). Maga a (qn ) sorozat M -beli, hiszen a defin´ oj´ aban S ıci´ felhaszn´alt ¨osszes fogalom M -beli (vagyis a sorozatot M -ben defini´altuk). Legyen r = n∈ω qn , ´es legyen X = {n ∈ ω | r (ˆ n ∈ τ )} . Bel´atjuk, hogy ez j´ o lesz. X ∈ M a defin´ıci´oja miatt. r ≤ qn teljes¨ ul minden n-re. Ez´ert minden n-re r (ˆ n ∈ τ ) vagy r (ˆ n ∈ / τ ), ´es r (τ ⊂ ω ˆ ), mert r ≤ p. Teh´at ha r beker¨ ul egy G0 ⊂ P 0 0 G ˆ generikus filterbe, akkor az M [G ]-ben τ -nek ugyanazok az elemei, mint X-nek, vagyis r (τ = X). ´Igy r ∈ S, ´es ezzel k´eszen vagyunk. Megjegyz´es: Ez a bizony´ıt´ as egy ´altal´anosabb koncepci´o r´esze. Egy k´enyszerk´epzet κ-teljes, ha minden legfeljebb κ sz´ amoss´ ag´ u l´ancnak van als´o korl´atja. A KH forszol´asa sor´an haszn´ alt k´enyszerk´epzet ω-teljes, ez´ert tudtuk bebizony´ıtani, hogy ω-nak nem keletkeznek u ´j r´eszhalmazai. Teljesen anal´ og m´ odon bel´ athat´ o, hogy ha egy k´enyszerk´epzet κ-teljes, akkor a b˝ov´ıt´es sor´ an nem + ker¨ ulnek be a modellbe κ-nak u ´j r´eszhalmazai. Tov´abb´a minden κ -n´al nem nagyobb sz´ amoss´ ag sz´amoss´ag marad az u ´j modellben.
5.2.
A KH tagad´ as´ anak a forszol´ asa
Legyen a k´enyszerk´epzet P = {p : ω2 × ω → {0, 1} v´eges tart´oj´ u parci´alis f¨ uggv´enyek} = = {p | p f¨ uggv´eny, Dp ⊂ ω2 × ω, |Dp | < ℵ0 , Rp ⊂ {0, 1}} , a rendez´es pedig: p ≤ q, ha p, mint f¨ uggv´eny kiterjeszti q-t (p ⊃ q). Ezzel egy (P, ≤) ∈ M k´enyszerk´epzetet defini´altunk, ugyan´ ugy, mint a KH forszol´as´an´al. S Legyen G ⊂ P egy generikus filter, M [G] a b˝ovebb modell ´es F = G ∈ M [G] a generikus filter elemeinek az uni´ oja. ´ ıt´ All´ as: F : ω2 × ω → {0, 1} f¨ uggv´eny, ´es minden α ∈ ω2 rendsz´amhoz az α-adik sorhoz tartoz´ o Fα : ω → {0, 1}, Fα (n) = F (α, n) f¨ uggv´enyek k¨ ul¨onb¨oz˝ok egym´ast´ol. Bizony´ıt´ as: 1. F f¨ uggv´eny, hiszen G elemei kompatibilisek. 2. DF = ω2 × ω, hiszen minden (α, n) ∈ ω2 × ω p´arra az S(α,n) = {q ∈ P | (α, n) ∈ Dq } ∈ M halmaz s˝ ur˝ u P -ben, ugyan´ ugy, mint a KH forszol´as´an´al. 3. B´armely k´et α, β ∈ ω2 rendsz´ amhoz van olyan n ∈ ω, hogy F (α, n) 6= F (β, n). Ennek az igazol´as´ ahoz el´eg megmutatnunk, hogy minden α, β ∈ ω2 eset´en a Zα,β = {q ∈ P | ∃n ∈ ω : F (α, n) 6= F (β, n)} M -beli halmaz s˝ ur˝ u P -ben. Ez pedig igaz: tetsz˝oleges p ∈ P -hez van olyan n ∈ ω, hogy p nincsen ´ertelmezve (α, n)-ben ´es (β, n)-ben (mert p v´eges tart´oj´ u). Terjessz¨ uk ki p-t ezekre a pontokra, egyik helyre 0-t, m´ asikra 1-et adva f¨ uggv´eny´ert´eknek. A kiterjesztett f¨ uggv´eny eleme Zα,β -nak. 9
F sorai (az Fα f¨ uggv´enyek) elk´ odolj´ak ω egy-egy r´eszhalmaz´at: Aα = {n ∈ ω | F (α, n) = 1}. Mivel az Fα f¨ uggv´enyek k¨ ul¨ onb¨ oz˝ oek, az Aα r´eszhalmazok is k¨ ul¨onb¨oz˝oek. M [G]-ben teh´at van legal´ abb ω2 darab k¨ ul¨onb¨ oz˝ o r´eszhalmaza ω-nak, teh´at M [G]-ben (l´atsz´olag!) teljes¨ ul a KH tagad´asa. Az egyetlen baj az, hogy az M -beli ω2 szerep´et j´ atsz´o rendsz´am lehet, hogy M [G]-ben nem is sz´amoss´ag, vagy, ha (M ) sz´amoss´ag, nem az ω2 -nek felel meg (pl. ha M [G]-be beker¨ ul egy ω1 → ω bijekci´o, akkor az M -beli ω2 az ω1 sz´amoss´ ag szerep´et fogja j´ atszani M [G]-ben). Ezeket a lehet˝os´egeket kiz´arja az al´abbi ´ all´ıt´ as (´es ´ıgy M [G]-ben val´ oban teljes¨ ul a KH tagad´asa). ´ ıt´ All´ as: A sz´ amoss´ agok ´eletben maradnak, vagyis M [G]-ben ugyanazok a sz´amoss´agok, mint M -ben. Bizony´ıt´ as: Bel´ atjuk, hogy ω1 ´eletben marad, vagyis nem keletkezik ω → ω1 sz¨ urjekci´o. Ennek a mint´aj´ara bel´ athat´ o, hogy nem keletkezik ω1 → ω2 sz¨ urjekci´o sem, ´es ´ıgy ω2 is ´eletben marad. Nek¨ unk ennyi el´eg is lenne, de nagyobb sz´ amoss´agokra is teljesen anal´og m´odon m˝ uk¨odik a bizony´ıt´as. Tegy¨ uk fel, hogy h ∈ M [G], h : ω → ω1 f¨ uggv´eny. Megmutatjuk, hogy nem lehet sz¨ urjekt´ıv: h ´ert´ekk´eszlet´et fel¨ ulr˝ ol becs¨ ulj¨ uk egy H ∈ M halmazzal, majd megmutatjuk, hogy H sz´amoss´ aga M -ben mind¨ ossze megsz´ aml´ alhat´ o. h-nak van neve: τ ∈ M , τ G = h, ´es van p ∈ G, hogy p (τ : ω ˆ → ωˆ1 f¨ uggv´eny). Defini´ aljuk minden n ∈ ω-ra a Hn halmazokat: Hn = {α ∈ ω1 | ∃q ∈ P : q ≤ p, q (τ (ˆ n) = α ˆ )} . Hn ∈ M a defin´ıci´ oja miatt, ´es Hn a potenci´alis h(n)-´ert´ekek halmaza, vagyis h(n) ∈ Hn teljes¨ ul minden n ∈ ω-ra (hiszen S ha h(n) = α, akkor van q ∈ G, ami ezt forszolja, ´es v´alaszthatunk ilyen q-t p alatt is). Ez´ert, a H = n∈ω Hn jel¨ ol´essel h ´ert´ekk´eszlete r´esze H-nak. Ha α ´es β k´et k¨ ul¨ onb¨ oz˝ o eleme Hn -nek, akkor hozz´ajuk tartoz´o P -beli qα illetve qβ elemek ˆ ´es mindketten forszolj´ak, hogy inkompatibilisek. Hiszen qα (τ (ˆ n) = α ˆ ) ´es qβ (τ (ˆ n) = β), (τ : ω ˆ → ωˆ1 f¨ uggv´eny), mivel kisebbek p-n´el. Ha lenne k¨oz¨os kiterjeszt´ese qα -nak ´es qβ -nak, akkor mindezt forszolnia kellene, de ez lehetetlen, hiszen egy f¨ uggv´eny nem vehet f¨ol egy helyen k´et k¨ ul¨ onb¨ oz˝ o ´ert´eket. Bel´atjuk, hogy P tetsz˝ oleges ω1 sz´amoss´ag´ u r´eszhalmaz´aban van k´et elem, amik kompatibilisek. Ehhez – bizony´ıt´ as n´elk¨ ul – f¨ olhaszn´ aljuk a v´egtelen ∆-rendszer lemm´ at: Ha κ > ω regul´ aris sz´ amoss´ ag, akkor minden κ sz´amoss´ag´ u, v´eges halmazokb´ol ´all´o halmazrendszerb˝ ol kiv´ alaszthat´ o κ-sz´amoss´ag´ u ∆-rendszer. (Egy halmazrendszer ∆-rendszer, ha tetsz˝ oleges k´et elem´enek a metszete ugyanaz a D halmaz.) ´ Legyen L ⊂ P , |L| = ω1 . Alljon a K halmaz az L-beli f¨ uggv´enyek ´ertelmez´esi tartom´anyib´ ol: K = ´ {Dr | r ∈ L}. Igy K ⊂ P(ω2 × ω) egy ω1 sz´amoss´ag´ u, v´eges halmazokb´ol ´all´o halmazrendszer ´es ω1 > ω regul´ aris rendsz´ am. Ez´ert a ∆-rendszer lemma szerint van K 0 ⊂ K ω1 sz´amoss´ag´ u ∆-rendszer: 0 tetsz˝oleges Dr , Ds ∈ K -re Dr ∩ Ds = D. De D v´eges halmaz, ez´ert csak v´eges sok D → {0, 1} f¨ uggv´eny van. Ez´ert K 0 elemeihez tartoz´o L-beli f¨ uggv´enyek k¨oz¨ott biztosan van kett˝o, amiknek a D-re vett megszor´ıt´ asa megegyezik, de akkor ez a k´et f¨ uggv´eny kompatibilis. Most rakjuk ¨ ossze: tetsz˝ oleges n-re a Hn minden α elem´ehez v´alaszthatunk egy-egy qα elemet (´ ugy, hogy qα (τ (ˆ n) = α ˆ )), ´es a {qα | α ∈ Hn } ⊂ P halmaz p´aronk´ant inkompatibilis elemekb˝ ol S ´all, teh´at megsz´ aml´ alhat´ o. Emiatt a Hn halmazok is megsz´aml´alhat´oak, ´es H = n∈ω Hn halmaz is, hiszen megsz´ aml´ alhat´ o sok megsz´ aml´ alhat´o halmaz uni´oja. Mivel h ´ert´ekk´eszlete r´esze h-nak, ez´ert ez is megsz´aml´ alhat´ o, teh´ at h nem lehet sz¨ urjekt´ıv. Megjegyz´es: Ha a k´enyszerk´epzet definici´oj´aban ω2 × ω helyett κ × ω-t ´ırunk (ahol κ tetsz˝ oleges sz´amoss´ag), akkor a b˝ ovebb modellben c ≥ κ fog teljes¨ ulni. Teh´at a kontinuum ´ert´eke tetsz˝ olegesen nagy lehet (de nem lehet ak´ armelyik sz´amoss´ag, a K˝ onig-t´etel korl´atozza a lehet˝os´egeket). Megjegyz´es: Ez a bizony´ıt´ as is egy ´ altal´anosabb koncepci´o r´esze. A k´enyszerk´epzet egy r´eszhalmaz´ at antil´ ancnak nevezz¨ uk, ha az elemei p´aronk´ant inkompatibilisek. A k´enyszerk´epzet teljes´ıti a κantil´ ancfelt´etelt, ha nincs benne κ m´eret˝ u antil´anc. (M´ask´eppen: ha a k´enyszerk´epzet b´armely κ 10
sz´amoss´ag´ u r´eszhalmaz´ aban van k´et elem, amik kompatibilisek.) A KH tagad´as´anak a forszol´asa sor´ an haszn´alt k´enyszerk´ezet teh´ at teljes´ıti az ω1 -antil´ancfelt´etelt. Az ilyen k´enyzerk´epzeteket megsz´ aml´ alhat´ o antil´ ancfel´etelesnek (MAF-osnak) h´ıvj´ak, term´eszetesen helytelen¨ ul. Voltak´epp azt bizony´ıtottuk be, hogy ha egy k´enyszerk´epzet MAF-os, akkor a sz´amoss´agok ´eletben maradnak. Teljesen anal´ og m´odon bizony´ıthat´ o, hogy ha egy k´enyszerk´epzet teljes´ıti a κ-antil´ancfelt´etelt, akkor a κ-n´al nagyobb sz´amoss´agok sz´ amoss´ agok maradnak a b˝ovebb modellben (´es ha κ regul´aris, akkor κ is sz´ amoss´ ag marad).
6.
B˝ ovebben:
Halmazelm´elet: • Hajnal-Hamburger: Halmazelm´elet • Halmazelm´elet jegyzet Komj´ ath P´eter honlapj´an valahol: http://www.cs.elte.hu/ kope Matematikai logika: • http://www.cs.elte.hu/ kope/oktatas/09tav/ma2.pdf • Csirmaz L´ aszl´ o k¨ onyve ´es jegyzetei a honlapj´an: http://renyi.hu/ csirmaz/ Forszol´as: • http://www.cs.elte.hu/ kope/oktatas/forsz.dvi • http://renyi.hu/ csirmaz/
11
