Zorns lemma

Zorns lemma kan användas för att visa att varje sammanhängande graf har ett uppspännande träd

Zorns lemma är inom mängdläran, en sats av fundamental betydelse. Lemmat används till exempel för att visa existens av maximalideal i ringar, baser i vektorrum samt i många andra fall när urvalsaxiomet behövs i ett existensbevis. Troligen är Zorns lemma den vanligaste formen av urvalsaxiomet i matematiska bevis.

För att kunna förstå Zorns lemma introduceras några begrepp som är av vikt även utanför denna artikel.

Definitioner

En partiellt ordnad mängd är ett par $(M,\leq )$ där

• $M$ är en icke-tom mängd;
• Symbolen $\leq$ betecknar en binär relation på $M$ med tre egenskaper:
  • (Reflexivitet) Varje element $a\in M$ uppfyller relationen $a\leq a$
  • (Antisymmetri) Om $a\leq b$ och $b\leq a$ så är $a=b.$
  • (Transitivitet) Om $a\leq b$ och $b\leq c$ så är $a\leq c.$

En totalt ordnad mängd är en partiellt ordnad mängd $(M,\leq )$ med egenskapen att om $x$ och $y$ är två element i mängden $M$ så är $x\leq y$ eller $y\leq x.$

Ett element $u\in M$ är en övre begränsning till en totalt ordnad delmängd $T$ av den partiellt ordnade mängden $(M,\leq )$ om varje element $x$ i mängden $M$ uppfyller relationen $x\leq u.$

Ett element $m\in M$ är ett maximal-element till mängden $M$ om det har egenskapen att närhelst $x$ är ett element i $M$ sådant att $m\leq x$, så är $x=m$.

Med dessa förberedelser gjorda kan vi formulera det centrala resultatet i denna artikel.

Zorns lemma

Låt $(M,\leq )$ vara en icke-tom partiellt ordnad mängd. Antag att varje totalt ordnad delmängd av $M$ har en övre begränsning. Då finns det minst ett maximal-element till mängden $M$.

Tillämpning: Existens av en Hamelbas i ett vektorrum

Varje vektorrum $X\neq \{0\}$ har en Hamelbas.

Bevis

Låt ${\mathcal {M}}$ vara en samling bestående av alla linjärt oberoende delmängder, $A_{i}$, till vektorrummet $X$. Mängden $A_{i}$ är alltså ett element i ${\mathcal {M}}$.

Eftersom $X\neq \{0\}$ så finns det ett element $x\neq 0$ i vektorrummet $X$. Detta element ger i sin tur upphov till en-punkts-mängden $\{x\}$, som är en linjärt oberoende delmängd: Det enda sättet på vilket ekvationen $\alpha x=0$ kan uppfyllas, är om det komplexa talet $\alpha =0.$ Detta visar att $\{x\}$ är ett element i samlingen ${\mathcal {M}}$, varför denna är en icke-tom mängd.

Paret $(M,\subseteq )$ är en partiellt ordnad mängd, där den binära relationen '$\subseteq$' betecknar mängd-inklusion: $A\subseteq B$ betyder att $A$ är en delmängd till mängden $B$.

Låt ${\mathcal {A}}=\{A_{i}\}_{i\in I}$ vara en godtycklig totalt ordnad delmängd av ${\mathcal {M}}$. Varje objekt $A_{i}$ är en linjärt oberoende delmängd av vektorrummet $X$. Unionen av dessa delmängder, $B=\cup _{i\in I}A_{i}$, är också en linjärt oberoende delmängd av $X$, varför $B\in {\mathcal {M}}$. Objektet $B$ är enligt konstruktion en övre begränsning till ${\mathcal {A}}$. Detta visar att varje total ordnad delmängd av ${\mathcal {M}}$ har en övre begränsning.

Zorns lemma låter oss då dra slutsatsen att samlingen ${\mathcal {M}}$ har minst ett maximal-element. Låt $H$ vara ett maximal-element till ${\mathcal {M}}$. Betraktad som ett element i samlingen ${\mathcal {M}}$, är $H$ en linjärt oberoende delmängd av vektorrummet $X$. Det är därför meningsfullt att studera det linjära spannet $span(H)$ av $H$.

Enligt definitionen av linjärt spann är $span(H)$ en delmängd av $X$. Vi skall visa att $X=span(H)$ genom att anta motsatsen. Vi antar alltså att det finns ett element $w\in X$ som inte är ett element i $span(H)$. Detta element ger upphov till den linjärt oberoende mängden $\{w\}$ som, tillsammans med $H$, ger den linjärt oberoende delmängden $\{w\}\cup H$ av vektorrummet $X$. Vi ser att $H\subseteq \{w\}\cup H$, varför vi måste dra slutsatsen att $H=\{w\}\cup H$ eftersom $H$ är ett maximal-element till den partiellt ordnade mängden $({\mathcal {M}},\subseteq )$. Detta innebär att $w\in H$, vilket motsäger antagandet att $w\notin H$.

Sammanfattningsvis har vi visat att det finns en linjärt oberoende delmängd $H\subseteq X$ som är sådan att $span(H)=X$, det vill säga: Mängden $H$ är en Hamelbas för vektorrummet $X$.

Tillämpning: Existens av en ortonormal bas i ett Hilbertrum

