för filosofie kanditatexamen i matematik vid

Göteborgs Universitet september 1998

Mängdlärans axiom och

den kumulativa hierarkin

ANDERS CLAESSON

Mängdlärans axiom

och

den kumulativa hierarkin

Anders Claesson

  claesson@math.chalmers.se

Förord

Hela denna uppsats skall väsentligen ses som ett försök att svara på en enda fråga, nämligen: Vad är en mängd? Ett naivt svar skulle kunna vara att en mängd är en samling objekt. Detta är dock alltför oprecist och leder till paradoxer. Ett svar man kan ge är att mängder är de objekt som tillhör den så kallade kumulativa hierarkin; vi kommer att se att Zermelo-Fraenkels axiom (ZF) är sanna i den kumulativa hierarkin. Om man i likhet med Platon tror att matematiska objekt har en verklig existens, så kanske man frågar sig om ZF ger en korrekt och fullständig bild av vårt mängduniversum? Den här typen av frågor kommer inte att diskuteras i uppsatsen. Jag vill dock nämna ett för Platonister vanligt förhållningssätt till ZF: Vi kan se ZF som ett instrument som tillåter oss att se åtminstone vissa delar av det verkliga mängduniversumet. Klart är att det finns utsagor som varken kan bevisas eller vederläggas från ZF, t.ex. den välkända kontinuumhypotesen. Den avsedda läsaren har studerat matematik på universitetsnivå och har helst också viss kännedom om logik. Appendix A innehåller en mycket kortfattad genomgång av första ordningens predikatlogik. Dock skall innehållet i appendix A ej ses som ett förkunskapskrav, utan uppsatsen är ämnad att vara läsbar även med ett minimum av förkunskaper i logik.

Tack!

Jag vill tacka min handledare Jan Smith, för alla insiktsfulla råd och för det stöd och den uppmuntran han givit mig under arbetets gång.

Innehåll

Förord i Tack! i 1. Mängdlärans fundament 1 1.1. Axiomen 1 1.2. Ordinaltal 5 1.3. Kardinaltal 9 2. Konsistensbevis 14 2.1. Den kumulativa hierarkin 14 2.2. De hereditära mängderna 17 2.3. Modeller 17 Appendix A. Första ordningens predikatlogik 19 Källförteckning 22

1. Mängdlärans fundament

1.1. Axiomen. Vi skall här bekanta oss med Zermelo-Fraenkels axiom (ZF) för mängdläran. Axiomen kommer att formuleras i ett första ordningens språk^{1}, vars enda primitiva symboler är de tvåställiga predikaten = och ∈. En tolkning, säg 𝔙, av mängdlärans språk definieras av en icke-tom domän över vilken variablerna avses variera, tillsammans med två binära relationer [[ ∈ ]]_{𝔙} och [[ =]]_{𝔙} på domänen. Om φ är ett påstående i mängdlärans språk, så är φ antingen sant eller falskt i tolkningen 𝔙. Som ett fånigt exempel kan vi låta vår domän vara ℕ och tolka ∈ och = som ≤ respektive =. Detta är en legitim tolkning av mängdlärans språk, trots att påståendet

∀x∀y(x = y → x ∈ y)

är sant under denna tolkning, men vederlägbart från ZF. Självklart är inte denna tolkning en modell för ZF. I den avsedda tolkningen, under vilken mängdlärans axiom antas vara sanna, tolkas x ∈ y som x är element i y, och x = y som x och y är lika. Vår domän är lite svårare att beskriva, informellt tänker vi oss att hela vårt mängduniversum byggs upp induktivt från tomma mängden. Detta leder oss till den kumulativa hierarkin:

0 : Tomma mängden
1 : Alla mängder vars element finns på nivå 0.
2 : Alla mängder vars element finns på nivå 0 eller 1.
⋮  ⋮
k : Alla mängder vars element finns på nivå 0 eller 1 eller … eller k − 1.
⋮  ⋮

Mängden {{{∅}}, ∅} återfinns t.ex. på nivå 3. Observera att elementen tillhörande en mängd också själva är mängder, ty vi har ingen speciell samling urelement på första nivån. Om mängdläran skall vara matematikens grunval vore det otillfredställande att inkludera element som vi inte vet någonting om. En fråga man kanske ställer sig är om nivåerna tar slut någon gång. Svaret är att det inte verkar rimligt, eftersom vi i så fall borde kunna föreställa oss att vi fullbordat alla nivåer, och att vi sedan går en nivå högre, med en motsägelse som följd. Efter nivåerna 1, 2, …, k, … kommer alltså nivå ω (= ℕ), följd av nivåerna ω +1, ω +1, …, ω +ω, … o.s.v. Vi kommer att använde oss av den kumulativa hierarkin för att motivera varför de axiom vi inför är sanna. Det första axiomet garanterar att vårt mängduniversum inte är tomt, vilket också ses vara trivialt sant i den kumulativa hierarkin.

Existensaxiomet. Det finns minst en mängd:

∃x(x = x)

Nästa axiom postulerar en fundamental egenskap hos ∈-predikatetet–dess relation till likhet.

1Se appendix A

Extensionalitetsaxiomet. Två mängder är lika om och endast om de innehåller samma element:

∀x∀y[x = y ↔ ∀z(z ∈ x ↔ z ∈ y)]

En naturlig princip för att bilda mängder kan tyckas vara abstraktionsprincipen: Om φ(x) är en formel, med x fri, så är {x : φ(x)} en mängd, d.v.s. ∃y∀x(x ∈ y ↔ φ(x)). Olyckligtvis är, som Bertrand Russell visade, detta axiomschema inkonsistent: Låt R = {x : x ∉ x}, då fås Russells paradox ur x ∈ R ⇔ x ∉ x. Ty låt x vara R, då gäller R ∈ R ⇔ R ∉ R, vilket är en motsägelse. Istället får vi nöja oss med en variant av abstraktionsprincipen som är inskränkt till redan existerande mängder. Vi säger att x är en delmängd till y, och skriver x ⊂ y, då ∀z(z ∈ x → z ∈ y).

Delmängdsaxiomet. Låt φ(x) vara en formel sådan att y inte förekommer i φ(x), då gäller: Givet en mängd a, så existerar det en delmängd av a innehållande precis de element i a som uppfyller φ(x):

∀a∃y∀x[x ∈ y ↔ x ∈ a ∧ φ(x)]

Observera att detta är ett axiomschema som till varje formel φ ger ett axiom och att φ kan ha fler fria variabler än x. Om så är fallet skall de fria variablerna betraktas som allkvantifierade. Delmängdsaxiomet tillåter oss alltså att bilda {x : x ∈ a ∧ φ(x)}. Speciellt kan vi bilda snittet mellan två mängder, x ∩ y = {z : z ∈ x ∧ z ∈ y}. Enligt existensaxiomet finns det åtminstone en mängd, säg y. Vi kan då formellt definiera tomma mängden, ∅, som {x : x ∈ y ∧ x ≠ x}. Notera också hur extensionalitetsaxiomet omöjliggör existensen av andra urelement än tomma mängden, ty om x och y är urelement, så innehåller de inga element och är därför lika. Delmängdsaxiomet är sant i den kumulativa hierarkin, ty på den nivå som a bildas har också alla delmängder till a bildats och då speciellt den delmängd vars element uppfyller φ. Följande tre axiom är specialfall av abstraktionsprincipen.

Paraxiomet. Givet två mängder a och b, så finns det en mängd vars enda element är a och b:

∀a∀b∃y∀x(x ∈ y ↔ x = a ∨ x = b)

Antag att a och b bildas på nivå k respektive l i den kumulativa hierarkin, då kan vi bilda {a, b} på nivå max(k, l) + 1.

Potensmängdsaxiomet. Givet en mängd a, så finns det en mängd som innehåller alla delmängder till a:

∀a∃y∀x(x ∈ y ↔ x ⊂ a)

Vi kan således bilda P(a) = {x : x ⊂ a}, potensmängden till a. Eftersom alla delmängder till a kommer att ha bildats på samma nivå som a, så kan vi på nästa nivå bilda P(a). Alltså är potensmängdsaxiomet sant i den kumulativa hierarkin.

Unionaxiomet. Givet en mängd a, så finns det en mängd vars element är elementen i elementen i a:

∀a∃y∀x[x ∈ y ↔ ∃z(x ∈ z ∧ z ∈ a)]

Detta axiom tillåter oss alltså att bilda {x : ∃z(x ∈ z ∧ z ∈ a)}, vi betecknar denna mängd med ⋃ a eller ⋃_{x∈a} x. Speciellt skriver vi ⋃{x, y} som x ∪ y. I den kumulativa hierarkin återfinns ⋃ a på samma nivå som a, eftersom elementen i a måste ha bildats tidigare än a. De mängder vars existens garanteras av de axiom vi hittills infört är alla ändliga. Det är därför dags att införa ett axiom som uttrycker att det finns minst en oändlig mängd. Först gör vi följande definition.

