Partiellt ordnad mängd

Från Wikipedia
Hoppa till: navigering, sök
Hassediagramet över potensmängden av {x,y,z} med delmängd (\subseteq) 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 (X, \preceq) är en mängd X med en relation \preceq som har följande egenskaper:

  • Reflexivitet: a \preceq a
  • Antisymmetri: a \preceq b och b \preceq a medför a = b\,
  • Transitivitet: a \preceq b och b \preceq c medför a \preceq c.

Exempel[redigera | redigera wikitext]

Hassediagram av alla positiva delare till 12.
  • De reella talen är partiellt ordnade av relationerna \leq (mindre än eller lika med) och \geq (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, \mathcal{P}(M) partiellt ordnad av delmängdsrelationen \subseteq.
  • Om G är en grupp och \mathcal{H} är mängden av alla delgrupper till G är \mathcal{H} partiellt ordnad genom att H_1 \preceq H_2 för H_1, H_2 i \mathcal{H} om H_1 är en delgrupp till H_2.
  • Om X är en mängd, P en partiellt ordnad mängd med partialordningen \preceq, så är funktionsrummet bestående av alla funktioner från X till P partiellt ordnade genom att g \preceq f om och endast om f(x) \preceq g(x) 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 \preceq så sägs a \in X vara ett största element om x \preceq a för alla x i X. Likaså är a ett minsta element om a \preceq x för alla x.

Ett maximalt element i X är ett element a \in X så att a \preceq x medför x = a. a är ett minimalt element om x \preceq a medför a = x.

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 (X, \preceq) är en partiellt ordnad mängd kan man införa flera partialordningar på den cartesiska produkten:

  • Lexikografisk ordning: (a,b)\preceq(c,d) om och endast om a \prec c eller både a = c\, och b \preceq d är uppfyllda.
  • Produktordning: (a,b)\preceq(c,d) om och endast om både a \preceq c och b \preceq d är uppfyllda.
  • (a,b)\preceq(c,d) om och endast om a \prec c och b \prec d eller a = c och b = d.

Isomorfier[redigera | redigera wikitext]

Låt (X, \preceq_X) och (Y, \preceq_Y) vara partiellt ordnade mängder. En ordningsisomorfi är en bijektiv funktion f:X \to Y som uppfyller

a \preceq_X b \Leftrightarrow f(a) \preceq_Y f(b).

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

Om (X, \preceq) är en partiellt ordnad mängd finns en mängd av delmängder till X, Y \subseteq \mathcal{P}(X) så att:

(X, \preceq) \cong (Y, \subseteq)

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]