Urvalsaxiomet

Förord

Den moderna matematiken "hänger ihop" på det sättet att man har samma logiska grundvalar för (nästan) all sorts matematik: Aritmetik, algebra, analys, topologi, grafteori, och så vidare. Man åstadkommer detta genom att definiera "alla" grundläggande begrepp och egenskaper med hjälp av termer från mängdläran. Därför kan resultat från ett område enkelt tillämpas på ett skenbart helt annat område.

Ett typiskt exempel är Cauchy-Schwarz olikhet från linjär algebra. Intuitivt sett säger den, att skalärprodukten av två vektorer aldrig kan vara mer än produkten av vektorernas längder (och aldrig mindre än minus denna produkt), eftersom skalärprodukten är denna produkt gånger kosinus av vinkeln mellan vektorerna, och eftersom ett kosinusvärde alltid håller sig mellan talen -1 och 1. Om man bara tänker på olikheten på det sättet, blir den rätt självklar, men också rätt ointressant. Nu är det inte riktigt så vi gör i modern linjär algebra. Vi definierar "vektorrum", "vektorer", "skalärprodukt" och "längder av vektorer" abstrakt i termer av mängder och operationer på dessa med vissa egenskaper; och sedan bevisar vi att Cauchy-Schwarz olikhet följer ur dessa egenskaper. Detta blir mycket mindre intuitivt; och många studenter som just har börjat med universitetskurser i linjär algebra har svårt att förstå vitsen med det. Vitsen är dock, att varje uppsättning mängder och mängdoperationer som upfyller de villkor vi valde som utgångspunkter för den linjära algebran också måste uppfylla slutsatserna. Mängden av alla kontinuerliga funktioner på det slutna intervallet från a till b för två reella tal (med a < b, och vanlig aritmetik för funktioner) uppfyller villkoren för ett vektorium, och integraler av produkter av sådana funktioner uppfyller villkoren för skalärprodukt. Alltså kan den "rent geometriska" olikheten tillämpas direkt, för att ge den "rent analytiska" olikheten

$\left(\int \limits _{a}^{b}f(x)g(x)\,dx\right)^{2}=\int \limits _{a}^{b}f(x)^{2}\,dx\;\int \limits _{a}^{b}g(x)^{2}\,dx\,.$

Utan mängdläran skulle det vara mycket svårt att se vad detta har med längder av vektorer och storleken på kosinus av mellanliggande vinkel att göra; men med mängdläran blir den analytiska olikheten en närmast trivial tillämpning av linjär algebra.

Detta gör att mängdläran är fundamental för den moderna matematiken, och att mängdlärans fundament i sin tur blir viktiga. Där stöter vi dock på vissa svårigheter. Det finns en hel del egenskaper för mängder som är enkla att förstå och ta till sig (och som de flesta lågstadiebarn begrep, under de åren mängdläran ingick i svensk grundskoleundervisning). Från dessa enkla egenskaper kan mycket av de mer komplicerade egenskaper vi ofta behöver tillämpa härledas. (Lågstadiebarnen hade dock nog svårare för härledningarna, i den mån de lärdes ut.) Mycket av detta sammanfattas formellt och koncist i Zermelo-Fraenkels axiomsystem (ZF) för mängdläran. Emellertid finns det vissa mycket användbara påståenden om mängder (och därför om de flesta matematikområdena), som man inte kan bevisa med hjälp av enbart (ZF). Urvalsaxiomet, välordningsprincipen och Zorns lemma är tre av dem. Dessa och en del andra utsagor kan alltså varken bevisas eller motbevisas med hjälp av "de enkla naturliga egenskaperna" för mängder. Däremot är dessa utsagor ekvivalenta med varandra. Det betyder, att om man lägger till ett av dem som ett axiom, en utgångspunkt, för teorin, så kan man med hjälp av detta och (ZF) bevisa att även övriga utsagor är sanna. På det viset får man en "rikare" teori, som brukar betecknas (ZFC). Det är emellertid helt möjligt att i stället anta att en av utsagorna inte gäller; och då gäller inte heller de övriga. Man får då en "annan sorts" matematik. Den blir på många sätt svårare att hantera än "den vanliga matematiken", men den har också en fördel. Urvalsaxiomet ("med familj") är en ren existensutsaga; den utsäger att exempelvis vissa typer av mängder eller funktioner måste existera, trots att det ibland inte går att konstruera några exempel på dem. Om man i ställer antar att dessa utsagor är falska, så får man kvar mycket mer "konstruerbara" objekt. Därför kan denna alternativa matematik vara bättre att ta till exempelvis i datoralgebrasystem, där man inte är lika intressererad av existens i största allmänhet, men mycket intresserad av att algoritmiskt kunna ta fram och räkna med objekten.

