Partialordnad mängd

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

En partialordning 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 partialordnad 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. Partialordnade ändliga mängder kan visualiseras med hjälp av Hassediagram.

Definitioner
Låt X vara en mängd. En partialordning på (eller av) X är en binär relation  på X som har följande egenskaper:
Reflexivitet: 
Antisymmetri:  och  medför 
Transitivitet:  och  medför .

En strikt partialordning eller sträng partialordning på X är en binär relation  på X med följande egenskaper:
Antireflexivitet:  medför a ≠ b.
Transitivitet:  och  medför .
Observera att en strikt partialordning formellt sett inte är en partialordning.

Om  är en partialordning på X, så är relationen  definierad genom
 om och endast om  men a ≠ b
en strikt partialordning på X. Omvänt kan man för en strikt partialordning  definiera en partialordning  genom
 om och endast om  eller a = b.

Den andra konstruktionen är i en uppenbar mening omvändningen till den första. Abstrakt sett definierar detta en bijektion mellan mängden av alla partialordningar på X och mängden av alla strikta partialordningar på X. Mer informellt uttryckt spelar det ingen roll om man börjar med en (vanlig) partialordning eller en strikt partialordning, därför att den ena på ett naturligt sätt bestäms av den andra.

Med en partialordnad mängd (eller partiellt ordnad mängd eller pomängd) avses i denna artikel ett par (X, ), där  är en partialordning på X. Det är dock helt ekvivalent att i stället definiera det som ett par (X, ), där  är en strikt partialordning på X. I båda fallen underförstår man att X tilldelas både en partialordning och en strikt partialordning, som bestämmer varandra på det sätt som beskrivits ovan.

Duala partialordningar
Om (X, ) är en partialordning på X, så är också (X, ) en partialordning, där  definieras av föreskriften
 om och endast om .
 och  är duala partialordningar på X. På samma sätt är  och  duala strikta partialordningar på X, där  är den strikta partialordning som motsvarar .

Exempel

De reella talen är partiellt ordnade av relationerna  (mindre än eller lika med) och  (större än eller lika med). De reella talen är också en fullständigt ordnad mängd
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

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

Ett största element i X är ett element  så att  medför . a är ett minsta element om  medför .

Skillnaden mellan största element och maximalt element är att ett största element alltid är ett maximalt element, men det omvända gäller ofta 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.

En majorant till en delmängd A av X är ett element  sådant att  för alla . x är en minorant om i stället . Den minsta majoranten kallas (om den existerar) supremum (betecknad sup A), och den största minoranten kallas infimum (inf A).

Alla element i X är både majoranter och minoranter till delmängden ∅ (den tomma mängden). Därför är sup ∅ detsamma som det minsta elementet i X, och inf ∅ detsamma som det största elementet i X (när dessa existerar). För varje ettdelmängd {x} av X är sup {x} = inf {x} = x. X är ett gitter, om även varje tvådelmängd {x,y} av X har både supremum och infimum.

Intervall
Om  är en partialordning på X, a och b är element i X, och  gäller, så är intervallet (eller det slutna intervallet) mellan a och b delmängden [a,b] = {x ∈ X : } av X. Om (X, ) = (R, ≤) så är alltså [a,b] ett slutet intervall i den vanliga mening detta ges i reell analys. Delmängden (a,b) = {x ∈ X : } är det öppna intervallet mellan a och b. Observera att det öppna intervallet kan vara den tomma mängden.

Täckningsrelationen
Om (X, ) är en partialordning på X, a och b är element i X, och , men (a,b) = ∅, så sägs a täckas av b, eller b täcka a. annorlunda uttryckt gäller att a täcks av b precis om [a,b] = {a,b}. Täckningsrelationen ligger till grund för den formella definitionen av Hassediagram.

Delpomängder
Om (X, ) är en partialordnad mängd och Y är en delmängd av X, så har Y en partialordning  som definieras naturligt genom att x  y om och endast om x och y tillhör Y och x  y. (Således är  restriktionen av  till Y.) Y är en kedja om  är en totalordning av Y, men en antikedja om  är den diskreta ordningen av Y.

Varje delmängd av en kedja är en kedja, och varje delmängd av en antikedja är en antikedja. Därför bildar mängden av alla ändliga kedjor i X ett abstrakt simpliciellt komplex, och mängden av alla antikedjor ett annat abstrakt simpliciellt komplex.

Cartesiska produkter
Om  är en partialordnad mängd kan man införa flera partialordningar på den cartesiska produkten X2 = X × X, bland annat följande.
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
Låt  och  vara partialordnade 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 pomängd finns en mängd av delmängder till X,  så att:

(Om man låter f(x) vara  för varje x ∈ X, så är f en ordningsisomorfi.) Med andra ord är varje pomängd isomorf med en delpomängd till ett booleskt gitter.

Se även
Ekvivalensrelation

Referenser

Noter

Källor

 Calvin Jongsma, 2016, Discrete Mathematics: Chapter 7, Posets, Lattices & Boolean Algebra.

Ordningsteori
Matematiska relationer