Kardinalitet utan Urvalsaxiomet; ett potpourri 1 Petter Remen 28 april 2005 1 Inlämnad som C-uppsats till Filosofiska Instutionen vid Göteborgs Universitet med Christian Bennet som handledare. Sammanfattning Urvalsaxiomet (AC) är numera allmänt accepterat som ett naturligt fun- dament i mängdlära. Här presenterar vi hur kardinalitet och kardinaltal kan definieras utan AC och visar ett antal klassiska resultat om vad som kan ske i modeller till ZF där AC är falsk. Det visar sig då att kardinaltalsaritmetiken, som med urvalsaxiomet är trivial, får en potentiellt sett rik struktur. Speciellt presenteras metoden att falsifiera AC i så kallade permutations- modeller. Med denna metod visas ett relativt nytt resultat av Shelah och Halbeisen som visar att det är konsistent med ZF att det finns en mängd U sådana att mängden av ordnade par med element ur U har strängt mindre kardinalitet än mängden av oordnade par med element ur U . 1 Inledning och notation Innehållet i denna text torde vara tillgänglig för envar som har grundläggande kunskaper om ZFC och den kumulativa hierarkin. Vad gäller notationen låter vi N = ω = ω0 beteckna de naturliga talen; ordnade par betecknas 〈x, y〉; n- tipler (ändliga sekvenser med längden n) skrivs 〈x0, x1, . . . , xn−1〉; delmängd skrivs ⊆ emedan äkta delmängd skrivs ⊂. Om f : X → Y är en funktion och A ⊆ X så låter vi f [A] := { f(x) | x ∈ A } vara bilden av A under f ; om y tillhör värdeförrådet till f så är f−1(y) := {x | f(x) = y } inversa bilden av y under f . Om B är en delmängd till värdeförrådet till f så är f−1[B] := {x | f(x) ∈ B } inversa bilden av B under f . 2 Urvalsaxiomet och kardinaltalsaritmetik 2.1 Historik och några ekvivalenser Betrakta följande argumentation: Antag att vi har en uppräknelig mängd, X, av uppräkneliga mängder. Låt Ai, där i ∈ N, vara en uppräkning av elementen i X. Det är klart att ⋃ X = ⋃ iAi är uppräknelig, ty låt ai,j där j ∈ N vara en uppräkning av elementen i Ai. Varje element i⋃ X motsvaras i så fall av (åtminstone) ett par av naturliga tal 〈i, j〉 och mängden av sådana par är uppräknelig. Argumentationen verkar uppenbart giltig men vilar ändå på ett gömt antagande. Lägg nämligen märke till att det för varje Ai finns en hel uppsjö olika bijektioner f : N → Ai; så för att skapa en entydig funktion ai,j måste vi faktiskt välja en sådan bijektion för varje i ∈ N. Problemet är bara att det inte generellt sett finns någon regel med vilken vi kan välja dessa bijektioner. Hur kan vi säga att en oändlig sekvens av saker existerar, om vi inte kan säga hur den ska konstrueras? Det gömda antagandet är följande: Axiom 1 (Urvalsaxiomet (AC)). För varje mängd X av icketomma mängder finns det en funktion f sådan att x ∈ X ⇒ f(x) ∈ x. f sägs vara en urvalsfunktion. Med detta axiom, det vill säga i ZFC, kan vi bevisa att unionen av en uppräknelig mängd av uppräkneliga mängder är uppräknelig. Bevis. Låt X vara en mängd av uppräkneliga mängder, vilket innebär att det finns en bijektiv funktion A : ω → X, och att det för varje x ∈ X finns en bijektiv funktion a : ω → x. 1 Bilda nu mängden F = { yi | i ∈ ω } där yi är mängden { 〈i, a〉 | a är en bijektiv funktion från ω till A(i) } . F är en mängd av icketomma mängder och alltså finns det enligt urval- saxiomet en funktion f sådan att x ∈ F ⇒ f(x) ∈ x. Värdeförrådet till f , det vill säga { 〈i, a〉 | i ∈ ω ∧ 〈i, a〉 = f(yi) }, genererar naturligt en surjektiv funktion från ω×ω på ⋃ X. Eftersom vi kan ordna ω×ω lexikografiskt finns det en funktion g : ⋃ X → ω × ω som, för varje x ∈ ⋃ X, avbildas på det minsta y ∈ ω×ω sådant att f(y) = x. g kommer då vara bijektiv. Dessutom är bilden av g en oändlig delmängd till ω×ω och därför uppräknelig, varför ⋃ X är uppräknelig. Huruvida man betraktar AC som intuitivt sant eller ej beror mycket på vilken uppfattning man har om när man kan påstå att ett matematiskt objekt existerar. Urvalsaxiomet anger nämligen inte hur urvalsfunktionen fungerar eller är uppbyggd. Det verkar ju föga konstruktivt. . . ? Frågor och problem av den här typen dök upp framför allt under slutet av artonhundratalet, dels i analysen (se [9], kapitel 1.2), där man hade börjat titta noggrannare på godtyckliga sekvenser av reella tal och deras egenskaper, men framför allt i Cantors nyuppfunna mängdlära där en teori för det faktiskt oändliga hade skapats. Cantor använde sig av urvalsaxiomet på ett flertal ställen i sina samlade verk, ofta implicit på liknande sätt som i exemplet ovan, men också på ett rätt förvånande sätt. Cantor ansåg nämligen till en början att det var intuitivt och logiskt självklart att 1. Alla mängder kan välordnas (välordningsprincipen) 2. Givet två godtyckliga mängder a och b så finns det en injektiv funktion f från a till b eller från b till a. (trichotomi) men båda dessa påståenden är ekvivalenta med AC. Ekvivalensen för (1) formulerar vi så här (den andra kommer vi bevisa senare): Faktum 1. ZF ` AC↔ ∀x∃y (y välordnar x)1 Själva formuleringen av AC inom ramen för en axiomatisk framställning av mängdläran kom först med Zermelo i 1908 ([11]) i en till synes svagare form; Om X är en icketom mängd av parvis disjunkta, icketomma mängder så finns det en mängd Y som innehåller precis ett ele- ment ur varje element i X. (Multiplicative axiom) 1 För bevis av detta och dylika obevisade fakta, se [6]. 2 Idén var att detta skulle vara mer intuitivt självklart än den ursprungliga formuleringen i termer av urvalsfunktioner. Han visade dock i samma artikel att de två är ekvivalenta. Det vill säga: Faktum 2. ZF ` AC↔ Multiplicative axiom. Kontroversen kring Zermelos axiomatisering var stor, men diskussionen ebbade ut något efter 1938 ([3]) då Gödel bevisade att om ZF är konsistent så är ZF+AC konsistent. Det är dock fortfarande intressant att studera den relativa styrkan hos AC, kanske speciellt i förhållande till påståenden om kardinaltal. 2.2 Likmäktighet Först och främst definierar vi några välbekanta relationer. Definition 1. 1. Låt a  b omm det finns en injektiv funktion från a till b. a sägs vara inbäddbar i b. 2. Låt a ' b omm det finns en bijektiv funktion från a på b. a och b sägs vara likmäktiga. 3. Låt a ≺ b omm a  b och a 6' b. Vi får omedelbart ur definitionerna att  är en transitiv och reflexiv relation och att ' är en ekvivalensrelation. Dessutom är de två relationerna relaterade till varandra via följande sats: Faktum 3 (Schröder-Bernsteins sats). ZF ` ∀x∀y (x  y∧y  x→ x ' y). Vad som däremot inte följer ur ZF är att  skulle vara total. Faktum 4. ZF ` AC↔ ∀x∀y (x  y ∨ y  x). Bevis. ⇒) Antag att M  ZFC och att a, b ∈ M . Eftersom M  AC så finns välordningar 〈a,= = >=< ‖ >=< ‖ < seq 1-1(m) >= >=< ‖ = =< >=< ‖ seq(m) >= >=< ‖ >= = >=< ‖ 2m > > >=< ‖ >=< ‖ = I [5] visas även att såväl [m]2 < m2 som [m]2 > m2 är möjliga. Vi kommer rekonstruera beviset för detta i avsnitt 3.2.6, men behöver först en uppsättning verktyg. 9 3 Fraenkel-Mostowskimodeller Fraenkel visade 1922 ([2]) att så länge man har med urelement i sin mängd- teori så finns det modeller i vilka AC är falskt. Idén är nämligen den att en modell M med urelement i någon mening inte kan skilja urelementen åt, vilket gör att en permutation av dessa faktiskt bildar en ny modell. Man kan dessutom konstruera M så att det finns uppräkneligt antal urelement, men där varje mängd i M bara beror på (t.ex. definieras via) ett ändligt antal. Då kommer inte mängden av urelement kunna ordnas totalt, ty denna ord- ning skulle i så fall bero på ett ändligt antal urelement u1, . . . , un, vilket är absurt eftersom det är klart att det finns en permutation ( 6= identitetsfunk- tionen) som ändrar ordningen på urelementen men samtidigt inte ändrar på just u1, . . . , un. Vi ska precisera argumentet ovan och även ge en presentation av ett mer generellt tillvägagångssätt som vi sedan ska använda oss av för att bygga modeller i vilka olika förhållanden mellan kardinaliteter gäller. Det kommer även visa sig att alla resultat vi kommer fram till kan överföras till ZF, ett resultat som bygger på Cohens forcingteknik. Idéerna i avsnitt 2.1 och 2.2.1. kommer från [7] och de avsnitt 2.2.2 och framåt kommer från [6]. Vi börjar med att visa att det finns modeller med uppräkneligt många urelement. 3.1 Con(ZF) ⇒ Con(ZFU) Låt V = 〈V,∈〉 vara en modell till ZF . Antag att vi har en formel R(x, y) sådan att V  R(x, y) är en bijektiv funktionell relation. Vi skriver F (a) för det unika objekt b ∈ V som satisfierar R(a, y). Låt nu x ∈′ y betyda att x tillhör bilden av y under F , alltså; x ∈′ y ⇔ x ∈ F (y) ⇔ ∃z(x ∈ z ∧R(y, z)). Om φ är en formel så är φ′ samma formel men med varje förekomst av x ∈ y utbytt mot formeln som uttrycker x ∈′ y. Det intressanta nu är att ∈′ uppför sig väldigt likt ∈. Låt nämligen ZF− vara ZF utan regularitetsaxiomet, då har vi att Sats 1. V ′ = 〈V,∈′〉 är en modell till ZF−. Bevis. Vi bevisar satsen genom att bevisa att om φ ∈ ZF− så gäller V  φ′. EXT Vi visar att ∀x, y(x = y ↔ ∀z(z ∈′ x ↔ z ∈′ y)) är sant i V. Implikationen åt höger är uppenbart sant. Antag därför att ∀z(z ∈′ x ↔ z ∈′ y). Detta är, per definition, ekvivalent med ∀z(z ∈ F (x) ↔ z ∈ F (y)), men då ger EXT i V att F (x) = F (y) men då gäller x = y, ty F är bijektiv. 10 PAR Låt a och b vara två godtyckliga mängder. Låt c = F−1({a, b}). Då har vi att z ∈′ c⇔ z ∈ F (c) ⇔ z = a ∨ z = b. UNION Vi visar att det för ett godtyckligt a finns ett b s.a. x ∈′ b ⇔ ∃z(x ∈′ z ∧ z ∈′ a) ⇔ ∃z(x ∈ F (z) ∧ z ∈ F (a)) ⇔ x ∈ ⋃ y∈F (a) F (y). Låt c = ⋃ y∈F (a) F (y). Denna mängd existerar enligt UNION och SUBST i V. Låt nu b = F−1(a), då gäller x ∈′ b⇔ x ∈ c vilket var vad vi ville. DEL Låt φ′(x) vara en godtycklig formel och a vara en godtycklig mängd. Eftersom φ′(x) är ett uttryck i språket för ZF och F (a) är en mängd så finns det en mängd c = {x | x ∈ F (a) ∧ φ′(x) }. Sätt b = F−1(c) så gäller x ∈′ b↔ x ∈′ a ∧ φ′(x) vilket är det önskade resultatet. POT Vi lägger först och främst märke till att x ⊆′ y ≡ ∀z(z ∈′ x→ z ∈′ y) ⇔ ∀z(z ∈ F (x) → z ∈ F (y)) ⇔ F (x) ⊆ F (y). Låt a vara en godtycklig mängd och låt c = {x | F (x) ⊆ F (a) } = {F−1(y) | y ∈ P(F (a)) }. c är en mängd enligt SUBST, DEL, POT i V och det faktum att F(a) är bijektiv och definieras av en formel i språket för ZF. Låt nu b = F−1(c), då får vi: x ∈′ b ⇔ x ∈ F (b) ⇔ x ∈ c ⇔ F (x) ⊆ F (a) ⇔ x ⊆′ a. VSB SUBST Låt φ(x, y) vara en formel i språket för ZF s.a. φ′(x, y) bildar en funktionell relation. Tag nu en godtycklig mängd a och låt c vara bilden av F (a) under φ′. c är en mängd enligt SUBST i V, så vi låter b = F−1(c). Vi får då att x ∈′ b ⇔ x ∈ c ⇔ ∃z(z ∈ F (a) ∧ φ′(z, x)), och alltså gäller SUBST i V ′. 11 INF Vi definierar induktivt en funktion f : ω → V på följande sätt (vi använder oss återigen av att F är bijektiv): f(∅) = F−1(∅) F (f(n+ 1)) = F (f(n)) ∪ f(n). Låt nu η = f [ω] och låt θ = F−1[η]. Lägg märke till att x ∈′ θ ⇔ x ∈ η. Vi visar att θ innehåller ∅′ och är sluten under Sc′(x). Vi har direkt att ∀x(x 6∈′ F−1(∅)) så ∅′ = F−1(∅). Eftersom ∅′ ∈ η har vi att ∅′ ∈′ θ. Vidare gäller att om a ∈′ θ så a ∈ η, och alltså a = f(n) för något n ∈ ω. Men vi har ju att z ∈′ f(n+ 1) ⇔ z ∈ F (f(n+ 1)) ⇔ z ∈ F (f(n)) ∪ {f(n)} ⇔ z ∈′ f(n) eller z = f(n) ⇔ z ∈′ f(n) ∪′ {f(n)}′ ⇔ z ∈′ Sc′(a), och därför gäller Sc′(a) ∈ η och alltså Sc′(a) ∈′ θ. Tyvärr får vi inte, på detta sätt, nödvändigtvis en modell som negerar AC. Faktum 11. Om urvalsaxiomet är sant i V ovan så är det sant i V ′ också. Vi får däremot möjligheten att skapa modeller med urelement! Definition 7. Ett urelement är en mängd x sådan att x = {x}, det vill säga ∀y (y ∈ x↔ y = x). Sats 2. Det finns en struktur M sådan att M  ZF− + det finns uppräkneligt många urelement. Bevis. Låt V vara en modell till ZF och låt F (x) vara sådant att om n är ett naturligt tal > 0 så gäller F (n) = {n}, F ({n}) = n och annars gäller F (x) = x. Lägg märke till att vi måste kräva att n > 0 eftersom {0} = 1 och F hade i så fall inte varit väldefinierad. Låt nu M = 〈V,∈′〉. Vi har, för varje n > 0 att V  ∀x(x ∈′ n↔ x = n) så varje n kommer att vara ett urelement i M . Vi definierar nu, med induktion i V en funktion f sådan att f(0) = F−1(0) f(n+ 1) = F−1({f(0), . . . , f(n)}). 12 Man får övertyga sig om att bilden av f i själva verket är den mängd som i M tolkas som ω. Om vi låter {a0, . . . , an}′ vara en förkortning för F−1({a0, . . . , an}) så kan vi låta 〈a, b〉′ vara { {a}′, {a, b}′ }′ . Med lite tankekraft räknar man ut att dessa definitioner faktiskt gör det dom ska, det vill säga att 〈a, b〉′, i M , kommer att vara det ordnade paret av a och b. Vi sätter nu g = F−1 ( { 〈n, f(n)〉′ | n ∈ ω } ) . g är då en mängd i V och är, i M, en bijektion mellan urelementen och ω. Lägg märke till att även om modellen M ovan självklart strider mot regularitet så är det egentligen bara urelementen som utgör motexempel. Därför kommer följande variant av regularitet vara sann i M : x 6= ∅ → ∃y ( y ∈ x ∧ (y ∩ x = ∅ ∨ y = {y}) ) . (UREG) Vi låter ZFU vara ZF−+UREG. Från sats 2 vet vi att det finns modeller till ZFU som har uppräkneligt många urelement. Det finns för ZFU en motsvarighet till den klassiska kumulativa hierar- kin, med den enda skillnaden att den lägsta nivån inte utgörs av ∅ utan av mängden av urelement. Det finns sådeles ett relevant rangbegrepp. Definition 8. Den tvåställiga funktionen Pα(x) definieras med transfinit induktion P0(x) = x Pα+1(x) = Pα(x) ∪ P(Pα(x)) Pλ(x) = ⋃ α<λ Pα(x). I modeller M till ZFU är det nu sant ∀x∃α (x ∈ Pα(U)), där U = {x | x ∈ {x} } är mängden av alla urelement. Vi låter rangen för en mängd x i M vara det minsta ordinaltal α sådant att x ∈ Pα(U). Det intressanta med dessa modeller är att varje permutation på urele- menten går att utvidga (på ett naturligt sätt) till en automorfism på hela modellen. Det är just detta faktum som gör att vi kan skapa modeller i vilka AC är falska. 3.2 Permutationsmodeller Definition 9. Låt M  ZFU och låt U vara mängden av urelement i M . Om pi är en permutation på U definierar vi pˆi : M →M som pˆi(x) = { pi(x), när x ∈ U { pˆi(y) | y ∈ x }, när x 6∈ U. 13 Faktum 12. Om M  ZFU och pi är en permutation av urelementen i M så är pˆi en automorfism på M , det vill säga en bijektion som bevarar ∈-relationen. Eftersom det inte kommer innebära några ambiguiteter använder vi oss av notationen pi(x) även för pˆi(x). Vi bygger nu inre modeller tillM i vilka urvalsaxiomet är falskt. Vi börjar med följande betraktelser och överlämnar de enkla bevisen till läsaren: Faktum 13. Om M  ZFU , pi(x) är en permutation på urelementen och φ(a0, . . . , an) är en sats med parametrar a0, . . . , an ∈M så gäller M  φ(a0, . . . , an) ⇔M  φ(pi(a0), . . . , pi(an)). Bevis. Bevisas med induktion över komplexiteten på φ. Faktum 14. Om α är ett ordinaltal så gäller pi(α) = α. Bevis. Inses lätt eller bevisas med transfinit induktion över α. 3.2.1 OAD och HOAD Precis som i fallet med ZF definierar vi, relativt en modell M  ZFU , de ordinaltals- och atomdefinierade mängderna, OAD(M). Definition 10. En mängd a tillhör OAD(M) om och endast om det finns en formel φ(x, α0, . . . , αn, u0, . . . , um) med en fri variabel x, där ordinaltalen α0, . . . , αn och urelementen u0, . . . , um får ingå som parametrar, sådan att M  φ(x, α0, . . . , αn, u0, . . . , um) ↔ x = a. De hereditärt ordinaltals- och atomdefinierade mängderna, HOAD(M), får vi sedan via Definition 11. En mängd a tillhör HOAD(M) omm a och varje element i det transitiva höljet till a finns med OAD(M). Faktum 15. Om M  ZFU så gäller HOAD(M)  ZFU . Bevis. Beviset är det samma som i fallet med ZF fast vi måste försäkra oss om att mängden av urelement finns med i HOAD. Men denna är ju definierbar via formeln ∀y(y ∈ x↔ y = {y}). Men i HOAD(M) är AC falskt! Sats 3. Om M  ZFU så HOAD(M)  ¬AC. 14 Bevis. Vi visar att det inte ens finns någon sträng total ordning av mängden av urelement, vilket motsäger välordningssatsen. Antag därför att v är en sträng total ordning av urelementen. Då finns det en formel φ(x, α0, . . . , αn, u0, . . . , um) sådan att M  ∀x(φ(x, α0, . . . , αn, u0, . . . , um) ↔ x = v). Men välj nu två urelement a och b, skilda från u0, . . . , un, sådana att 〈a, b〉 ∈ v. Låt pi vara en permutation som byter plats på a och b men som för övrigt inte ändrar på några urelement. Enligt faktum 13 så gäller M  ∀x(φ(x, pi(α0), . . . , pi(αn), pi(u0), . . . , pi(u0)) ↔ x = pi(v)) vilket, med vårt val av pi och faktum 14, ger att pi(v) = v. Men vi har också att M  〈a, b〉 ∈ v varför M  pi(〈a, b〉) ∈ pi(v), det vill säga M  〈b, a〉 ∈ v vilket motsäger att v är en sträng ordning. 3.2.2 En generalisering Vi presenterar nu en generaliseringen av föregående resultat, med vars hjälp vi kan konstruera ett flertal olika modeller i vilka vi kan påtvinga olika rela- tioner mellan kardinaliteter. Låt som vanligt M  ZFU och U vara urelementen i M . Låt G vara en grupp av permutationer på U . Definition 12. Symmetrigruppen för en mängd x, symG(x), är mängden av alla permutationer i G som fixerar x. Det vill säga symG(x) := {pi ∈ G | pi(x) = x }. Dessutom låter vi, för varje delmängd S ⊆ U , fixG(S) vara gruppen av alla permutationer som fixerar elementen i S, det vill säga fixG(S) := {pi ∈ G | pi(s) = s för alla s ∈ S } = ⋂ s∈S symG(s). Definition 13. En mängd F av delgrupper till G är ett normalt filter på G om det för alla delgrupper H och K till G gäller att (1) G ∈ F , (2) om H ∈ F och H ⊆ K, så K ∈ F , (3) om H,K ∈ F så H ∩K ∈ F , (4) om pi ∈ G och H ∈ F , så piHpi−1 ∈ F , 15 (5) för varje u ∈ U , {pi ∈ G | pi(u) = u } ∈ F . Definition 14. Låt F vara ett normalt filter på G. En mängd x sägs vara symmetrisk om symmetrigruppen för x tillhör F . Definition 15. En mängd x är hereditärt symmetrisk om x är symmet- risk och varje element i det transitiva höljet av x är symmetriskt. Faktum 16. Låt V = {x ∈ M | x är hereditärt symmetrisk }. Då är V en modell till ZFU . En sådan modell kallas en permutationsmodell. Bevis. Vi visar här att PAR och POT är sanna i V och hänvisar till [6], sidorna 46-47, för resten av beviset. PAR Låt a och b vara två godtyckliga mängder i V, dvs a och b är he- reditärt symmetriska. För att visa att {a, b} ∈ V räcker det alltså att vi- sa att {a, b} är symmetrisk. Det är dock klart att symG(a) ∩ symG(b) ⊆ symG({a, b}) och enligt egenskaperna (2) och (3) hos filtret F så får vi alltså att symG({a, b}) ∈ F , vilket skulle bevisas. POT Låt a vara en mängd och låt b = P(a)∩V. Det är klart att elementen i b är hereditärt symmetriska varför det räcker att visa att b är symmetrisk. Det gäller för alla x att om pi ∈ G så är symG(pi(x)) = pisymG(x)pi −1 och alltså är pi(x) symmetrisk närhelst x är det. Detta innebär att om x är ett element i b så är pi(b) det också. Låt nu pi ∈ symG(a). Då har vi att x ∈ b ⇒ pi−1(x) ∈ b ⇒ x ∈ pi(b), och dessutom att x ∈ pi(b) ⇒ x = pi(y) för ngt y ∈ b ⇒ x = pi(y) ∈ b. Alltså gäller pi(b) = b varför pi ∈ symG(b) och alltså symG(a) ⊆ symG(b) och eftersom F är ett filter så har vi att symG(b) ∈ F vilket skulle bevisas. Vi kommer här endast att använda oss av en speciell sorts filterkonstruk- tion, nämligen filtret som fås via ett normalt ideal på U . Definition 16. Låt G vara en grupp av permutationer på U . En familj I av delmängder till U är ett normalt ideal om det för alla E,F ⊆ U gäller att: 1. ∅ ∈ I, 2. om E ∈ I och F ⊆ E, så gäller F ∈ I, 3. om E,F ∈ I, så gäller E ∪ F ∈ I 16 4. om pi ∈ G och E ∈ I, så gäller pi[E] ∈ I och 5. för varje u ∈ U så gäller u ∈ I. Om F är någon familj av delmängder till U och I är det minsta idealet sådant att F ⊆ I så säger vi att I genereras av F . Faktum 17. Antag att I är ett normalt ideal på U . Låt F vara mängden av alla delgrupper, H, till G sådana att H ⊇ fixG(E) för något E ∈ I. Då är F ett normalt filter på G. Bevis. Vi måste visa att F har alla egenskaperna i definition 13. 1. G ∈ F eftersom G = fixG(∅). 2. Vi har direkt ur definitionen av F att om H ∈ F och K ⊇ H så gäller K ∈ F . 3. F är slutet under snitt, ty antag att H,K ∈ F . Då finns det E,F ∈ I sådana att H ⊇ fixG(E) och K ⊇ fixG(F ). Men H ∩K ⊇ fixG(E) ∩ fixG(F ) = fixG(E ∪ F ) och E ∪ F ∈ I varför H ∩K ∈ F . 4. Antag att pi ∈ G och H ∈ F . Vi vet då att det finns ett E ∈ I sådant att H ⊇ fixG(E). Enligt definitionen av ideal så gäller pi[E] ∈ I. Låt nu pi0 ∈ G vara sådant att pi0 ∈ fixG(pi[E]), det vill säga pi0pi(e) = pi(e) för alla e ∈ E. Vi vill visa att pi0 ∈ piHpi−1 ty då är fixG(pi[E]) ⊆ piHpi−1 och således gäller piHpi−1 ∈ F . Men vi har ju att pi−1pi0pi(e) = e för alla e ∈ E, det vill säga pi−1pi0pi ∈ fixG(E) ⊆ H. Samtidigt har vi att pi(pi−1pi0pi)pi−1 = pi0 varför pi0 ∈ piHpi−1. 5. Låt u ∈ U . Enligt definitionen av ideal så gäller {u} ∈ I varför fixG(u) ∈ F Ett filter F som bildas av ett ideal I på ovanstående sätt har egenskapen att en mängd x är symmetrisk omm det finns en mängd urelement Ex ∈ I sådan att fixG(Ex) ⊆ symG(x). Ex kallas för ett stöd (eng. support) för x. Antag nu att vi har byggt en permutationsmodell V sådan att det i V finns två kardinaltal n och m sådana att V  φ(n,m), där φ är något intressant för- hållande mellan de två kardinaltalen. Från detta kan vi alltså dra slutsatsen att det är konsistent med ZFU att det finns två sådana kardinaltal. 17 I själva verket kan vi åstadkomma mer än så. Antag att vi har en modell M  ZFU + AC, och att V är en permutationsmodell i M . Kärnan i M , vilket vi skriver M0, är helt enkelt elementen i M vars transitiva hölje saknar urelement. Då är det ett faktum att M0  ZF . Genom forcing kan vi nu skapa generiska extensioner, N , till M0 på ett sådant sätt att N  ZF och där strukturen hos godtyckligt stora delar av V kan återfinnas i N . Mer precist har vi följande sats 2 : Sats 4 (Jech-Sochor). Låt M vara en modell till ZFU +AC, U vara mäng- den av urelement i M , M0 vara kärnan i M och låt α vara ett godtyckligt ordinaltal i M . Då finns det, för varje permutationsmodell V ⊆M , en sym- metrisk extension N ⊇ M0 och en mängd U˜ ∈ N , sådan att N  ZF och där (Pα(U))V är isomorf med (Pα(U˜)N . Bevis. Se [6], sidorna 85-89. Idén i beviset är att expanderaM0 med |U | nya generiska mängder u˜0, u˜1, . . . där varje u˜i är en mängd av mängder av ordi- naltal sådan att |u˜i| > Pα(U). Därefter begränsar man den nya expanderade modellen genom att med hjälp av filtret som användes i konstruktionen av V endast ta med de mängder som är hereditärt symmetriska med avseende på permutationer av forcingvillkoren. På detta sätt fås modellen N  ZF som falsifierar urvalsaxiomet och där strukturen Pα({u˜0, u˜1, . . .}) uppför sig (är isomorf med) den ursprungliga strukturen Pα(U). Som en konsekvens av detta får vi följande faktum som ger oss ett tillräck- ligt villkor för när vi kan lyfta över ett påstående från en permutationsmodell till en modell för ZF. Definition 17. φ(x) är en begränsad formel omm φ(x) är på formen ∃αψ(x, α) där alla kvantifikatorer i ψ är på formen ∃z ∈ Pα(x) eller ∀z ∈ Pα(x). Faktum 18. Om V är en permutationsmodell och V  ∃xφ(x) där φ(x) är en begränsad formel så finns det en modell N  ZF sådan att N  ∃xφ(x). Alla påståenden om kardinaltal som vi, i den här texten, vill visa vara konsistenta med ZF är ekvivalenta med ett sådant begränsat existenspåstå- enden. Detta innebär att det räcker att hitta en permutationsmodell i vilket påståendet gäller. Vi kommer nu bygga fyra olika sådana permutationsmo- deller. I samtliga fall kommer M vara en modell till ZFU och U kommer vara (den uppräkneliga) mängden av alla urelement. 2 Vi har här valt att använda oss av formuleringen som finns i [6] där teorin för mängd- lära med urelement är något annorlunda. Självklart kan inte Pα(U) vara isomorft med någon struktur i vilken regularitetsaxiomet är sant. Satsen kan dock lätt omformuleras för att täcka in vår definition genom att begränsa ∈-relationen i Pα(U) så att u 6∈ u för alla u ∈ U . 18 3.2.3 Fraenkelmodellen Vi beskriver först och främst permutationsmodellen som närmast motsvarar modellen HOAD(M) ovan. Låt G vara gruppen av alla permutationer på U och låt I vara mängden av alla ändliga delmängder till U . Då är I ett ideal, varför vi skapar motsvarande filter F och bildar vår permutationsmodell VF (F för Fraenkel). Faktum 19. Låt m vara kardinaliteten hos U i VF . Följande påståenden är då sanna i VF : 1. U är oändlig och dedekindändlig. 2. fin(m) ‖ seq1-1(m) 3. fin(m) ‖ seq(m) 4. seq1−1 ‖ 2m 5. seq(m) ‖ 2m Bevis. Vi visar (1) och hänvisar till [5] för 2-4. Att U är oändlig är klart ty om det hade funnits en bijektion mellan U och ett heltal n i VF så hade denna bijektion redan funnits i M . Vi visar alltså att U är dedekindändlig. Antag att det finns en injektiv funktion f : ω → U . Då finns det ett stöd Ef ∈ I för f . Eftersom Ef är ändlig så kan inte gärna fixG(Ef ) ⊆ fixG(f [ω]) så det finns en permutation pi ∈ fixG(Ef ) sådan att pi 6∈ fixG(f [ω]), det vill säga pi(f(n)) 6= f(n) för något n. Samtidigt gäller pi(n) = n och alltså kan inte pi(f) = f vilket motsäger att Ef var ett stöd för f . 3.2.4 Ett efterlängtat motexempel Låt M vara en modell till ZFU med en uppräknelig mängd U av urelement och {Ui | i ∈ ω } vara en partition av U där varje Ui är uppräknelig. Låt nu G vara gruppen av alla permutationer, pi, på U sådana att pi[Ui] = Ui för alla Ui. Låt I genereras av familjen av ändliga unioner av Ui:n. Då är I ett ideal varför vi låter F vara filtret som fås av I och skapar en permutationsmodell VF . Följande gäller då i VF : 1. {Ui | i ∈ ω } är en uppräknelig familj av uppräkneliga mängder. 2. U = ⋃ i∈ω Ui är en ickeuppräknelig mängd. (2) är sant av egentligen samma anledning som i Fraenkelmodellen, dvs en total ordning av urelementen kan inte ha ett ändligt stöd. Vi visar istället (1). 19 Bevis. Låt fi = { 〈j, ui,j〉 | j ∈ ω } vara en uppräkning i M av elementen i Ui. Varje j ∈ ω är symmetrisk och varje ui,j är ett urelement så dessa är också symmetriska. Dessutom är fi självt symmetrisk eftersom fixG(Ui) ⊆ symG(fi) (i själva verket är dom ju lika). Alltså är varje Ui uppräknelig i VF . Dessutom är f = { 〈i, Ui〉 | i ∈ ω } trivialt symmetrisk eftersom pi(f) = f för varje pi ∈ G. 3.2.5 Den ordnade Mostowskimodellen Låt