Partialordnad mängd

(c) I, KSmrq, CC BY-SA 3.0

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 ${\displaystyle \preceq }$ på X som har följande egenskaper:^[1]

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

En strikt partialordning eller sträng partialordning på X är en binär relation ${\displaystyle \prec }$ på X med följande egenskaper:

• Antireflexivitet: ${\displaystyle a\prec b}$ medför a ≠ b.
• Transitivitet: ${\displaystyle a\prec b}$ och ${\displaystyle b\prec c}$ medför ${\displaystyle a\prec c}$.

Observera att en strikt partialordning formellt sett inte är en partialordning.

Om ${\displaystyle \preceq }$ är en partialordning på X, så är relationen ${\displaystyle \prec }$ definierad genom

${\displaystyle a\prec b}$ om och endast om ${\displaystyle a\preceq b}$ men a ≠ b

en strikt partialordning på X. Omvänt kan man för en strikt partialordning ${\displaystyle \prec }$ definiera en partialordning ${\displaystyle \preceq }$ genom

${\displaystyle a\preceq b}$ om och endast om ${\displaystyle a\prec b}$ 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, ${\displaystyle \preceq }$), där ${\displaystyle \preceq }$ är en partialordning på X. Det är dock helt ekvivalent att i stället definiera det som ett par (X, ${\displaystyle \prec }$), där ${\displaystyle \prec }$ ä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, ${\displaystyle \preceq }$) är en partialordning på X, så är också (X, ${\displaystyle \succeq }$) en partialordning, där ${\displaystyle \succeq }$ definieras av föreskriften

${\displaystyle a\succeq b}$ om och endast om ${\displaystyle b\preceq a}$.

${\displaystyle \preceq }$ och ${\displaystyle \succeq }$ är duala partialordningar på X. På samma sätt är ${\displaystyle \prec }$ och ${\displaystyle \succ }$ duala strikta partialordningar på X, där ${\displaystyle \succ }$ är den strikta partialordning som motsvarar ${\displaystyle \succeq }$.

Exempel

• De reella talen är partiellt ordnade av relationerna ${\displaystyle \leq }$ (mindre än eller lika med) och ${\displaystyle \geq }$ (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, ${\displaystyle {\mathcal {P}}(M)}$ partiellt ordnad av delmängdsrelationen ${\displaystyle \subseteq }$.
• Om G är en grupp och ${\displaystyle {\mathcal {H}}}$ är mängden av alla delgrupper till G är ${\displaystyle {\mathcal {H}}}$ partiellt ordnad genom att ${\displaystyle H_{1}\preceq H_{2}}$ för ${\displaystyle H_{1},H_{2}}$ i ${\displaystyle {\mathcal {H}}}$ om ${\displaystyle H_{1}}$ är en delgrupp till ${\displaystyle H_{2}}$.
• Om X är en mängd, P en partiellt ordnad mängd med partialordningen ${\displaystyle \preceq }$, så är funktionsrummet bestående av alla funktioner från X till P partiellt ordnade genom att ${\displaystyle g\preceq f}$ om och endast om ${\displaystyle f(x)\preceq g(x)}$ för alla x i X.

Största och minsta element

Om X är partiellt ordnad av den partiella ordningen ${\displaystyle \preceq }$ så sägs ${\displaystyle a\in X}$ vara ett maximalt element om ${\displaystyle x\preceq a}$ för alla x i X. Likaså är a ett minimalt element om ${\displaystyle a\preceq x}$ för alla x.^[2]

Ett största element i X är ett element ${\displaystyle a\in X}$ så att ${\displaystyle a\preceq x}$ medför ${\displaystyle x=a}$. a är ett minsta element om ${\displaystyle x\preceq a}$ medför ${\displaystyle a=x}$.^[2]

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.^[2]

En majorant till en delmängd A av X är ett element ${\displaystyle x\in X}$ sådant att ${\displaystyle x\preceq a}$ för alla ${\displaystyle a\in A}$. x är en minorant om i stället ${\displaystyle a\preceq x}$. 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 ${\displaystyle \preceq }$ är en partialordning på X, a och b är element i X, och ${\displaystyle a\preceq b}$ gäller, så är intervallet (eller det slutna intervallet) mellan a och b delmängden [a,b] = {x ∈ X : ${\displaystyle a\preceq x\preceq b}$} av X. Om (X, ${\displaystyle \preceq }$) = (R, ≤) så är alltså [a,b] ett slutet intervall i den vanliga mening detta ges i reell analys. Delmängden (a,b) = {x ∈ X : ${\displaystyle a\prec x\prec b}$} är det öppna intervallet mellan a och b. Observera att det öppna intervallet kan vara den tomma mängden.

Täckningsrelationen

Om (X, ${\displaystyle \preceq }$) är en partialordning på X, a och b är element i X, och ${\displaystyle a\prec b}$, 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, ${\displaystyle \preceq }$) är en partialordnad mängd och Y är en delmängd av X, så har Y en partialordning ${\displaystyle \preceq _{Y}}$ som definieras naturligt genom att x ${\displaystyle \preceq _{Y}}$ y om och endast om x och y tillhör Y och x ${\displaystyle \preceq }$ y. (Således är ${\displaystyle \preceq _{Y}}$ restriktionen av ${\displaystyle \preceq }$ till Y.) Y är en kedja om ${\displaystyle \preceq _{Y}}$ är en totalordning av Y, men en antikedja om ${\displaystyle \preceq _{Y}}$ ä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 ${\displaystyle (X,\preceq )}$ är en partialordnad mängd kan man införa flera partialordningar på den cartesiska produkten X² = X × X, bland annat följande.

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

Isomorfier

Låt ${\displaystyle (X,\preceq _{X}\prec )}$ och ${\displaystyle (Y,\preceq _{Y})}$ vara partialordnade mängder. En ordningsisomorfi är en bijektiv funktion ${\displaystyle f:X\to Y}$ som uppfyller

${\displaystyle 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 ${\displaystyle X\cong Y}$.

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

${\displaystyle (X,\preceq )\cong (Y,\subseteq )}$

(Om man låter f(x) vara ${\displaystyle \{y\in X:y\preceq x\}}$ 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

• Svensson, Per-Anders (2001). Abstrakt algebra. Studentlitteratur. ISBN 91-44-01262-4 
• Devlin, Keith (1993). The Joy of Sets. Springer-Verlag. ISBN 3-540-94094-4 
• Stanley, Richard (1997). Enumerative Combinatorics, Volume I. Cambridge University Press. ISBN 0-521-66351-2 
• Calvin Jongsma, 2016, Discrete Mathematics: Chapter 7, Posets, Lattices & Boolean Algebra.