Partialordnad mängd
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/250px-Hasse_diagram_of_powerset_of_3.svg.png)
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:[1]
- 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Divisors_12.svg/250px-Divisors_12.svg.png)
- 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Regular_divisibility_lattice.svg/300px-Regular_divisibility_lattice.svg.png)
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.[2]
Ett största element i X är ett element så att medför . a är ett minsta element om medför .[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 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
Referenser
Noter
- ^ Jongsma, sid 7.1-1
- ^ [a b c] Jongsma sid. 7.1-6
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.