Definition. Givet en mängd x definierar vi efterföljaren, x^{+}, till x som

x^{+} = x ∪ {x}

Mer detaljerat bildar vi x^{+} så här: Givet x (och x), så bildar vi i enlighet med paraxiomet en mängd bestående av precis x (och x), d.v.s. {x}. Paraxiomet igen, nu givet x och {x}, ger {x, {x}}. Slutligen fås x∪{x} av unionaxiomet.

Oändlighetsaxiomet. Det finns en en mängd som innehåller tomma mängden och är sluten under efterföljaroperationen:

∃x[∅ ∈ x ∧ ∀y(y ∈ x → y^{+} ∈ x)]

Eftersom y^{+} = y ∪ {y} bildas på en nivå högre än y, så kräver detta axiom en oändlig växande följd av nivåer, och efter alla dessa nivåer en ny nivå där den oändliga mängden själv bildas. Detta axiom kan ses som ett första försök att säga något som garanterar att nivåerna i den kumulativa hierarkin inte har något upptänkligt slut. Av intuitionen att mängder bildas i steg följer det att ingen mängd är element i sig själv och att det inte förekommer cirkulära kedjor av typen x ∈ y∧y ∈ x. Med avsikt att utesluta sådana fenomen inför vi nästa axiom.

Regularitetsaxiomet. Om x är en icke-tom mängd, så innehåller x ett element som inte har något element gemensamt med x:

∀x[x ≠ ∅ → ∃y(y ∈ x ∧ y ∩ x = ∅)]

Distinktionen mellan mängd och klass: En klass är en formel med en fri variabel, säg x. Vi använder vanligtvis den informella notationen {x : φ(x)} för klassen som bestäms av φ. Innebörden av att vara element i en klass preciseras av

∀y[y ∈ {x : φ(x)} ↔ φ(y)]

Två klasser {x : φ(x)} och {x : ψ(x)} är lika om ∀x(φ(x) ↔ ψ(x)). Vidare gäller att en klass {x : φ(x)} är en mängd om ∃y∀x(φ(x) ↔ x ∈ y). Om vi kan visa negationen till detta påstående är {x : φ(x)} en äkta klass.

Definition. V =_{def} {x : x = x}

V är alltså klassen av alla mängder. V är en äkta klass ty annars är V element i sig själv, vilket strider mot regularitetsaxiomet. Om vi för ett ögonblick återvänder till Russells klass R, ser vi att också R är en äkta klass, ty det följer av regularitetsaxiomet att R = V. Frågan om R tillhör R saknar således formell mening, då elementen i en klass måste vara mängder. Vi har på så vis undvikit vi Russells paradox. Nu riktar vi vår uppmärksamhet mot en speciell klass: En funktionsklass är en formel φ med två fria variabel, säg x och y, för vilken vi kan visa ∀x∃!yφ(x, y), där ∃!y betyder att det finns exakt ett y. Således är ∀x∃!yφ(x, y) en förkortning för ∀x∀y∀z(φ(x, y) ∧ φ(x, z) → y = z). Domänen till φ är klassen {x : ∃yφ(x, y)} och kodomänen är klassen {y : ∃xφ(x, y)}. Med detta språkbruk introducerar vi nu ett axiomschema som säger att om domänen till en funktionsklass är en mängd, så är också dess kodomän en mängd.

Substitutionsaxiomet. Låt φ(x, y) vara en formel, ej innehållande z. Om φ(x, y) definierar en funktionsklass och vi är givna en mängd a, så kan vi bilda {y : ∃x(x ∈ a ∧ φ(x, y))}, d.v.s. bilden av a under φ:

∀x∃!yφ(x, y) → ∀a∃z∀y[y ∈ z ↔ ∃x(x ∈ a ∧ φ(x, y))]

På samma sätt som vid introduktionen av delmängdsaxiomet tillåter vi att φ har fler fria variabler än x. Substitutionsaxiomet är en utsaga om att nivåerna i den kumulativa hierarkin inte har något slut. Det är den starkaste utsagan som Zermelo-Fraenkels axiom gör i den här riktningen.

Urvalsaxiomet. Om z är en mängd av icke-tomma och parvis disjunkta mängder så finns det en ‘valmängd’ u med exakt ett element gemensamt med varje element i z:

\begin{aligned}∀z[∀x(x ∈ z → x ≠ ∅ ∧ ∀y(y ∈ z → x & ∩ y = ∅ ∨ x = y)) → \\ & → ∃u∀x∃v(x ∈ z → u ∩ x = \{v\})] \end{aligned}

I termer av nivåer motiverar vi urvalsaxiomet (AC) med att det inte finns någon anledning till att den av AC postulerade mängden inte skall existera. Ty vår intuitiva bild av den kumulativa hieriarkin säger oss att alla delmängder adderas till varje ny nivå. AC har orsaktat en hel del turbulens genom åren. Detta på grund av dess i högsta grad icke-konstruktiva natur. Axiomet postulerar existensen av en mängd som inte är specifierad utifrån elementen i mängden, utan bara kan konstrueras genom godtyckliga val. Därför intar AC lite av en särställning bland mängdlärans axiom. Vi änvänder beteckningarna

ZF = {EXIST, EXT, DEL, PAR, POT, UNION, INF, SUBST, REG}

och ZFC = ZF+AC (= ZF∪{AC}). (Förkortningarna skall förhoppningsvis vara självförklarande.) Vi kommer ofta att använda AC, speciellt i avsnittet om kardinaltal, och om inget annat explicit uttrycks skall alla resultat antas vara resultat i ZFC. Slutligen vill jag göra läsaren observant på att ZF innehåller (uppräkningsbart) oändligt många axiom, ty DEL och SUBST är axiomscheman. Dock gäller att om ZF ⊢ φ så finns det en ändlig delmängd Δ till ZF sådan att Δ ⊢ φ, ty härledningar är alltid ändliga.

Eliminering av definierade begrepp: I detta avsnitt har vi introducerat ett antal mängdteoretiska definitioner, så som ⊂, ∩ och ∅. Var detta berättigade definitioner? Detta kan synas vara en konstig fråga, eftersom det är praxis bland matematiker att utöka vokabulären genom nya definitioner. Emellertid gör vi här anspråk på en axiomatisk behandling av mängdläran, där axiomen formuleras i ett specifikt första ordningens språk, som vi här kommer att kalla L. Speciellt har vi explicit formulerat delmängds- och substitutionsaxiomet så att de skall tillämpas på formler i L. Trots detta använder vi oss alltså av symboler som inte ingår i L. Hur försvarar vi detta? De begrepp vi har definierat kan delas upp i tre kategorier: relationer, operationer och konstanter. En ny relation är helt enkelt ett förkortat skrivsätt för någon formel. T.ex. är x ⊂ y en förkortning för ∀z(z ∈ x → z ∈ y), vilket är en formel i L. Att introducera nya operationer är lite klurigare, eftersom vi utgående från våra axiom måste visa att den nya definitionen är välgrundad. Vi uttrycker detta lite mer formellt: Om φ(x_{1}, …, x_{n}, y) är en formel, med x_{1},…,x_{n} och y fria, och Γ är en mängd axiom sådana att

Γ ⊢ ∀x_{1}, …, ∀x_{n}∃!yφ(x_{1}, …, x_{n}, y)

så får vi definiera F (x_{1}, …, x_{n}) att vara det y sådant att φ(x_{1}, …, x_{n}, y). Formellt gör vi detta genom att utvidga L med funktionssymbolen F samt utöka Γ med axiomet

∀x_{1}, …, ∀x_{n}φ(x_{1}, …, x_{n}, F (x_{1}, …, x_{n}))

Introduktionen av konstanter är specialfallet då n = 0. Låt till exempel φ(x, y, z) vara ∀a(a ∈ z ↔ a ∈ x ∧ a ∈ y) och antag att Γ innehåller den instans av DEL som vi behöver för att visa ∀x∀y∃!zφ(x, y, z). Då introducerar vi x ∩ y genom att utvidga L med funktionssymbolen ‘∩’ samt addera axiomet

∀x∀y∀a(a ∈ x ∩ y ↔ a ∈ x ∧ a ∈ y)

till Γ. Låt L′ och Γ′ vara utvidgningar av L respektive Γ enligt ovanstående principer. Låt vidare T och T′ vara teorier till Γ respektive Γ′. Det är nu inte svårt att visa att T′ är en konservativ utvidgning av T i den meningen att varje sats i T′ som är formulerad i språket L också är en sats i T.

1.2. Ordinaltal. Ordinaltalen kan ses som en generalisering av de naturliga talen, vilka vi börjar med att studera. Hur kan vi definiera de naturliga talen i ZF? Uppenbarligen måste varje naturligt tal identifieras med en mängd. Naturligt verkar då följande induktiva definition

