Partiellt ordnad mängd

Från Wikipedia
Hoppa till: navigering, sök
Hassediagramet över potensmängden av {x,y,z} med delmängd () som ordningsrelation. Här är exempelvis {x} och {y,z} inte jämförbara.

En partiellt ordnad mängd eller partialordnad mängd, ibland förkortat pomängd, är inom matematiken en mängd utrustad med en speciell binär relation, en så kallad partiell ordning eller partialordning.

En partiell ordning beskriver hur element i en mängd är ordnade, vilka element som kommer "före" eller "efter" andra element. Till skillnad från en totalt ordnad mängd kan element i en partiellt ordnad mängd vara ojämförbara, det kan finnas par av element där det ena elementet varken kommer före eller efter eller är lika med det andra elementet. Partiellt ordnade ändliga mängder kan visualiseras med hjälp av Hassediagram.

Definition[redigera | redigera wikitext]

En partiellt ordnad mängd är en mängd X med en relation som har följande egenskaper:

  • Reflexivitet:
  • Antisymmetri: och medför
  • Transitivitet: och medför .

Exempel[redigera | redigera wikitext]

Hassediagram av alla positiva delare till 12.
  • De reella talen är partiellt ordnade av relationerna (mindre än eller lika med) och (större än eller lika med).
  • De naturliga talen är partiellt ordnade av delbarhet.
  • Om M är en mängd är potensmängden av M, partiellt ordnad av delmängdsrelationen .
  • Om G är en grupp och är mängden av alla delgrupper till G är partiellt ordnad genom att för i om är en delgrupp till .
  • Om X är en mängd, P en partiellt ordnad mängd med partialordningen , så är funktionsrummet bestående av alla funktioner från X till P partiellt ordnade genom att om och endast om för alla x i X.

Största och minsta element[redigera | redigera wikitext]

Reguljära tal upp till 400, partiellt ordnade med delbarhet. Det finns flertalet maximala element, men inget största element. Dock finns ett minsta element, 1, som delar alla andra element.

Om X är partiellt ordnad av den partiella ordningen så sägs vara ett största element om för alla x i X. Likaså är a ett minsta element om för alla x.

Ett maximalt element i X är ett element så att medför . a är ett minimalt element om medför .

Skillnaden mellan största element och maximala element är att ett största element alltid är ett maximalt element, men det omvända gäller i allmänhet inte. Ett största element är större än alla andra element, och måste därför vara jämförbar med alla andra element. Ett maximalt element är större än alla element det är jämförbart med. En partiellt ordnad mängd kan innehålla maximalt ett största och ett minsta element.

Cartesiska produkter[redigera | redigera wikitext]

Om är en partiellt ordnad mängd kan man införa flera partialordningar på den cartesiska produkten:

  • Lexikografisk ordning: om och endast om eller både och är uppfyllda.
  • Produktordning: om och endast om både och är uppfyllda.
  • om och endast om och eller och .

Isomorfier[redigera | redigera wikitext]

Låt och vara partiellt ordnade mängder. En ordningsisomorfi är en bijektiv funktion som uppfyller

Om det finns en ordningsisomorfi mellan X och Y säger man att mängderna är isomorfa, vilket vanligtvis skrivs .

Om är en partiellt ordnad mängd finns en mängd av delmängder till X, så att:

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]