Partialordnad mängd

inom matematiken en mängd försedd med en särskild binär relation
(Omdirigerad från Partiellt ordnad 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.

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 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.

DefinitionerRedigera

Låt X vara en mängd. En partialordning på (eller av) X är en binär relation  X som har följande egenskaper:[1]

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

En strikt partialordning eller sträng partialordningX är en binär relation  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 partialordningarRedigera

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   är duala strikta partialordningar på X, där   är den strikta partialordning som motsvarar  .

ExempelRedigera

 
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 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 elementRedigera

 
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 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.

IntervallRedigera

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äckningsrelationenRedigera

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ängderRedigera

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 produkterRedigera

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  .

IsomorfierRedigera

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 ävenRedigera

ReferenserRedigera

NoterRedigera

  1. ^ Jongsma, sid 7.1-1
  2. ^ [a b c] Jongsma sid. 7.1-6

KällorRedigera