Topologi/Inledning

Topologi kan intuitivt sett sägas handla om sådana egenskaper som inte ändras, när man töjer på eller trycker ihop geometriska figurer, utan att slita av eller sammanfoga delar. Exempelvis har ytan av en slät munk samma topologiska egenskaper som ytan av en temugg med ett öra; se bild 1 nedan! (Ett mer formellt sätt att säga samma sak på är att egenskaperna skall bevaras under kontinuerliga avbildningar med kontinuerliga inverser.) Det visar sig att för att analysera sådana egenskaper behöver man inte veta särskilt mycket om geometrin hos de inblandade mängderna; däremot måste man kunna avgöra exempelvis vilka delmängder som är öppna eller slutna. Detta gör det möjligt att ge en mycket enkel och avskalad definition av topologiska rum och kontinuerliga avbildningar. Det visade sig att denna abstraktare punktmängdstopologi också kunde tillämpas i många oväntade sammanhang. På det sättet blev topologin ett kraftfullt och allmänt verktyg för mycket av den moderna matematiken.

• 
  Ett klassiskt exempel på två ytor som har samma topologiska egenskaper.

Den abstraktare framställningen har dock också vissa konsekvenser för den som vill lära sig topologi.

• För det första används mängdläran på ett mycket grundläggande sätt. Om du vill förstå det som följer, så måste du 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. Du måste också känna till mängdbeteckningarna för de viktiga talområdena N, Z, Q och R. (De skrivs också ofta $\mathbb {N,\ Z,\ Q,\ R}$.) Känner du dig inte säker på detta, så bör du först repetera den elementära mängdläran, innan du återkommer till topologin.
• För det andra blir definitioner och generella utsagor i topologin väldigt abstrakta. Det lönar sig ofta att tänka efter vad de betyder i olika konkreta situationer. I denna bok ges ibland exempel på konkretiseringar; men det görs inte hela tiden. Läsaren uppmanas att själv tänka igenom vad olika begrepp och utsagor får för innebörd i olika konkretiseringar.

I denna inledning börjar vi med att redogöra för olika konventioner som används i hela detta verk; dels i allmänhet, dels avseende begrepp från den elementära mängdläran. Vi tar sedan kortfattat upp ett par områden, som närmast hör till den allmänna mängdläran, men som nog oftast inte tas med i grundläggande läromedel om denna.

I ett avsnitt behandlar vi familjer i allmänhet, och mängdfamiljer och kartesiska produkter i synnerhet. Detta generaliserar exempelvis hur punkter i planet eller rummet kan ges av koordinater. I det sista avsnittet tar vi i stället upp vissa slags tvåställiga relationer, som generaliserar kongruensrelationer respektive ordningsrelationer. Båda avsnitten ger mycket kortfattade genomgångar av respektive teori.

Avsnitten tar också upp tre viktiga verktyg för topologin, nämligen urvalsaxiomet, välordningsprincipen och Zorns lemma. Dessa hör till den mer avancerade mängdteorin, där det bland annat visas att de är ekvivalenta utsagor, men varken bevisbara eller motbevisbara med hjälp av de mer "intuitivt klara" grundreglerna för mängdläran. Det skulle föra för långt ifrån ämnet att gå in på dessa bevis här; och i stället får läsaren antingen acceptera dem alla tre som obevisade axiom, eller läsa mer om dem och deras ekvivalens och oberoende i någon annan källa (som wikipediaartiklarna Urvalsaxiomet, Välordningssatsen och Zorns lemma).

Konventioner och beteckningar i denna bok

I vissa fall ger vi exempel och tillämpningar där det är lämpligt med fördjupade kunskaper inom något delområde av matematiken, men som inte behövs för att följa texten i övrigt. Vi ger då dessa exempel i sammandragen form, där ämnesområdet anges. Det kan alltså stå exempelvis Exempel (algebraisk geometri) eller Tillämpning (komplex analys). De läsare som vill se exemplen eller tillämpningarna kan då klicka på ordet visa för att öppna dem; övriga kan hoppa över dem.