0 = ∅, n + 1 = n ∪ {n}

så att det naturliga talet n innehåller exakt n element. Vi säger att en mängd är induktiv om den innehåller tomma mängden och är sluten under efterföljaroperationen. Med detta språkbruk säger oändlighetsaxiomet helt enkelt att det existerar en induktiv mängd. Eftersom snittet av två induktiva mängder är en induktiv mängd (visas lätt) kan vi göra följande definition.

Definition. De naturliga talen, ℕ, definieras som snittet av alla induktiva mängder.

I detta sammanhang är det brukligt att beteckna ℕ med ω. Från definitionen ser vi direkt att ω ⊂ y för varje induktiv mängd y. Om elementen i ω är de ‘verkliga’ naturliga talen är en kverulantisk fråga. Det väsentliga är att de satisfierar Peanos axiom:

PA1. 0 ∈ ω

PA2. ∀n(n ∈ ω → n^{+} ∈ ω)

PA3. ∀n, m ∈ ω(n^{+} = m^{+} → n = m)

PA4. ∀n ∈ ω(0 ≠ n^{+})

PA5. ∀X ⊂ ω[(0 ∈ X ∧ ∀n ∈ X(n^{+} ∈ X)) → X = ω]

PA1, PA2, PA4 och PA5 följer direkt av definitionen av ω. Det återstår att visa PA3: Antag att n^{+} = m^{+}. Enligt regularitetsaxiomet och definitionen av efterföljare gäller det att n ∉ m ∨ m ∉ n. Av symmetriskäl kan vi anta att n ∉ m. Vi har då n ∈ n^{+} = m^{+} = m ∪ {m} ⇒ n ∈ m ∨ n = m. Alltså n = m. Vi identifierar det ordnade paret, (x, y), med mängden {x, {x, y}}. Det följer av extensionalitetsaxiomet att (x, y) = (x′, y′) om och endast om x = x′ och y = y′. Vidare definierar vi X × Y som mängden av alla ordnade par med första komponent i X och andra komponent i Y. En mängd R är en relation om ∀x ∈ R ∃y, z(x = (y, z)); speciellt om R ⊂ X × Y, så är R en relation från X till Y. Då (x, y) ∈ R skriver vi xRy. En partiell ordning är ett par (X, ≤), där X är en mängd och ≤ är en relation sådan att:

(i) ∀x ∈ X(x ≤ x)  (reflexiv)
(ii) ∀x, y ∈ X(x ≤ y ∧ y ≤ x → x = y) (antisymmetrisk)
(iii) ∀x, y ∈ X(x ≤ y ∧ y ≤ z → x ≤ z) (transitiv)

En linjär ordning (X, ≤) är en partiell ordning sådan att ∀x, y ∈ X(x ≤ y ∨ y ≤ x). Om x ≤ y ∧ x ≠ y skriver vi x < y. Relationen < är: (a) irreflexiv och (b) transitiv. Omvänt gäller att om < satisfierar (a) och (b) och ≤ är definierad av x < y ∨ x = y, så är (X, ≤) en partiell ordning. Vi säger också att (X, <) är en sträng partiell ordning om (X, ≤) är en partiell ordning och att (X, <) en (sträng) linjär ordning om ∀x, y ∈ X(x < y ∨ x = y ∨ y < x). Vidare är x; ett minsta element i X om ∀y ∈ X(x ≤ y); ett minimalt element i X om ¬∃y ∈ X(y < x). Av regularitetsaxiomet följer att varje icke-tom mängd har ett minimalt element. En mängd X är transitiv om ∀x, y(y ∈ x ∧ x ∈ X → y ∈ X), d.v.s. varje element i X är en delmängd till X.

Definition. Ett ordinaltal är en transitiv mängd vars element är transitiva.

En ekvivalent variant är att definiera ordinaltalen som de transitiva mängder vars element är linjärt ordnade av ∈-relationen.

Definition. Ett ordinaltal α kallas efterföljartal om det finns ett ordinaltal β sådant att α=β^{+}. Ett ordinaltal som inte är 0 eller ett efterföljartal kallas limestal.

Lemma 1.1.

(i) Tomma mängden är ett ordinaltal.
(ii) Om α är ett ordinaltal, så är α^{+} ett ordinaltal.
(iii) Alla naturliga tal förutom 0 är efterföljartal.
(iv) ω är det minsta limestalet.
(v) Om β ∈ α, där α är ett ordinaltal, så är β ett ordinaltal.

Bevis. (i) samt (v) följer direkt av definitionen av ordinaltal. (iii) och (iv) följer av n ∈ ω ⇒ n + 1 ∈ ω. Vi visar (ii): x ∈ α^{+} = α ∪ {α} implicerar x ∈ α ∨ x = α. Alltså är x transitiv och x ⊂ α ⊂ α^{+} ger att även α^{+} är transitiv. □

Definition. ON = {α : α är ett ordinaltal}

Antag att ON är en mängd, då är ON ett ordinaltal (visas lätt). Alltså har vi ON ∈ ON, vilket strider mot regularitetsaxiomet. Således är ON är en äkta klass.

Definition. α < β =_{def} α ∈ β och α ≤ β =_{def} α < β ∨ α = β, där α, β ∈ ON.

Lemma 1.2 (Transfinit induktion). För varje formel φ i ZFC gäller:

∀α ∈ ON[∀β < α φ(β) → φ(α)] → ∀α ∈ ON φ(α)

Bevis. Antag att premissen gäller och att ¬φ(α_{0}) för något α_{0} ∈ ON. Låt

x = {α : α < α_{0} ∧ ¬φ(α)}

vilket är en mängd ty x ⊂ α_{0}. Speciellt gäller x ≠ ∅, ty annars skulle premissen ge φ(α_{0}). Alltså innehåller x ett minimalt element α′. Om β < α′, så gäller β < α_{0}, enligt transitiviteten hos <-relationen, och vårt val av α′ ger oss att β ∉ x. Således gäller φ(β) och premissen ger slutligen φ(α′), vilket motsäger α′ ∈ x. □ Om vi vill visa φ(α) för något godtyckligt ordinaltal α, kan vi alltså anta att φ(β) gäller för alla β < α. Ett bevis enligt den här metoden kallas för ett bevis av φ(α) genom transfinit induktion (eller bara induktion) över α. Att φ(β) gäller för β < α kallas för induktionsantagande.

Proposition 1.3. (ON, <) är en linjär ordning.

Bevis. Irreflexiviteteten och transitiviteten följer av regularitetsaxiomet respektive definitionen av ordinaltal. Det återstår att visa:

∀α, β ∈ ON(α < β ∨ α = β ∨ β < α).

Låt φ(α, β) =_{def} α < β ∨ α = β ∨ β < α. Vi visar ∀βφ(α, β) med induktion över α, och φ(α, β) med induktion över β. Antag alltså:

∀βφ(γ, β) för alla γ < α_{0}  (1)
φ(α_{0}, δ) för alla δ < β_{0}  (2)

Nu gäller endera av α_{0} = β_{0}, α_{0} \ β_{0} ≠ ∅ eller β_{0} \ α_{0} ≠ ∅. Om α_{0} = β_{0}, så gäller φ(α_{0}, β_{0}). Antag nu att α_{0} \ β_{0} ≠ ∅. Då finns γ < α_{0} sådant att ¬(γ < β_{0}). Enligt induktionsantagande (1) gäller φ(γ, β_{0}), d.v.s. β_{0} < γ eller β_{0} = γ. Alltså gäller β_{0} < α_{0} varför vi har φ(α_{0}, β_{0}). På samma sätt visas att φ(α_{0}, β_{0}) gäller om β_{0} \ α_{0} ≠ ∅, och beviset för (2) implicerar φ(α_{0}, β_{0}) är klart. Med transfinit induktion kan vi från detta sluta oss till ∀βφ(α_{0}, β). Vi har därmed visat att (1) medför ∀βφ(α_{0}, β) och resultatet följer med induktion. □

Definition. (X, <) är en välordning om (X, <) är en linjär ordning och varje icke-tom delmängd till X har ett minsta element.

Vi ser t.ex. att varje ordinaltal α välordnas av ∈, eller mer formellt (α, ∈_{α}) är en välordning, där ∈_{α}= {(β, γ) ∈ α × α : β ∈ γ}. Två välordningar (X, <) och (Y, ˙<) är isomorfa och vi skriver (X, <) ≅ (Y, ˙<) om det finns en bijektion f : X → Y sådan att ∀z, w ∈ X(z < w ⇔ f(z) ˙<f(w)). Om a ∈ X, så låt pred(X, a) =_{def} {x ∈ X : x < a}.

Sats 1.4. Varje välordning är isomorf med ett unikt ordinaltal.

Bevisskiss. Vi skall visa att givet en välordning (X, <), så finns det ett unikt ordinaltal α sådant att (X, <) ≅ (α, ∈_{α}). Låt oss till att börja med konstatera att entydigheten är uppenbar, ty för ordinaltal sammanfaller “lika med” och “isomorf med”. Vi visar existensen: Låt

