Partiellt ordnad mängd

inom matematiken en mängd försedd med en särskild binär relation
(Omdirigerad från Partialordning)

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.

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

DefinitionRedigera

En partiellt ordnad mängd   är en mängd X med en relation   som har följande egenskaper:[1]

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

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 (maximum) i X är ett element   så att   medför  . a är ett minsta element (minimum) 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 supremum, den största minoranten kallas infimum.

Cartesiska produkterRedigera

Om   är en partiellt ordnad mängd kan man införa flera partialordningar på den cartesiska produkten:

  • 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 partiellt ordnade 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 partiellt ordnad mängd finns en mängd av delmängder till X,   så att:

 

Se ävenRedigera

ReferenserRedigera

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