Zorns lemma – Wikipedia

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

[redigera | redigera wikitext]

En partiellt ordnad mängd är ett par där

  • är en icke-tom mängd;
  • Symbolen betecknar en binär relation med tre egenskaper:
    • (Reflexivitet) Varje element uppfyller relationen
    • (Antisymmetri) Om och så är
    • (Transitivitet) Om och så är

En totalt ordnad mängd är en partiellt ordnad mängd med egenskapen att om och är två element i mängden så är eller

Ett element är en övre begränsning till en totalt ordnad delmängd av den partiellt ordnade mängden om varje element i mängden uppfyller relationen

Ett element är ett maximal-element till mängden om det har egenskapen att närhelst är ett element i sådant att , så är .

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

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

Tillämpning: Existens av en Hamelbas i ett vektorrum

[redigera | redigera wikitext]

Varje vektorrum har en Hamelbas.

Låt vara en samling bestående av alla linjärt oberoende delmängder, , till vektorrummet . Mängden är alltså ett element i .

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

Paret är en partiellt ordnad mängd, där den binära relationen '' betecknar mängd-inklusion: betyder att är en delmängd till mängden .

Låt vara en godtycklig totalt ordnad delmängd av . Varje objekt är en linjärt oberoende delmängd av vektorrummet . Unionen av dessa delmängder, , är också en linjärt oberoende delmängd av , varför . Objektet är enligt konstruktion en övre begränsning till . Detta visar att varje total ordnad delmängd av har en övre begränsning.

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

Enligt definitionen av linjärt spann är en delmängd av . Vi skall visa att genom att anta motsatsen. Vi antar alltså att det finns ett element som inte är ett element i . Detta element ger upphov till den linjärt oberoende mängden som, tillsammans med , ger den linjärt oberoende delmängden av vektorrummet . Vi ser att , varför vi måste dra slutsatsen att eftersom är ett maximal-element till den partiellt ordnade mängden . Detta innebär att , vilket motsäger antagandet att .

Sammanfattningsvis har vi visat att det finns en linjärt oberoende delmängd som är sådan att , det vill säga: Mängden är en Hamelbas för vektorrummet .

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

[redigera | redigera wikitext]

Varje Hilbertrum har en ortonormal bas.

Låt vara en samling bestående av alla ortonormala delmängder av Hilbertrummet . Det finns ett element i detta Hilbertrum, eftersom vi antar att . Detta element ger upphov till den ortonormala mängden , där elementet , vilket visar att samlingen är icke-tom.

Paret utgör en partiellt ordnad mängd, där symbolen betecknar mängd-inklusion.

Låt vara en godtycklig totalt ordnad delmängd av . Elementen i utgörs av ortogonala delmängder till Hilbertrummet . Unionen av dessa delmängder, , är också en ortogonal delmängd av . Eftersom varje mängd är en delmängd av , det vill säga , är en övre begränsning till samlingen , med avseende på den partiella ordningen ''. Detta visar att varje totalt ordnad delmängd av har en övre begränsning.

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

Det slutna höljet av det linjära spannet är en delmängd av . Vi vill visa att . 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, , i Hilbertrummet som är sådant att . Detta element är ortogonalt mot mängden F. Tillsammans bildar de den ortonormala mängden , där elementet . Vi ser att , vilket innebär att vi tvingas dra slutsatsen att , eftersom är ett maximal-element till den partiellt ordnade mängden . Detta leder fram till motsägelsen: och .

Sammanfattningsvis har vi visat att varje Hilbertrum har en ortonormal bas.

Resultat ekvivalenta med Zorns lemma

[redigera | redigera wikitext]
  • Zorns lemma är ekvivalent med Urvalsaxiomet: Låt E vara en mängd. Då finns det en funktion som avbildar varje delmängd på ett element .
  • Urvalsaxiomet är också ekvivalent med Tychonoffs teorem inom topologi: Låt vara en familj av kompakta topologiska rum. Då är paret ett kompakt topologiskt rum, där betecknar

produkt-topologin .

  • Zorns lemma är ekvivalent med Hausdorffs maximalitetsprincip: Låt vara en partiellt ordnad mängd. Då finns det en totalt ordnad mängd sådan att
    • ;
    • Om är sådan att , så är 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 på X, sådan att paret ä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.