Varje Hilbertrum $X\neq \{0\}$ har en ortonormal bas.

Bevis

Låt ${\mathcal {M}}$ vara en samling bestående av alla ortonormala delmängder av Hilbertrummet $H$. Det finns ett element $x\neq 0$ i detta Hilbertrum, eftersom vi antar att $H\neq \{0\}$. Detta element ger upphov till den ortonormala mängden $\{y\}$, där elementet $y=\Vert x\Vert ^{-1}x$, vilket visar att samlingen ${\mathcal {M}}$ är icke-tom.

Paret $({\mathcal {M}},\subseteq )$ utgör en partiellt ordnad mängd, där symbolen $\subseteq$ betecknar mängd-inklusion.

Låt ${\mathcal {A}}=\{A_{i}\}_{i\in I}$ vara en godtycklig totalt ordnad delmängd av ${\mathcal {M}}$. Elementen i ${\mathcal {A}}$ utgörs av ortogonala delmängder till Hilbertrummet $H$. Unionen av dessa delmängder, $B=\cup _{i\in I}A_{i}$, är också en ortogonal delmängd av $H$. Eftersom varje mängd $A_{i}$ är en delmängd av $B$, det vill säga $A_{i}\subseteq B$, är $B$ en övre begränsning till samlingen ${\mathcal {A}}$, med avseende på den partiella ordningen '$\subseteq$'. Detta visar att varje totalt ordnad delmängd av ${\mathcal {M}}$ har en övre begränsning.

Zorns lemma låter oss dra slutsatsen att samlingen ${\mathcal {M}}$ har ett maximal-element, som vi betecknar med symbolen $F$. Detta maximal-element är en ortonormal delmängd av Hilbertrummet $H$. Om vi kan visa att $F$ även är en total delmängd av $H$, så är $F$ en ortonormal bas till Hilbertrummet.

Det slutna höljet ${\overline {span(F)}}$ av det linjära spannet $span(F)$ är en delmängd av $H$. Vi vill visa att $H={\overline {span(F)}}$. För att göra detta antar vi motsatsen och visar att detta leder till en motsägelse.

Vi antar därför att det finns ett element, $z\neq 0$, i Hilbertrummet $H$ som är sådant att $z\notin {\overline {span(F)}}$. Detta element är ortogonalt mot mängden F. Tillsammans bildar de den ortonormala mängden $F\cup \{e\}\in {\mathcal {M}}$, där elementet $e=\Vert z\Vert ^{-1}z$. Vi ser att $F\subseteq F\cup \{e\}$, vilket innebär att vi tvingas dra slutsatsen att $F=F\cup \{e\}$, eftersom $F$ är ett maximal-element till den partiellt ordnade mängden $({\mathcal {M}},\subseteq )$. Detta leder fram till motsägelsen: $z\in F$ och $z\notin F$.

Sammanfattningsvis har vi visat att varje Hilbertrum $H\neq \{0\}$ har en ortonormal bas.

Resultat ekvivalenta med Zorns lemma

• Zorns lemma är ekvivalent med Urvalsaxiomet: Låt E vara en mängd. Då finns det en funktion $f:2^{E}\longrightarrow E$ som avbildar varje delmängd $M\subseteq E$ på ett element $f(M)\in M$.

• Urvalsaxiomet är också ekvivalent med Tychonoffs teorem inom topologi: Låt $\{(X_{i},T_{i})\}_{i\in I}$ vara en familj av kompakta topologiska rum. Då är paret $(\prod _{i\in I}X_{i},\,\prod _{i\in I}T_{i})$ ett kompakt topologiskt rum, där $\prod _{i\in I}T_{i}$ betecknar

produkt-topologin på $\prod _{i\in I}X_{i}$.

• Zorns lemma är ekvivalent med Hausdorffs maximalitetsprincip: Låt $(X,\leq )$ vara en partiellt ordnad mängd. Då finns det en totalt ordnad mängd $(E,\leq )$ sådan att
  • $E\subseteq X$;
  • Om $M\subseteq X$ är sådan att $E\subset M$, så är $(M,\leq )$ inte en totalt ordnad mängd.

Ett annat sätt att uttrycka Hausdorffs maximalitetsprincip är: Varje partiellt ordnad mängd har en maximal totalt ordnad delmängd.

• Zorns lemma är ekvivalent med principen om väl-ordning: För varje icke-tom mängd X går det att konstruera en ordningsrelation $\leq$ på X, sådan att paret $(X,\leq )$ är en välordnad mängd.

Zorns lemma är en sats inom mängdläran. Lemmat används till exempel för att visa existens av maximalideal i ringar, baser i vektorrum samt i många andra fall när urvalsaxiomet behövs i ett existensbevis. Troligen är Zorns lemma den vanligaste formen av urvalsaxiomet i matematiska bevis.

Givet en icke-tom partiellt ordnad mängd M som är sådan att varje kedja har en övre gräns, så existerar ett maximalt element i M.

Zorns lemma visas med hjälp av urvalsaxiomet. Vidare kan urvalsaxiomet, givet mängdlärans övriga axiom, visas med hjälp av Zorns lemma. Därmed är Zorns lemma och urvalsaxiomet ekvivalenta givet axiomen i ZF.