Avslutningen av ett bevis markeras med symbolen ♦ .
För åsättning av ett värde används ofta symbolen := i stället för =.
Enhetsintervallet, det slutna intervallet av reella tal mellan 0 och 1, alltså mängden {x∈R : 0 ≤ x ≤ 1} (oftast betecknad [0,1]), kommer att betecknas E.

Logikbeteckningar

Vi kommer att använda symbolerna ∧, ∨, ⇒ och ⇔ för (logiskt) "och", "eller", "implicerar" respektive "är ekvivalent med". ∀ ("allkvantifikatorn") och ∃ ("existenskvanitfikatorn") står för "För varje" ("För alla") respektive för "Det finns någon/något" ("Det existerar"). (För detaljer, se t. ex. Matematik/Diskret matematik/Logik med undersidor.)

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 ∪ respektive ∩, och den tomma mängden betecknas ∅. Två mängder A och B är disjunkta, om A ∩ B = ∅. 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 union respektive ett tomt snitt. Den tomma unionen är $\scriptstyle \emptyset$, eftersom detta är det neutrala elementet för unionsoperationen. 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 (vilken vi ofta betecknar D_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\}$.

f : A → B är injektiv, om olika element i A alltid har olika bilder, eller med andra ord om

$f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$.

f är surjektiv, om värdemängden är hela målmängden, alltså om

$f(A)=B$;

och f är inverterbar eller bijektiv om f är både injektiv och surjektiv. Om f är injektiv och f(x) = y, så är x urbilden av y (med avseende på f).

Om f : A → B är inverterbar, så betecknar vi som vanligt funktionsinversen till f med f^-1, så att

$f(x)=y\Leftrightarrow f^{-1}(y)=x{\text{ om }}x\in A{\text{ och }}y\in B$.

Oavsett om f är inverterbar eller inte kommer vi dock att använda beteckningen f^-1 på två andra sätt. Låt urbilden av en delmängd $\scriptstyle D\subseteq B$ vara

$f^{-1}(D)=\{x\in A;f(x)\in D\}$,

och låt urbildsmängden eller fibern till ett element y i B vara

$f^{-1}(y)=f^{-1}(\{y\})=\{x\in A;f(x)=y\}$.

Detta medför formellt sett ett litet problem: Om f är injektiv och f(x) = y, så kan f ^-1(y) beteckna antingen urbilden x eller urbildsmängden {x}. I praktiken kommer läsaren nog att lätt kunna se vilket som avses i ett visst sammanhang.

Om f : A $\longrightarrow$ B är en funktion, och C är en delmängd av A, så definieras restriktionen f|_C av f till C genom föreskriften f för varje x i C.

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∈N4 ä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).

Observation. Formellt sett "behövs" inte familjebegreppet, eftersom I-indexerade familjer formellt är detsamma som funktioner på I (alltså funktioner med I som definitionsmängd). I praktiken skulle det bli rätt ohanterligt att konsekvent använda funktionsterminologin. Det är oftast betydligt enklare att säga och tänka "punkten P = (1,3,-2) i R³" än "funktionen P: {1,2,3} → R given av att P(1) = 1, P(2) = 3 och P(3) = -2".

I resten av avsnittet kommer vi då och då att påminna om hur de införda begreppen kan tolkas i funktionstermer.

Observation. Vi utesluter här inte att I är den tomma mängden. () = (x_i)_i∈∅ är den tomma familjen eller nolltuppeln. Betraktad som funktion på dess indexmängd ∅ är den förstås den tomma funktionen, vars funktionsgraf är ∅. Den tomma familjen är "av varje typ": Eftersom den helt saknar poster, är det formellt sant att alla dess poster är tal samt punkter, samt mängder, samt har varje liknande annan egenskap.

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₊, eller tillhör A^I för någon annan oändlig delmängd I av N. Om alla element i A exempelvis är tal eller punkter, så kan följden kallas en tal- respektive punktföljd.

Kommentar. Allmännare indexmängder för följder förekommer främst i samband med delföljder.