I denna skift tar vi upp de tre nämnda utsagorna, och tre till, och visar att de verkligen är ekvivalenta, givet den "vanliga enkla mängdläran". Vi visar däremot inte att de är logiskt oberoende av (ZF). Bevisen kräver inte mycket mer än mängdlära, men å andra sidan bitvis rätt mycket mängdlära. För att kunna följa med i resonemangen behöver du vara tillräckligt van vid mängder för att tycka att "delmängder av mängden av alla delmängder av mängden av alla delmängder av vilken som helst given mängd" inte är oöverstigligt konstiga. Du bör också ha en viss vana vid bevisföring, och inte minst bör du kunna följa ett motsägelsebevis.

Vi börjar dock med en snabb sammanfattning av de mängdbegrepp vi behöver. I stort sett är det samma begreppsapparat som den som ligger till grund för topologin, så om du har läst Topologi/Inledning, så kommer du att känna igen det mesta.

Du måste alltså veta vad man menar med mängder, element i mängder, delmängder, unioner och snitt (skärningar) av mängder, och komplementet i en mängd av en delmängd.

Konventioner och beteckningar i denna bok

Avslutningen av ett bevis markeras med symbolen ♦ .

Mängder:

Mängder kommer normalt att betecknas med versaler ("stora bokstäver").

För de vanliga talområdena följer vi de vanliga svenska konventionerna till innehållet, och Bourbakis typsnittskonventioner, så att

$\mathbf {N} =\{0,1,2,3,4,\ldots \}=$ mängden av naturliga tal,

$\mathbf {Z} =\{\ldots ,-3,-2,-1,0,1,2,3,4,\ldots \}=$ mängden av heltal,

$\mathbf {Q} =\{{\frac {a}{b}};a,b\in \mathbf {Z} {\text{ och }}b\neq 0\}=$ mängden av rationella tal,

