Partialordnad mängd

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

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 element

Reguljära tal upp till 400, partiellt ordnade med delbarhet. Det finns flera 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.

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

  1. ^ Jongsma, sid 7.1-1
  2. ^ [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.

Media som används på denna webbplats

Divisors 12.svg
Författare/Upphovsman: Klaus Röder, Licens: CC BY-SA 3.0
SVG vector image made with "dot" from Graphviz.org. Shows the divisor relation on the lattice of the divisors of 12 as directed graph.
Hasse diagram of powerset of 3.svg
(c) I, KSmrq, CC BY-SA 3.0
Hasse diagram, powerset of {x,y,z} ordered by inclusion.
Regular divisibility lattice.svg
A Hasse diagram of divisibility relationships among regular numbers up to 400. As shown by the horizontal light red lines, the vertical position of each number is proportional to its logarithm. Inspired by similar diagrams in a paper by Kurenniemi [1].