Observation. För varje mängd A är den triviala mängdpotensen A⁰ = {()}, mängden med ett enda element (), nolltuppeln eller den tomma familjen. På samma sätt är den kartesiska produkten över den tomma familjen själv den tomma familjen. Detta kan tyckas vara en rätt ointressant mängdprodukt; men i situationer när vi betraktar delfamiljer kan den tjäna som utgångspunkt i någon form av induktion eller rekursion.

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 skriva F = (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).

Definition: Mängden av alla poster i familjen (x_i)_i∈I betecknas {x_i}_i∈I . Observera att detta är detsamma som värdemängden för den funktion på I som familjen formellt sett är.

Anmärkning. Ibland används {x_i}_i∈I  som alternativ beteckning på familjen (x_i)_i∈I. Vi följer i stället de vanliga skillnaderna mellan mängder och tuppler, alltså den att mängder inte är ordnade, och den att ett element bara kan räknas en gång i en mängd. (Mängden {1,4,3,1} innehåller ju bara tre element, nämligen talen 1, 3 och 4.)

Projektionsavbildningar

Definition: Låt X vara produkten av en familj (X_i)_I av mängder. För varje index i ∈ I definieras projektionen i i-led av X på X_i som funktionen

$\pi _{i}:X\longrightarrow X_{i}$,

given av att

$\pi _{i}({\bf {x}})=x_{i}$

för varje x = (x_i)_I ∈ X.

Exempel. Om P = (1,4,3,1) ∈ R⁴, så är π₂(P) = 4.

Kommentar rörande mängdlära:
Om X tolkas som en mängd av funktioner, så blir projektionen πi evalueringsfunktionen i elementet i för denna funktionsmängd.

Delfamiljer

• Inför delfamiljer, också som restriktioner av motsvarande grafer. Fastslå eventuellt noggrannare notationer för dessa funktioner, och motsvarande funktionsgrafer. I så fall kan "delfamilj" direkt kopplas till "delmängd av funktionsgrafen för hela familjen". Gör en genomgång av delföljder, och ändra ev. länken ovan om dessa till lämpligt {{mf}}-skapat ankare.

Familjer har delfamiljer, på samma sätt som mängder har delmängder. En delfamilj har med vissa (men oftast inte alla) av posterna i familjen.

Definitioner: En delfamilj av familjen x = (x_i)_i∈I (med avseende på J) är en familj x' = (x_i)_i∈J för någon delmängd J av indexmängden I. x' är en äkta delfamilj av x, om J är en äkta delmängd av I.

Exempel 1. R⁴-elementet P = (1,4,3,1) är ju en familj med indexmängden I = {1,2,3,4}, och J = {1,2,3} är en delmängd av I. Motsvarande delfamilj är Q = (1,4,3) ∈ R³. Observera att i detta fall de två familjerna har samma mängd av poster, nämligen {1,3,4}.

Definition: En (oändlig) delföljd av en följd är en delfamilj av följden, med avseende på en oändlig delindexmängd.

Kommentar rörande mängdlära:
När man tolkar en familj på indexmängden I som en funktion på I, blir delfamiljen med avseende på J ⊆ I helt enkelt restriktionen av denna funktion till J.

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 för ett index 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.

När familjen (x_i)_I tolkas som en funktion på I, brukar denna kallas en urvalsfunktion.

Relationer

Nedan går vi mycket kortfattat igenom de delar av teorin om relationer vi behöver i denna bok, eftersom de ännu ej gås igenom ordentligt i någon annan bok här.

Definition. En (tvåställig eller binär) relation R på en mängd A är ett "logiskt predikat", en "sanningsvärdesfunktion", på den kartesiska produkten A², alltså något som för varje par (a,b) ∈ A×A antingen är sant eller falskt. Med andra ord skall R(a,b) antingen gälla eller inte gälla för varje givet par (a,b) av element i A.

Exempel 1. Om R är likhetsrelationen på R, så gäller R(2,2), R(-3,-3) och R(π,π), men inte R(2,-3) eller R(π,3).

Exempel 2. Om R är mindreänrelationen på Q, så gäller R(1,3) och R(½,1), men inte R(3,1) eller R(2,2).