$\mathbf {R} ={\mathopen {]}}-\infty ,\infty {\mathclose {[}}=$ mängden av reella tal, och

$\mathbf {C} =\{a+ib;a,b\in \mathbf {R} \}=$ mängden av komplexa tal,

Mängden av positiva heltal, alltså $\{1,2,3,4,\ldots \}$, betecknas Z₊. På liknande sätt är Q₊ respektive R₊ mängden av positiva rationella tal respektive positiva reella tal. (Observera att 0 inte ingår i någon av dessa mängder, eftersom 0 inte är ett positivt tal.) Mängden av de positiva heltalen till och med det naturliga talet n betecknas N_n. Med andra ord är

$\mathbf {N} _{n}=\{k\in \mathbf {N} ;1\leq k\leq n\}$,

för varje n ∈ N. Exempelvis är

$\mathbf {N} _{0}=\emptyset ,\ \mathbf {N} _{1}=\{1\},\ \mathbf {N} _{2}=\{1,2\}{\text{ och }}\mathbf {N} _{5}=\{1,2,3,4,5\}$.

Union och snitt eller skärning betecknas som vanligt $\cup$ respektive $\cap$, och den tomma mängden betecknas $\scriptstyle \emptyset$. Om $\scriptstyle {\mathcal {F}}$ är en mängd av mängder, så är

$\cup {\mathcal {F}}=\bigcup _{A\in {\mathcal {F}}}A{\text{ och }}\cap {\mathcal {F}}=\bigcap _{A\in {\mathcal {F}}}A\;.$

Skulle dessutom $\scriptstyle {\mathcal {F}}$ vara den tomma mängden $\scriptstyle \emptyset$, så är $\cup {\mathcal {F}}$ respektive $\cap {\mathcal {F}}$ en tom uniom respektive ett tomt snitt. Den tomma unionen är $\scriptstyle \emptyset$, eftersom detta är det neutrala elementet för nionsoperationen. Om en grundmängd X (se nedan) ges av sammanhanget, så är det tomma snittet denna grundmängd, så att vi då har

$\cup \emptyset =\emptyset {\text{ och }}\cap \emptyset =X\;;$

annars är det tomma snittet odefinierat.
Mängddifferens betecknas $\scriptstyle \setminus$ , så att

$A\setminus B=\{x\in A;x\notin B\}$.

$\scriptstyle A\subseteq B$ betyder att A är en delmängd till B, medan $\scriptstyle A\subset B$ betecknar att A är en äkta delmängd till B (så att då dessutom $\scriptstyle A\neq B$).

Komplementet i mängden B till delmängden A av B betecknas $\scriptstyle \complement _{B}A$. Ofta anger sammanhanget en "grundmängd", ofta betecknad X, exempelvis det topologiska eller metriska rum vi betraktar. I sådana fall studerar vi oftast bara delmängder av grundmängden, och talar om komplementet till A utan specifikation av övermängden. I rummet X är alltså

$\complement A=\complement _{X}A=X\setminus A$.

Funktioner

Vi påminner om att en funktion eller en avbildning f från en mängd A till en mängd B är en tillordning av ett element ur B för varje element i A. Att f är en funktion från A till B betecknas också

$f:A\longrightarrow B$.

Elementet som tillordnas ett x i A betecknas f(x), och kallas bilden av x (med avseende på f), eller värdet för f i x. A är definitionsmängden för f, och B är målmängden för f.

Värdemängden för f, alltså mängden

$f(A)=\{f(x);x\in A\}=\{y\in B:{\text{det finns minst ett }}x{\text{ i }}A,{\text{ sådant att }}y=f(x)\}$,

kommer oftast att kallas bilden av (mängden) A (med avseende på f). Allmännare låter vi bilden av en delmängd $\scriptstyle C\subseteq A$ vara

$f(C)=\{f(x);x\in C\}$.

Funktionsgrafen för en funktion f : A → B är mängden

$\mathrm {graf} (f)=\{(x,f(x)):x\in A\}.$

graf(f) är en delmängd av den kartesiska produkten A×B (se nedan).

Om f : A → B är en funktion, och C⊆A (det vill säga C är en delmängd av A) f : A → B, så är restriktionen av f till C funktionen g : C → B definierad av att g(x) = f(x) för varje x i C. Restriktionen kommer också att betecknas med f|_C. Dess funktionsgraf gras(g) = graf(f|_C) är en delmängd av graf(f).

Om mer precist C⊂A (det vill säga C är en äkta delmängd av A), så är g en äkta restriktion av f.

Indexerade familjer och mängdprodukter

Definition: Mängdprodukten eller den kartesiska produkten av två mängder A och B är

$A\times B=\{(a,b);a\in A{\text{ och }}b\in B\}\,.$

Här är (a,b) ett par (eller en tvåtuppel) av element, parets poster. Par är ordnade, vilket betyder att om a ≠ b, så är (a,b) ≠(b,a). På samma sätt är

$A\times B\times C=\{(a,b,c);a\in A{\text{ och }}b\in B{\text{ och }}c\in C\}$

(där (a,b,c) är en trippel eller tretuppel), och så vidare. Om mängderna är lika, så använder man även en potenslik beteckning:

$A^{2}=A\times A\,,$ $A^{3}=A\times A\times A\,,$

och så vidare.
Exempel: Mängderna R² och R³ av alla par respektive trippler av reella tal är välkända exempel på kartesiska produkter. Mängden

$\mathbf {Z} ^{5}=\mathbf {Z} \times \mathbf {Z} \times \mathbf {Z} \times \mathbf {Z} \times \mathbf {Z}$

innehåller bland annat femtupplerna (pentupplerna) (1, 5, -2, 7, 9) och (2061, -318, 0, 1, -987654321).

Det torde vara rätt uppenbart hur dessa definitioner generaliseras till kartesiska produkter av ett större ändligt antal mängder. För att generalisera även till kartesiska produkter med oändligt många faktorer, är några alternativa tolkningar till hjälp. En n-tuppel (x₁, x₂,..., x_n) ∈Aⁿ kan tolkas som en funktion f från mängden N_n = {1, 2, ,..., n} av "platser" till A, där x_i = f(i) för i = 1, 2, ..., n. Talet i i uttrycket x_i kallas för uttryckets index, och därför kallas mängden {1, 2, ,..., n} för n-tuppelns indexmängd. Eftersom index bestämmer platsen, behöver vi inte heller skriva ut posterna x₁, ... i ordning för att veta hur ntuppeln ser ut; det räcker att ange dessa poster med deras index, som en (N_n-indexerad) familj av element, (x_i)_i∈Nn.
Exempel: Familjen (i²+2i-5)_i∈N'4 är detsamma som kvadruppeln (fyrtuppeln) (-2, 3, 10, 19).
För enkelhets skull behandlade vi här bara n-tuppler, där alla posterna tillhör samma mängd; alltså elementen i någon kartesisk produkt Aⁿ. För att betrakta allmännare n-tuppler i allmännare kartesiska produkter behöver vi också betrakta N_n-indexerade familjer av mängder. Detta motiverar följande allmänna definitioner.

Definition: Låt I vara en (godtycklig) mängd. En I-indexerad familj (x_i)_i∈I är en tillordning av en post (ett element) x_i till varje element i i I. Om varje post är ett tal (respektive punkt eller mängd), så är familjen en talfamilj (respektive punktfamilj eller mängdfamilj).

Definition: Låt I vara en mängd, och (A_i)_i∈I en I-indexerad familj. Mängdprodukten eller den kartesiska produkten av denna familj är då

$\prod _{i\in I}A_{i}=\{(x_{i})_{i\in I}\;;\;x_{i}\in A_{i}{\text{ för alla }}i\in I\}=\{{\text{funktioner }}f\,:\,I\longrightarrow \bigcup _{i\in I}A_{i}\;;\;f(i)\in A_{i}{\text{ för alla }}i\in I\}.$

I specialfallet där alla A_i är lika med en given mängd A skriver man också mängdprodukten som A^I, en mängdpotens:

$A^{I}=\prod _{i\in I}A=\{(x_{i})_{i\in I}\;;\;x_{i}\in A{\text{ för alla }}i\in I\}=\{{\text{funktioner }}f\,:\,I\longrightarrow A\}.$

Slutligen är Aⁿ = A^N_n för varje mängd A och varje naturligt tal n.

Definition: En följd på en mängd A är en familj som antingen tillhör A^N eller A^Z₊. Om alla element i A exempelvis är tal eller punkter, så kan följden kallas en tal- respektive punktföljd.

Observation. för varje mängd A är den triviala mängdpotensen A⁰ = {()}, mängden med ett enda element (), nolltuppeln eller den tomma familjen. Detta är för oss en rätt ointressant mängdprodukt, som vi normalt kan bortse från.

Konvention: Om antingen indexet eller indexmängden för en familj F = (x_i)_i∈I framgår tydligt av sammanhanget, så kan vi utelämna det i den avslutande beskrivningen av index, och i stället skrivaF = (x_i)_I respektive F = (x_i)_i.

Konvention: Om f : A₁×...×A_n → M är en funktion på en mängdprodukt (av ändligt många mängder), och (x₁,...,x_n) är ett element i A₁×...×A_n, så borde vi formellt sett beteckna funktionsvärdet för detta element med f((x₁,...,x_n)). I stället utelämnar vi i sådana fall det ena parentesparet, och skriver f(x₁,...,x_n). Vi tänker då oss snarast f som en funktion av n olika variabler. Alternativt namnges elementet, och då ofta med samma bokstav i fetstil, som användes för att beteckna posterna. I exemplet skulle vi alltså skriva x = (x₁,...,x_n), och beteckna funktionsvärdet med f(x).

Urvalsaxiomet

Följande utsaga är en variant av urvalsaxiomet.
Axiom: En produkt av icketomma mängder är alltid icketom.
Detta kan inte bevisas i allmänhet utan hjälp av något likvärdigt antagande. För en ändlig indexmängd I och en familj (A_i)_i∈I av icketomma mängder räcker det att välja ut ett element x_i i A_i i taget; processen tar slut när vi har gått igenom alla element i I, och vi har då hittat en familj (x_i)_I i mängdprodukten. Om I är oändlig, så fungerar inte detta förfarande. Skulle vi försöka välja ut våra x_i ett och ett, blir vi aldrig färdiga. Urvalsaxiomet utsäger att det (åtminstone teoretiskt sett) går att välja ut ett x_i från varje A_i samtidigt. Detta är mycket långtifrån att vara självklart sant.