φ(b, β) =_{def} (pred(X, b), <) ≅ (β, ∈_{β})

och B = {b ∈ X : ∃β ∈ ONφ(b, β)}. Då gäller ∀b ∈ B∃!βφ(b, β), så enligt substitutionsaxiomet kan vi bilda α = {β : ∃b ∈ Bφ(b, β)}. Låt nu f ⊂ B×α vara den funktion som definieras av: f(b) är det (unika) ordinaltal, β sådant att φ(b, β). Vi ser direkt att R(f) = α. Det återstår att visa; (i) α är ett ordinaltal; (ii) f är en isomorfism från (B, <) till (α, ∈_{α}); (iii) B = X. Detta lämnar jag till den intresserade läsaren. □ Notera att vi i beviset ovan använder oss av substitutionsaxiomet för att visa existensen av mängden f ⊂ B × α. Utan substitutionsaxiomet kan man fortfarande utveckla det mesta av ‘vanlig’ matematik, men man kan inte visa sats 1.4.

Definition. Summan, α + β, av två ordinaltal definieras rekursivt över β:

α + 0 = α
α + β = \{ \begin{matrix}(α + γ)^{+} & om β är ett efterföljartal och β = γ^{+} \\ ⋃_{γ<β}(α + γ) & om β är ett limestal \end{matrix}

Definition. Produkten, α·β, av två ordinaltal definieras rekursivt över β:

α·0 = 0
α·β = \{ \begin{matrix}(α·γ) + α & om β är ett efterföljartal och β = γ^{+} \\ ⋃_{γ<β}(α·γ) & om β är ett limestal \end{matrix}

Definition. Exponententiering: α^{β} definieras rekursivt över β:

α^{0} = 1
α^{β} = \{ \begin{matrix}α^{γ} ·α & om β är ett efterföljartal och β = γ^{+} \\ ⋃_{γ<β} α^{γ} & om β är ett limestal \end{matrix}

Lemma 1.5. Följande gäller för godtyckliga ordinaltal α, β och γ:

\begin{matrix}(i) & α·1 = α = 1·α \\ (ii) & α + (β + γ) = (α + β) + γ \\ (iii) & α·(β + γ) = α·β + α·γ \\ (iv) & α·(β·γ) = (α·β)·γ \end{matrix}

Bevis. Jag nöjer mig med att med hjälp av transfinit induktion visa (iv). Antag att α·(β·δ) = (α·β)·δ för alla δ < γ. Om γ = ζ + 1 är ett efterföljartal, så gäller:

α·(β·γ) = α·(β·ζ + β) enl. def. av multiplikation
= α·(β·ζ) + α·β enl. (iii)
= (α·β)·ζ + α·β enl. induktionsantagandet
= (α·β)·γ  enl. def. av multiplikation

Om γ är ett limestal så är α·(β·γ) = α·⋃{β·ζ : ζ < γ}. Eftersom följden av ordinaltal β·ζ, där ζ < γ, är strängt växande (förutom om β = 0, vilket är trivialt), så följer det att unionen måste vara ett limestal. Eftersom något η mindre än detta limestal är mindre än β·ζ för något ζ < γ så har vi:

α·(β·γ) = ⋃{α·η : η < ⋃{β·ζ : ζ < γ}}
= ⋃{α·(β·ζ) : ζ < γ}
= ⋃{(α·β)·ζ : ζ < γ}  enl. induktionsantagandet
= (α·β)·γ  enl. def. av multiplikation
□

Observera att varken addition eller multiplikation i allmänhet kommuterar. Till exempel 1 + ω = ω ≠ ω + 1 och 2·ω = ω ≠ ω + ω = ω·2. Dock gäller som väntat att både addition och multiplikation kommuterar på de naturliga talen.

1.3. Kardinaltal. En funktion är en relation f sådan att ∀x∃!y((x, y) ∈ f). Om (x, y) ∈ f är det brukligt att skriva f(x) = y. Definitions- och värdemängden till en funktion f definieras av

D(f) = {x : ∃y(f(x) = y)} respektive R(f) = {y : ∃x(f(x) = y)}.

Om D(f) = X och R(f) ⊂ Y säger vi att f är en funktion från X till Y och skriver f : X → Y. Vi definierar också Y^{X} som mängden av alla f : X → Y. Vidare säger vi att f : X → Y är injektiv om f(x) = f(x′) ⇒ x = x′ för alla x, x′ ∈ X, surjektiv om R(f) = Y och bijektiv om f är injektiv och surjektiv. I detta avsnitt är vi intresserade av att kunna jämföra mängder med avseende på hur många element de innehåller. Vi säger att två mängder X och Y är likmäktiga och skriver X ∼ Y om det finns en bijektion mellan X och Y. På liknande sätt skriver vi X ≲ Y om det finns en injektion från X in i Y. Det är lätt att verifiera att ≲ är en transitiv relation och att ∼ är en ekvivalensrelation (d.v.s. en reflexiv, symmetrisk och transitiv relation). Ett djupare resultat är följande.

Schröder-Bernsteins sats. Om X ≲ Y och Y ≲ X, så X ∼ Y.

Bevis. Antag att f : X → Y och g : Y → X är injektioner. Tag en punkt x ∈ X; om x ∈ R(g), så bildar vi g^{−1}(x) ∈ Y; om g^{−1}(x) ∈ R(f), så bildar vi f^{−1}(g^{−1}(x)) ∈ X; o.s.v. Antingen fortgår den här processen i oändlighet, eller så slutar den med ett element i X \R(g) eller i Y \R(f). I dessa tre fall säger vi att x tillhör X_{∞}, X_{X} respektive X_{Y}. Således är X_{∞}, X_{X} och X_{Y} en partition av X, d.v.s. X är den disjunkta unionen av dessa tre mängder. På samma sätt får vi att Y_{∞}, Y_{X} och Y_{Y} är en partition Y. Klart är att f avbildar X_{∞} på Y_{∞} och X_{X} på Y_{X}. Vidare avbildar g Y_{Y} på X_{Y}. Allså är

h(x) = \{ \begin{matrix}f(x) & om x ∈ X_{∞} ∪ X_{X} \\ g^{−1}(x) & om x ∈ X_{Y} \end{matrix}

en bijektion från X till Y. □ Man bestämmer storleken av en ändlig mängd genom att räkna dess element. Mer generellt gäller det att om X kan välordnas, så finns det något ordinaltal α sådant att X ∼ α (enl. sats 1.4). Men kan varje mängd välordnas? Vi kommer med hjälp av urvalsaxiomet att visa att så är fallet. Den form vilken urvalsaxiomet är given i avsnitt 1.1 är inte den i praktiken mest användbara, det är bara den form som enklast återges i primitiv notation. Det är mer praktiskt att använda ‘val-funktioner’ istället för ‘valmängder’. Restriktionen till mängder vars element är skilda från ∅ och parvis disjunkta blir då överflödig.

Lemma 1.6. ∀x∃f[f : x → ⋃x ∧ ∀y ∈ x(y ≠ ∅ → f(y) ∈ y)]

Bevis. För att kunna använda urvalsaxiomet byter vi taktiskt varje mängd y i x mot y′ = {(y, t) : t ∈ y}. Då gäller ∀y_{1}, y_{2} ∈ x(y_{1} ≠ y_{2} → y′_{1} ∩ y′_{2} = ∅). Låt z = {y′ : y ∈ x ∧ y ≠ ∅}. Vi ser att z är en delmängd till P(x × ⋃ x) och är därför en mängd. Vidare satisfierar z premissen i urvalsaxiomet. Vi har således ett u sådant att y′ ∩ u är en singeltonmängd för varje y′ ∈ z. Eftersom denna mängd måste vara av formen {(y, t)} för något t ∈ y, så är f = u ∩ ⋃ z en funktion sådan att f(y) ∈ y för varje y ∈ x, y ≠ ∅. Om ∅ ∈ x tar vi f ∪ {(∅, ∅)} för att få en funktion som satisfierar lemmat. □

Välordningssatsen. Alla mängder kan välordnas.

Bevis. Vi kommer att visa ∀x∃α ∈ ON(x ∼ α). Eftersom (α, ∈_{α}) är en välordning kommer x att välordnas genom bijektionen. Låt S = P(x) \ ∅ och i enlighet med lemma 1.6 låt f : S → x vara en ‘val-funktion’ för S, så att f(s) ∈ s för varje s ⊂ x, s ≠ ∅. Definiera nu, med transfinit rekursion över ordinaltalen, en funktion g sådan att:

g(α) = \{ \begin{matrix}f(x \ \{g(β) : β < α\}) & om x \ \{g(β) : β < α\} ≠ ∅ \\ z & annars \end{matrix}  (3)

där z inte är element i x. På så vis väljer vi i varje steg, med hjälp av f, ett element från de element i x som inte redan valts. Antag nu att α är det första ordinaltal sådant att x ⊂ {g(β) : β < α} om ett sådant existerar. Då är g|_{α} injektiv (enligt (3)), D(g|_{α}) = α och R(g|_{α}) = x, så att α ∼ x som önskat. Nu återstår det att visa att ett sådant α existerar. Eftersom g är injektiv om vi undantar z, så måste y = {β : g(β) ∈ x} vara en mängd enligt substitutionsaxiomet på x. Vi ser lätt att y är ett ordinaltal, säg γ. Antag nu att x ⊄ {g(β) : β ∈ γ}, då är g(γ) = f(x \ {g(β) : β < γ}) ∈ x och vi har γ ∈ y, d.v.s. γ ∈ γ, vilket är en motsägelse. □ Vi har nu visat att urvalsaxiomet implicerar välordningssatsen. Man kan visa att välordningssatsen i själva verket är ekvivalent med urvalsaxiomet . Det finns otaliga andra satser som också är ekvivalenta med urvalsaxiomet, varav en av de mer välkända är Zorns lemma. Innan vi formulerar lemmat behöver vi lite terminologi: En kedja i en av ≤ partiellt ordnad mängd X är en delmängd Y till X som är linjärt ordnad av < (d.v.s. ≤ och ≠) begränsad till Y × Y. En övre begränsning till Y är ett element u ∈ X sådant att ∀y ∈ Y (y ≤ u). Ett maximalt element till X är ett element m ∈ X sådant att ¬∃x ∈ X(m < x). Då säger Zorns lemma: Om x är en icke-tom partiellt ordnad mängd i vilken varje kedja har en övre begränsning, så har X ett maximalt element. Detta är en i matematiken ofta använd sats. Jag kommer dock inte att behöva den och avstår också från att bevisa densamma.

Definition. Låt, för varje mängd X, kardinaliteten av X, |X|, vara det minsta ordinaltal α sådant att X ∼ α. Vidare är α ett kardinaltal om |α| = α.

Eftersom X ∼ Y ⇒ |X| = |Y | och |X| ∼ X, så gäller det att |X| väljer ut en unik representant från varje ∼-ekvivalensklass. Utan större ansträngning kan vi visa att ω samt varje n ∈ ω är kardinaltal.

Definition. En mängd X är; ändlig om |X| < ω; oändlig om X inte är ändlig; uppräknelig om |X| ≤ ω; överuppräknelig om X inte är uppräknelig.

Cantors sats. ∀X[¬(P(X) ≲ X)]

Bevis. Obsevera först att x ↦ {x} är en injektion från X till P(X). Alltså har vi X ≲ P(X). Det återstår att visa X ≁ P(X). Antag att det finns en surjektion f : X → P(X) och låt A = {x ∈ X : x ∉ f(x)}. Eftersom A ∈ P(X), så finns det a ∈ A sådant att f(a) = A. Av definitionen av A följer nu att:

a ∈ A ⇒ a ∉ f(a) ⇔ a ∉ A

vilket är en motsägelse. Antagandet att det finns en sådan bijektion var således falskt. □ Potensmängdsoperationen utrustar oss alltså med ett sätt att konstruera större och större kardinaltal. Faktum är att vi inte skulle komma långt utan den, ty det går att visa att det är konsistent med ZFC − POT att alla mängder är uppräkningsbara.

Definition. Addition, multiplikation och exponentiering av två godtyckliga kardinaltal κ och λ definieras av:

\begin{aligned}(i) & κ ⊕ λ & = & |κ × \{0\} ∪ λ × \{1\}| \\ (ii) & κ ⊙ λ & = & |κ × λ| \\ (iii) & κ^{λ} & = & |κ^{λ}| \end{aligned}

Observera att κ^{λ} i högerledet i (iii) betecknar mängden av funktioner från λ till κ. Vi ser direkt att ⊕ och ⊙ är kommutativa. Vidare kan man också visa att |κ + λ| = |λ + κ| = κ ⊕ λ och |κ·λ| = |λ·κ| = κ ⊙ λ. Alltså har vi t.ex. ω ⊕ 1 = |1 + ω| = ω < ω + 1 och ω ⊙ 2 = |2·ω| = ω < ω·2. En praktisk räkneregel för oändliga kardinaltal är κ ⊕ λ = κ ⊙ λ = max(κ, λ).

Proposition 1.7. Om |X| = κ, så |P(X)| = 2^{κ}.

Bevis. Identifiera varje delmängd till X med motsvarande karakteristiska funktion χ : κ → 2. □ Lägg märke till att kardinaltals exponentiering inte är det samma som ordinaltals exponentiering. Ordinaltalet 2^{ω} är lika med ω, men kardinaltalet 2^{ω} är lika med |P(ω)| vilket är strängt större än ω enligt Cantors sats.

Definition. Efterföljaren till kardinaltalet κ, κ^{+}, är det minsta kardinaltal som är större än κ.

Definition. Ett kardinaltal κ kallas efterföljarkardinaltal om det finns ett kardinaltal λ sådant att κ = λ^{+}. Ett kardinaltal som inte är 0 eller ett efterföljarkardinaltal kallas limeskardinaltal.

Definition. ℵ_{α} definieras med transfinit rekursion över α.

ℵ_{0} = ω
ℵ_{α} = \{ \begin{matrix}(ℵ_{β})^{+} & om α är ett efterföljartal och α = β + 1 \\ ⋃_{β<α} ℵ_{β} & om α är ett limestal \end{matrix}

Proposition 1.8. ℵ_{α} har följande egenskaper:

(i) ℵ_{α} är ett kardinaltal för varje α.
(ii) Varje oändligt kardinaltal är lika med ℵ_{α} för något α.
(iii) α < β ⇒ ℵ_{α} < ℵ_{β}
(iv) ℵ_{α} är ett limeskardinaltal ⇔ α är ett limestal.
(v) ℵ_{α} är ett efterföljarkardinaltal ⇔ α är ett efterföljartal.

Bevis. Utelämnas. □

Definition. Kontinuumhypotesen, CH, är påståendet 2^{ℵ_{0}} = ℵ_{1}. Den generaliserade kontinuumhypotesen, GCH, är påståendet 2^{ℵ_{α}} = ℵ_{α+1}, för varje α.

Det är brukligt att också använda beteckningen 𝔠 för 2^{ℵ_{0}}. Kardinaltalet 𝔠 kallas kardinaliteten av kontinuum eftersom 𝔠 = |ℝ|. Vi kan därför också formulera CH utgående från de reella talen. T.ex. är CH ekvivalent med: Varje överuppräknelig delmängd till ℝ har samma kardinalitet som hela ℝ. K. Gödel visade 1939 att CH är konsistent^{2} med ZF. Senare, 1963, visade P. J. Cohen att också negationen till CH är konsistent med ZF. Alltså är CH oberoende av ZF.

Definition. Låt α och β beteckna ordinaltal.

(i) α är kofinal med β om α ≤ β ∧ ∃f[f : α→β ∧ β = ⋃ R(f)].
(ii) Kofinaliteten för β, cf(β), är det minsta α sådant att α är kofinal
med β.
(iii) α är reguljär om cf(α) = α, annars är α singulär.

Definition. Låt κ och λ beteckna kardinaltal.

(i) κ är svagt ouppnåeligt om κ > ω är ett reguljärt limeskardinaltal.
(ii) κ är starkt ouppnåeligt om κ > ω är reguljärt och ∀λ < κ(2^{λ} < κ).

2Se appendix A sidan 21.

Idén bakom den här definitionen är att ett kardinaltal κ är uppnåeligt om det kan konstrueras underifrån genom att använda de till buds stående mängdbildningsprinciperna, varav de två starkaste är potensmängdsaxiomet och substitutionsaxiomet, vilket avspeglar sig i villkoren κ reguljärt respektive ∀λ < κ(2^{λ} < κ). Klart är att ω är ouppnåeligt i det här avseendet, men vi väljer att utesluta ω i definitionen, eftersom ω garanteras av oändlighetsaxiomet.

2. Konsistensbevis

Genom hela vår diskussion om mängdläran har vi antagit att den är konsistent eller ekvivalent att den har en modell. När ZFC:s axiom hade etablerats var det en naturlig uppgift att visa att ZFC är en konsistent teori. D. Hilbert var den som först föreslog detta program, runt 1920, men bara tio år senare visade K. Gödel att, om mängdläran är konsistent, så kan ett bevis av dess konsistens inte formaliseras i mängdläran. En annan intressant fråga är om ZFC är en fullständig teori i den betydelsen att varje påstående i ZFC kan bevisas eller motbevisas utgående från axiomen. Gödel visade att så inte är fallet. Mer precist visade han att om mängdläran är konsistent, så är den ofullständig; och att dess ofullständighet är en väsentlig sådan, vilken inte kan åtgärdas genom att lägga till ändligt många nya axiom eller axiomscheman. Ovan nämnda resultat av Gödel brukar kallas för Gödels två ofullständighetssatser. Sensmoralen av allt detta är att vi inte kan förvänta oss att finna ett ‘själv-uppbärande’ bevis av konsistensen av något formellt system kraftfullt nog att fungera som fundament för matematiken. Om vi vill bevisa konsistensen av ett sådant system T, måste vi göra antaganden som är starkare än T. Det finns ett uppenbart sådant antagande, nämligen att lägga till Con(T)^{3} som ett axiom, men detta blir ju något löjeväckande och föga givande. Vi får helt enkelt nöja oss med intuitiva bevis av mänglärans konsistens samt relativa konsistensbevis, d.v.s. bevis av typen Con(T_{1}) ⇒ Con(T_{2}), t.ex. Con(ZF) ⇒ Con(ZFC).

2.1. Den kumulativa hierarkin. I avsnitt 1.1 använde vi oss av den kumulativa hierarkin för att motivera varför mängdlärans axiom i någon intuitiv mening är sanna. Vi kan också definiera den kumulativa hierarkin formellt i mängdläran, vilket vi nu gör.

Definition (Kumulativa hierarkin). V_{α} definieras med transfinit rekursion över ordinaltalen.

V_{0} = ∅
V_{α} = \{ \begin{matrix}P(V_{β}) & om α är ett efterföljartal och α = β + 1 \\ ⋃_{β<α} V_{β} & om α är ett limestal \end{matrix}

Definition. V^{∗} = ⋃{V_{α} : α ∈ ON}

Det följer direkt av definitionen av den kumulativa hierarkin och en enkel induktion att

∀α ∈ ON ∀β < α(V_{β} ⊂ V_{α}).

Således är V_{α} växande i α och om x ∈ V^{∗} så måste det minsta α sådant att x ∈ V_{α} vara ett efterföljartal enligt definitionen av den kumulativa hierarkin.

Definition. Om x ∈ V^{∗}, så är rang(x) det minsta β sådant att x ∈ V_{β+1}.

Precis som vi önskade, vid införandet av regularitetsaxiomet, finns det inget x i V^{∗} sådant att x ∈ x, ty då skulle vi ha rang(x) < rang(x). Analogt utesluts cirkulära kedjor av typen x ∈ y ∧ y ∈ x, ty detta skulle implicera rang(x) < rang(y) < rang(x).

3Con(T) betyder att T är en konsistent teori, se appendix A sidan 21.

Lemma 2.1. ∀α ∈ ON(V_{α} = {x ∈ V^{∗} : rang(x) < α})

Bevis. x ∈ V^{∗} ∧ rang(x) < α ⇔ ∃β < α(x ∈ V_{β+1}) ⇔ x ∈ V_{α} □

Lemma 2.2. ∀y ∈ V^{∗}(rang(y) = ⋃{rang(x) + 1 : x ∈ y})

Bevis. Låt α = ⋃{rang(x) + 1 : x ∈ y} och β = rang(y), då har vi x ∈ y ∧ y ∈ P(V_{β}) ⇒ x ∈ V_{β}. Lemma 2.1 implicerar att rang(x) < β vilket ger α ≤ β och ∀x ∈ y(rang(x) < α) ⇒ y ⊂ V_{α} ⇒ y ∈ V_{α+1} ⇒ β ≤ α. Alltså α = β. □

Lemma 2.3. ∀α ∈ ON(α ∈ V^{∗} ∧ rang(α) = α)

Bevis. Transfinit induktion: Antag att lemmat är sant för alla β < α, då har vi β ∈ V_{β+1} ⊂ V_{α} ⇒ α ⊂ V_{α} ⇒ α ∈ V_{α+1}. Enligt lemma 2.2 gäller det att rang(α) = ⋃{β + 1 : β < α} = α. Alltså är lemmat sant för alla α ∈ ON. □ Den kumulativa hierarkin ger upphov till en tilltalande bild av vårt mängdteoretiska universum:

[figure: 0; 1; 2; ω; V_{α}; α]

Idén med bilden är att ordinaltalen bildar en ryggrad som löper upp längs universums mitt, och att den nivå där en given mängd först uppenbarar sig bestäms av dess rang. Lemma 2.1 säger oss därför att V_{α} fås genom att hugga av bilden vid nivå α.

Lemma 2.4.

(i) rang({x, y}) = max(rang(x), rang(y)) + 1
(ii) rang((x, y)) = max(rang(x), rang(y)) + 2
(iii) rang({a : a ∈ x ∧ φ(a)}) ≤ rang(x)
(iv) rang(P(x)) = rang(x) + 1
(v) rang(⋃ x) ≤ rang(x)

Låt ℤ vara ringen av heltal, ℚ kroppen av rationella tal, ℝ kroppen av reella tal och ℂ kroppen av complexa tal. Vilken rimlig definition som helst av dessa objekt duger för vår diskussion. För klarhet antar vi: ℤ = ω×ω/ ≅, där (n, m) representerar n−m. ℚ = (ℤ×(ℤ\{0}))/ ≅, där (n, m) representerar \frac{n}{m}. Elementen i ℝ är ekvalensklasser av rationella Cauchy-följder:

ℝ = {f:ω →ℚ | ∀ϵ>0∃N ∈ ω∀n, m ∈ ω(m, n > N → |f(m)−f(n)| < ϵ)}/ ≅ I vart och ett av de tre ovanstående definitionerna antar vi att ekvivalens relationen ≅ är definierad på lämpligt vis. Slutligen är ℂ = ℝ×ℝ, där (x, y) representerar x + iy.

Proposition 2.5. ℤ, ℚ, ℝ och ℂ är element i V_{ω+15}.

Bevis. (n, m) ⇒ rang((n, m)) ≤ max(rang(m), rang(n)) + 2 < ω + 2, där den första olikheten ges av Lemma 2.4(ii). Alltså ℤ ∈ V_{ω+4}, eftersom ℤ är en mängd av ekvivalensklasser av sådana talpar. Analogt får vi ℚ ∈ V_{ω+8} och ℝ ∈ V_{ω+12}, ty ℝ ⊂ P(ℚ^{ω}) ⊂ PP(ω × ℚ). Slutligen får vi ℂ ∈ V_{ω+15}. □ Vi har nu visat att våra välbekanta talsystem existerar i den kumulativa hierarkin. Vårt mål nu är att visa att varje mängd tillhör den kumulativa hierarkin, vilket i vår notation betyder ∀x∃α ∈ ON(x ∈ V_{α}) eller ekvivalent V = V^{∗}. För att visa detta behöver vi en något starkare induktionsprincip än den lemma 1.2 tillhandahåller. Vi börjar med en definition.

Definition. TC(X) = ⋃_{n∈ω} ⋃^{n} X, där ⋃^{0} X = X, ⋃^{n+1} X = ⋃(⋃^{n} X).

Intentionen är att TC(X), det transitiva höljet till X, skall ‘se’ bakåt i den kumulativa hierarkin och samla upp alla element som förekom i bildandet av X, d.v.s. elementen i X och elementen i elementen i X o.s.v. Vi inser lätt att TC(X) är den minsta transitiva mängd som har X som delmängd.

Lemma 2.6 (∈-induktion). För varje formel φ i ZFC gäller:

∀x[∀y ∈ xφ(y) → φ(x)] → ∀xφ(x)

Bevis. Antag att premissen gäller och att ¬φ(z). Låt v = {x : x ∈ TC(z) ∧ ¬φ(x)}. Eftersom z ∈ v, så innehåller x ett minimalt element x. Om y ∈ x, så y ∈ TC(x) (ty TC(x) transitiv) och y ∉ v. Således gäller φ(y) och premissen ger slutligen φ(x), vilket motsäger x ∈ v. □

Sats 2.7. ∀x∃α ∈ ON(x ∈ V_{α})

Bevis. Vi visar ∀x∃α∈ON(x ⊂ V_{α}) med ∈-induktion över x. Låt α vara ett ordinaltal större än alla ordinaltal i {rang(y) : y ∈ x}, t.ex. efterföljaren till unionen av dessa ordinaltal. Om y ∈ x och β = rang(y), så är y delmängd till V_{β}, enligt induktionsantagandet. Alltså y ∈ V_{α} och vi har visat x ⊂ V_{α}. Satsen följer nu av x ⊂ V_{α} ⇒ x ∈ V_{α+1}. □ Sats 2.7 är helt beroende av regularitetsaxiomet. Det är i själva verket inte svårt att visa att den är ekvivalent med regularitetsaxiomet. Låt oss för ett ögonblick betrakta mängdteori utan regularitetsaxiomet. Vi kan då definiera klassen av välgrundade mängder som de mängder som uppfyller regularitetsaxiomet. En typisk icke välgrundad mängd är x = {x}. Dylika mängder har använts för att representera strömmar i datavetenskapen. Men all ‘vanlig’ matematik verkar försiggå i bland de välgrundade mängderna och regularitetsaxiomet begränsar vårt mängduniversum till precis dessa mängder.

2.2. De hereditära mängderna. Vi skall här studera en speciell samling mängder, som lämpar sig bra för att konstruera modeller i ZFC.

Definition. H(κ) = {x : |TC(x)| < κ}, för varje oändligt kardinaltal κ.

Elementen i H(κ) kallas de hereditära mängderna av kardinalitet mindre än κ. Speciellt är H(ω) mängden av de hereditärt ändliga mängderna. H(ω) kan också ges en något mer intuitiv definition: H(ω) är den minsta mängden som uppfyller:

(i) ∅ ∈ H(ω)
(ii) Om x_{1}, …, x_{n} tillhör H(ω), så {x_{1}, …, x_{n}} ∈ H(ω).

Att H(κ) verkligen är en mängd och inte en äkta klass följer av:

Lemma 2.8. H(κ) ⊂ V_{κ}, för varje oändligt kardinaltal κ.

Bevis. Vi visar att rang(x) < κ för ett godtyckligt men fixt x ∈ H(κ). Låt t = TC(x) och S = {rang(y) : y ∈ t}, så att S ⊂ ON. Vi börjar med att visa att S är ett ordinaltal. Låt α vara det minsta ordinaltalet som inte tillhör S, då är α en delmängd till S. Om α ≠ S, så låt β vara det minsta elementet i S som är större än α, och tag ett y ∈ t med rang(y) = β. Eftersom t är transitiv har vi ∀z ∈ y(rang(z) < α), så att rang(y) = ⋃{rang(z) + 1 : z ∈ y} ≤ α, vilket är en motsägelse. Alltså α = S. □

Lemma 2.9. Om κ är reguljärt, så är H(κ) = V_{κ} om och endast om κ = ω eller κ är starkt ouppnåeligt.

Bevis. Om κ = ω eller κ är starkt ouppnåeligt så kan vi med en enkel induktion visa ∀α < κ(|V_{α}| < κ). Om nu rang(x) = α < κ, så är TC(x) ⊂ V_{α} och |TC(x)| < κ. Således får vi V_{κ} ⊂ H(κ), vilket enligt lemma 2.8 implicerar V_{κ} = H(κ). Om κ > ω är reguljärt och inte starkt ouppnåeligt fixerar vi ett λ sådant att 2^{λ} ≥ κ. Då får vi P(λ) ∈ V_{κ} \ H(κ). □

2.3. Modeller. En modell av någon mängd påståenden Γ är en tolkning sådan att alla påståenden i Γ är sanna i tolkningen. Med en tolkning av ZFC menar vi som bekant (om ej bekant se appendix A) en icke-tom domän tillsammans med två binära relationer på domänen, men eftersom vi alltid kommer att tolka = och ∈ på avsett vis, identifierar vi tolkningen med dess domän.

Proposition 2.10. H(ω) är en modell för ZFC − INF + ¬INF.

Bevis. Vi behöver visa att varje axiom i ZFC−INF+¬INF är sant i H(ω) = V_{ω}. EXIST och EXT är trivialt sanna. Lemma 2.4 visar att alla mängder vi kan bilda med hjälp av DEL, PAR, POT samt UNION har rang mindre än ω. SUBST är sant ty bilden av en ändlig mängd är ändlig. Vi visar nu att REG är sant: Tag x ∈ V_{ω} sådant att x ≠ ∅. Mängden x innehåller något element, säg y, av lägsta rang. Då är y ∩ x = ∅, ty ett gemensamt element skulle ha lägre rang än y. INF är ej sant i V_{ω}, ty tag x ∈ V_{ω}, n = rang(x), då finns y ∈ x sådant att rang(y) = n−1 och rang(y^{+}) = rang(y ∪{y}) = n, vilket implicerar y^{+} ∉ x. □

En slutsats vi kan dra från detta är att det inte var onödigt att ta med INF i ZFC. Ty vi har funnit en modell där INF falskt och enligt sundhetssatsen^{4} kan vi därför inte härleda INF från ZFC − INF. Låt Z = ZF − SUBST (Zermelos mängdteori). Då har vi följande proposition, vilken torde vara speciellt intressant i ljuset av proposition 2.5.

Proposition 2.11. V_{ω+ω} är en modell för Z.

Bevis. Med samma typ av argument som i beviset av ovanstående proposition finner vi att EXIST, EXT, DEL, PAR, POT, UNION och REG alla är sanna. INF är sant ty ω ∈ V_{ω+1} ⊂ V_{ω+ω}. □ Jag ämnar nu visa att Z ger en svagare teori än ZF. Vi gör detta genom att visa att det finns en utsaga, t.ex. sats 1.4, vilken är härledbar från ZF men inte från Z. Vi erinrar oss sats 1.4: Varje välordning är isomorf med ett unikt ordinaltal. Vi kommer nu visa att denna sats inte är härledbar från Z. Enligt lemma 2.3 är ordinaltalen i V_{ω+ω} helt enkelt alla ordinaltal mindre än ω + ω. Men P(ω × ω) ∈ V_{ω+ω}, så varje välordning av ω tillhör V_{ω+ω}. Bland dessa välordningar finns det uppenbarligen någon välordning som är isomorf med ω + ω; men detta är inte ett ordinaltal i V_{ω+ω}, så den aktuella välordningen är inte isomorf med något ordinaltal i V_{ω+ω}. Alltså är sats 1.4 inte sann i V_{ω+ω} och därför inte heller härledbar från Z. Alternativt kan vi från ZF explicit bilda ordinaltalet ω + ω och (igen) observera att detta inte är ett ordinaltal i V_{ω+ω}. Låt φ(x, y) vara formeln y = ω + x. Vi ser direkt att φ uppfyller ∀x∃!yφ(x, y) och således är en funktionsklass. Enligt substitutionsaxiomet kan vi då bilda bilden av ω under φ, d.v.s. följande mängd

{y : ∃x ∈ ω φ(x, y)} = {ω + x : x ∈ ω} = ω + ω

Proposition 2.12. H(κ) är en modell för ZFC − POT + ¬POT om κ > ω är reguljärt.

Bevis. Utelämnas. För ett bevis se Kunen [11, s 132]. □

Proposition 2.13. H(κ) är en modell för ZFC ⇔ κ är starkt ouppnåeligt.

Bevis. Enligt föregående proposition återstår det bara att visa att POT är sant i H(κ), vilket är ekvivalent med:

∀x ∈ H(κ)(P(x) ∈ H(κ))

Detta är sant om H(κ) = V_{κ} men falskt om det finns λ < κ sådant att 2^{λ} ≥ κ, ty då gäller λ ∈ H(κ) men P(λ) ∉ H(κ). □

4Se Appendix A sidan 21.

Appendix A. Första ordningens predikatlogik

Syftet med detta appendix är att befästa notation och fungera som referens.

Definition. Alfabetet för predikatlogik består av följande symboler.

Predikatsymboler: P_{1}^{n}, P_{2}^{n}, P_{3}^{n}, …
Funktionssymboler: f_{1}^{n}, f_{2}^{n}, f_{3}^{n}, …
Individkonstanter: C_{1}, C_{2}, C_{3}, …
Individvariabler:  x_{1}, x_{2}, x_{3}, …
Konnektiver:  ∧, ∨, →, ↔, ¬, ⊥
Kvantorer:  ∀, ∃
Hjälpsymboler:  (,).

I definitionen ovan gäller att övre index (n≥0) indikerar ställighet och ‘… ’ skall tolkas som uppräkneligt många. I definitionerna som följer använder jag mig av konventionerna □ ∈ {∧, ∨, →, ↔} och Q ∈ {∀, ∃}.

Definition. Det predikatlogiska språket består av följande induktivt definierade objekt.

(i) Termer.
(a) Individkonstanter och individvariabler är termer.
(b) Om t_{1}, …, t_{k} är termer, så är f_{i}^{k}(t_{1}, …, t_{k}) en term.
(ii) Atomära formler
(a) ⊥ och P_{i}^{0} är atomära.
(b) Om t_{1}, …, t_{k} är termer, så är P_{i}^{k}(t_{1}, …, t_{k}) atomär.
(iii) Formler
(a) Atomära formler är formler.
(b) Om φ och ψ är formler, så är (¬φ), (φ□ψ) och ((Qx_{i})φ)

formler.

Om ((Qx_{i})φ) är en delformel till en formel, så är φ i området för kvantorn Q. Informellt säger vi att en variabel x_{i} är bunden om den förekommer inom området för en kvantor Q. Formellt definierar vi mängden av fria variabler:

Definition. Mängden av fria variabler F V (t) , i en term t, definieras rekursivt över uppbyggnaden av t.

\begin{aligned}(i) & F V (x_{i}) & = & \{x_{i}\} \\ (ii) & F V (C_{i}) & = & ∅ \\ (iii) & F V (f_{i}^{k}(t_{1}, …, t_{k})) & = & F V (t_{1}) ∪ … ∪ F V (t_{k}) \end{aligned}

Definition. F V utökas till formler genom

(i) F V (⊥)  = ∅
F V (P_{i}^{0})  = ∅
F V (P_{i}^{k}(t_{1}, …, t_{k})) = F V (t_{1}) ∪ … ∪ F V (t_{k})
(ii) F V (¬φ)  = F V (φ)
F V (φ□ψ)  = F V (φ) ∪ F V (ψ)
(iii) F V (Qx_{i}φ)  = F V (φ) \ {x_{i}}

På liknande sätt kan man formellt definiera mängden, BV, av bundna variabler.

Definition. En term, t, är sluten om F V (t) = ∅. Analogt gäller att en formel, φ, är sluten om F V (φ) = ∅. Slutna formler kallas för påståenden.

Definition. En tolkning 𝔄 för ett predikatlogiskt språk definieras av.

(i) En icke-tom mängd A (kallas domän för tolkningen 𝔄)
(ii) En funktion [[ ·]]_{𝔄} sådan att:
[[C_{i}]]_{𝔄} ∈ A, [[f_{i}^{k}]]_{𝔄} : A^{k} → A och [[P_{i}^{k}]]_{𝔄} ⊂ A^{k}

Observera att [[P_{i}^{0}]]_{𝔄} ⊂ A^{0} = A^{∅} = {∅} ger oss två möjligheter; antingen [[P_{i}^{0}]]_{𝔄} = ∅ eller [[P_{i}^{0}]]_{𝔄} = {∅} (falskt resp sant). Nollställiga predikat kan således ses som propositioner (sanningsvärden). På liknande sätt gäller att nollställiga funktionssymboler kan ses som en individkonstanter.

Definition. Vi utvidgar [[ ·]]_{𝔄} till slutna termer.

\begin{matrix}(i) & [[C_{i}]]_{𝔄} = C_{i} \\ (ii) & [[f_{i}^{k}(t_{1}, …, t_{k})]]_{𝔄} = [[f_{i}^{k}]]_{𝔄}([[t_{1}]]_{𝔄}, …, [[t_{k}]]_{𝔄}) \end{matrix}

Utöka nu språket genom att till varje element a ∈ A introducera en individkonstant ā och utvidga [[ · ]]_{𝔄} genom [[ā]]_{𝔄} = a. Låt S och F stå för sant respektiv falskt.

Definition. Vi associerar till varje påstående φ ett sanningsvärde [[φ]]_{𝔄}.

(i)

[[⊥]]_{𝔄}  = F
[[P_{i}^{k}(t_{1}, …, t_{k})]]_{𝔄} = \{ \begin{matrix}S & om ([[t_{1}]]_{𝔄}, …, [[t_{k}]]_{𝔄}) ∈ [[P_{i}^{k}]]_{𝔄} \\ F & annars \end{matrix}

(ii)

(a) φ är ¬ψ
[[¬ψ]]_{𝔄}  = \{ \begin{matrix}S & om [[ψ]]_{𝔄} = F \\ F & annars \end{matrix}
(b) φ är ψ ∨ σ
[[ψ ∨ σ]]_{𝔄}  = \{ \begin{matrix}S & om [[ψ]]_{𝔄} = S eller [[σ]]_{𝔄} = S \\ F & annars \end{matrix}
(c) φ är ψ ∧ σ
[[ψ ∧ σ]]_{𝔄}  = \{ \begin{matrix}S & om [[ψ]]_{𝔄} = S och [[σ]]_{𝔄} = S \\ F & annars \end{matrix}
(d) φ är ψ → σ
[[ψ → σ]]_{𝔄} = \{ \begin{matrix}F & om [[ψ]]_{𝔄} = S och [[σ]]_{𝔄} = F \\ S & annars \end{matrix}
(e) φ är ψ ↔ σ
[[ψ ↔ σ]]_{𝔄} = \{ \begin{matrix}S & om [[ψ]]_{𝔄} = [[σ]]_{𝔄} \\ F & annars \end{matrix}

(iii)

(a) φ är ∀xψ(x)
[[∀xψ(x)]]_{𝔄} = \{ \begin{matrix}S & om [[ψ(ā)]]_{𝔄} = S för alla a ∈ A \\ F & annars \end{matrix}
(b) φ är ∃xψ(x)
[[∃xψ(x)]]_{𝔄} = \{ \begin{matrix}S & om [[ψ(ā)]]_{𝔄} = S för något a ∈ A \\ F & annars \end{matrix}

Låt φ vara ett påstående och 𝔄 en tolkning för språket som φ är formulerad i. ⊧_{𝔄} φ betyder att φ är sann i 𝔄, dvs [[φ]]_{𝔄} = S, och vi säger att 𝔄 är en modell till φ. Låt Γ vara en mängd av påståenden. En modell till Γ är en tolkning i vilken alla formler i Γ är sanna. Då φ är sann i alla modeller till Γ skriver vi Γ ⊧ φ. Om φ är sann i alla tolkningar, säger vi att φ är en predikatlogisk sanning, och skriver ⊧ φ. Relationen Γ ⊢ φ definieras av: Det finns en härledning med alla antaganden i Γ och med slutsats φ. Här måste vi egentligen specifiera vad vi menar med härledning; detta kommer jag dock inte att göra, utan litar till läsarens intuition. Vanligt är att definiera härledbar som härledbar med naturlig deduktion. Se tex Dalen [3, s 30]. Om Γ = ∅ skriver vi ⊢ φ och säger att φ är en sats. En fundamental egenskap hos ⊢ relationen är att varje Γ sådan att Γ ⊢ φ innehåller en ändlig delmängd Δ sådan att även Δ ⊢ φ. Vi säger att Γ är konsistent, och skriver Con(Γ), om Γ ⊬ ⊥.

Definition. En teori T är en mängd påståenden med egenskapen T ⊢ φ ⇒ φ ∈ T, dvs T är sluten under härledbarhet. En mängd Γ sådan att T = {φ : Γ ⊢ φ} kallas en axiommängd till teorin T.

Definition. Låt T och T′ vara teorier i språken L resp. L′. Vi säger att T′ är en utvidgning av T om T ⊂ T′ och att T′ är en konservativ utvidgning av T om varje sats i T′ i språket L också är en sats i T.

Definition. En teori med axiom Γ i det predikatlogiska språket L kallas fullständig om Γ ⊢ φ eller Γ ⊢ ¬φ för varje påstående φ i L.

Sundhetssatsen. Om Γ ⊢ φ så Γ ⊧ φ.

Fullständighetssatsen. Γ ⊢ φ om och endast om Γ ⊧ φ.

Kompakthetssatsen. Om varje ändlig delmängd Δ till Γ har en modell, så har Γ en modell.

Sats A.1. Γ är konsistent om och endast om Γ har en modell.

För bevis av ovanstående satser refererar jag till Dalen [3, s 94, 105, 113, 108].

Källförteckning

[1] J. L. Bell. Boolean-Valued Models and Independence Proofs in Set Theory. Oxford logic guides: 12. Clarendon press Oxford, second edition, 1985.

[2] Christian Bennet. Något litet om mängder. Filosofiska institutionen, Göteborgs Universitet, 1996.

[3] Dirk van Dalen. Logic and Structure. North-Holland Pubishing Company, third edition, 1997.

[4] Frank R. Drake. Set Theory: An Introduction to Large Cardinals. Studies in Logic and the Foundations of Mathematics, vol 76. North-Holland Pubishing Company, 1974.

[5] Paul R. Halmos. Naive Set Theory. D. van Nostrand Company Inc, 1996.

[6] Abraham A. Fraenkel. Abstract Set Theory. North-Holland Pubishing Company, second edition, 1974.

[7] Thomas Jech. Multiple Forcing. Cambridge Tracts in Mathematics 88. Cambridge University Press, 1986.

[8] Ronald Jensen. Inner Models and Large Cardinals. The Buletin of Symbolic Logic, Volume 1, Number 4, Dec. 1995.

[9] P. T. Johnstone. Notes on Logic and Set Theory. Cambridge University Press, 1987.

[10] Jean-Louise Krivine. Introduction to Axiomatic Set Theory, D. Reidel Pubishing Company, 1971.

[11] Kenneth Kunen. Set theory: An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics, vol 102. North-Holland Pubishing Company, 1980.

[12] J. R. Shoenfield. Axioms of Set Theory, Studies in Logic and the Foundations of Mathematics, vol 90, Handbook of Mathematical Logic. North-Holland Pubishing Company, 1977.

[13] Ernst Zermelo. Über Grenzzahlen und Mengenbereiche, Fundamenta Mathematicae, vol 16, s29-47, 1930.