Exempel från aritmetik:
Exempel 3. Om R är kongruensmodulotrerelationen på Z, så gäller R(5,1) och R(-8,271), men inte R(-8,8) eller R(4,0). Exempel 4. Om R är delbarhetsrelationen på Z, så gäller R(3,0), R(4,4) och R(5,35), men inte R(0,3) eller R(78,13).

Det finns också andra typer av relationer, men i den här boken kommer vi inte att träffa på sådana. Eftersom alla våra relationer är tvåställiga, kan vi normalt använda den intuitivt klarare infixnotationen, där R(a,b) anges med en symbol mellan a och b, exempelvis a~b.

Om R är en relation på mängden A, och B är en delmängd på A, så är restriktionen R|_B×B en relation på B. Normalt använder vi samma infixsymbol för att beteckna den ursprungliga relationen och dess restriktion.

De relationer vi beaktar kommer att uppfylla något eller några av nedanstående villkor.
Definitioner: Om ~ är en relation på en mängd A, och a, b och c antas löpa över hela A, så sägs A vara

• reflexiv, om $a=b\Rightarrow a\sim b;$
• antireflexiv, om $a=b\Rightarrow a\not \sim b;$
• symmetrisk, om $a\sim b\Rightarrow b\sim a;$
• strikt antisymmetrisk, om $a\sim b\Rightarrow b\not \sim a;$
• transitiv, om $a\sim b\land b\sim c\Rightarrow a\sim c;$ respektive
• total, om $a\not \sim b\land a\neq b\Rightarrow b\sim a.$

Här står $a\not \sim b$ för att a~b inte gäller; och att en variabel sägs "löpa över" eller "genomlöpa" en viss mängd innebär att den antar alla värden i mängden, vilket här medför att det som sägs om den skall gälla för vilket värde i mängden som helst.

Relationerna i exemplen 1 och 3 ovan är reflexiva och symmetriska, den i exempel 2 är antireflexiv, strikt antisymmetrisk och total, den i exempel 4 är reflexiv och antisymmetrisk, och alla fyra relationerna är transitiva.

Ekvivalensrelationer och partitioner

Definition. En relation är en ekvivalensrelation, om den är reflexiv, symmetrisk och transitiv. (Relationerna i exemplen 1 och 3 ovan är ekvivalensrelationer.)

Definition. Om ~ är en ekvivalensrelation på en mängd A, och a ∈ A, så är ekvivalensklassen för a (med avseende på ~) delmängden

$[a]_{\sim }:=\{x\in A:a\sim x\}.$

Lemma. Om ~ är en ekvivalensrelation på en mängd A, och a och b löper över A, så gäller följande ekvivalenser:

$[a]_{\sim }=[b]_{\sim }\iff [a]_{\sim }\cap [b]_{\sim }\neq \emptyset \iff a\sim b.$

Bevis: Vi skall visa att

$[a]_{\sim }=[b]_{\sim }\Rightarrow [a]_{\sim }\cap [b]_{\sim }\neq \emptyset \Rightarrow a\sim b\Rightarrow [a]_{\sim }=[b]_{\sim }\,.$

Den första implikationen följer direkt av att varje ekvivalensklass är icketom, eftersom a ∈ [a]_~ på grund av reflexiviteten.

Om c ∈ [a]_~ ∩ [b]_~, så gäller

$a\sim c\land b\sim c$     (definitionsmässigt), och alltså

$a\sim c\land c\sim b$     (på grund av symmetrin), och alltså

$a\sim b\quad$       (på grund av transitiviteten).

Slutligen ger transitiviteten direkt att a~b ⇒ [b]_~ ⊆ [a]_~ , och eftersom symmetrin också ger a~b ⇒ b~a ⇒ [a]_~ ⊆ [b]_~ , så gäller också den tredje implikationen.♦

Detta lemma visar att varje element i A tillhör exakt en ekvivalensklass, så att A delas upp i ekvivalensklasser. Mer precist har vi:

Definition. En partition av en mängd X är en mängd av icketomma parvis disjunkta delmängder av X, vars union är hela X.

Sats. Ekvivalensrelationerna på en mängd A svarar bijektivt mot partitionerna av A, genom att varje ekvivalensrelation svarar mot partitionen bestående av mängden av motsvarande ekvivalensrelation, och att varje partition $\scriptstyle {\mathcal {P}}$ svarar mot ekvivalensrelationen

$\exists M\in {\mathcal {P}}:\{a,b\}\subseteq M.$♦

Exempel från aritmetik:

Ekvivalensklasserna för kongruensrelationen i exempel 3 kallas också restklasser eller kongruensklasser. Man anger ofta modulus, alltså det tal man räknar modulo, i stället för relationsbeteckningen som index för restklasserna. Eftersom modulus är 3 i exemplet, består partitionen av Z i detta fall av de tre restklasserna [0]3 = {..., -9, -6, -3, 0, 3, 6, 9, 12}, [1]3 = {..., -8, -5, -2, 1, 4, 7, 10, ...} och [2]3 = {..., -7, -4, -1, 2, 5, 8, 11, ...}. De tre aritmetiska operationerna addition, subtraktion och multiplikation "respekteras" av kongruensrelationen, vilket gör att Z-partitionen {[0]3, [1]3, [2]3} "ärver" dessa operationer från Z.

Ordningsrelationer

Definitioner. En relation är en partialordning om den är strikt antisymmetrisk och transitiv. En partialordning är en ordning eller totalordning om den dessutom är total. Oftast används < eller någon variant av detta tecken till infixnotation av partialordningen. Paret (P,<), där P är en mängd och < en partialordning på P, kallas en partialordnad mängd eller pomängd (efter engelskans poset).

Man inser lätt att en strikt antisymmetrisk relation också måste vara antireflexiv. (a~a skulle nämligen medföra sin egen motsats.) Mot varje partialordning < på P svarar därför entydigt en ostrikt associerad "mindreänellerlikamedrelation" ≤, definierad genom föreskriften

$a\leq b\iff a<b\lor a=b.$

Dessa "ostrikta partialordningar" kan också direkt karakteriseras som de binära relationer som är reflexiva, antisymmetriska och transitiva. Normalt inför man bara < eller ≤ explicit, och räknar med att läsaren "på köpet" förstår hur den associerade relationen är definierad. Vidare används a>b och a≥b som synonymer till b<a respektive b≤a; och även termer som "mindre än" och "större än eller lika med" används på det sätt vi är vana vid, när vi diskuterar partialordningar.

Definitioner. En delmängd K av en pomängd (P,<) (varmed förstås en delmängd av "den underliggande mängden") är en kedja, om restriktionen av < till K är en totalordning. En övre begränsning till en kedja K är ett p ∈ P, sådant att a≤p för varje a i K. Maximum för K är den unika övre begränsning för K som själv tillhör K, om det existerar någon sådan. Undre begränsningar och minima definieras analogt.

Ett element p i P är maximalt, om det inte är mindre än något annat element i P. En pomängd kan sakna eller ha ett eller flera maximala element, men om mängden är ordnad så har den högst ett maximalt element, som i så fall är dess maximum.

En välordning på en mängd P är en totalordning på P, sådan att varje icketom delmängd av P har ett minimum.

Följande två utsagor är ekvivalenta med urvalsaxiomet. (Man kan alltså bevisa dem som satser, om man antar att urvalsaxiomet gäller; men man kan också visa att de inte alltid gäller, om man antar att urvalsaxiomet inte gäller.) Eftersom vi i denna bok behandlar urvalsaxiomet som giltigt, gäller också dessa två utsagor:

Zorns lemma. Om varje kedja i en partialordnad mängd har en övre begränsning, så har mängden något maximalt element.

Välordningsprincipen. Varje mängd kan välordnas.

Observation. Vid ett första påseende kan man få intrycket att Zorns lemma inte skulle vara tillämpbart på tomma mängden, eftersom denna uppenbart saknar maximala element. Detta intryck vore dock felaktigt. Förutsättningen i Zorns lemma är nämligen i detta fall inte uppfyllda, eftersom ∅ själv är en kedja i ∅, men saknar övre begränsning där. Följdaktligen gäller även i detta fall implikationen, trots att slutsatsen inte gäller. (Se vid behov även sista raden i tabellen för implikation i Matematik/Diskret matematik/Logik/Satslogik#Sanningsvärden!)