Partiellt ordnad mängd

Från Rilpedia

Hoppa till: navigering, sök

Texten från svenska Wikipedia

Hassediagramet över potensmängden av {x,y,z} med delmängd ( $\subseteq$ ) som ordningsrelation. Här är exempelvis {x} och {y,z} inte jämförbara.

En partiellt ordnad mängd, ibland förkortat pomängd, är inom matematiken en mängd utrustad med en speciell relation, en så kallad partiell ordning eller partialordning.

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

Definition

En partiellt ordnad mängd $(X, \preceq)$ är en mängd X med en relation $\preceq$ som har följande egenskaper:

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

Exempel

Hassediagaram av alla positiva delare till 12.

De reella talen är partiellt ordnade av relationerna $\leq$ (mindre än eller lika med) och $\geq$ (större än eller lika med).
De naturliga talen är partiellt ordnade av delbarhet.
Om M är en mängd är potensmängden av M, $\mathcal{P}(M)$ partiellt ordnad av delmängdsrelationen $\subseteq$ .
Om G är en grupp och $\mathcal{H}$ är mängden av alla delgrupper till G är $\mathcal{H}$ partiellt ordnade genom att $H_1 \preceq H_2$ för $H 1, H 2$ i $\mathcal{H}$ om $H 1$ är en delgrupp till $H 2$ .
Om X är en mängd, P en partiellt ordnad mängd med partialordningen $\preceq$ , så är funktionsrummet bestående av alla funktioner från X till P partiellt ordnade genom att $g \preceq f$ om och endast om $f(x) \preceq g(x)$ för alla x i X.

Största och minsta element

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 $\preceq$ så sägs $a \in X$ vara ett största element om $x \preceq a$ för alla x i X. Likaså är a ett minsta element om $a \preceq x$ för alla x.

Ett maximalt element i X är ett element $a \in X$ så att $a \preceq x$ medför $x = a$ . a är ett minimalt element om $x \preceq a$ medför $a = x$ .

Skillnaden mellan största element och maximala element är att ett största element alltid är ett maximalt element, men det omvända gäller i allmänhet 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.

Cartesiska produkter

Om $(X, \preceq)$ är en partiellt ordnad mängd kan man införa flera partialordningar på den cartesiska produkten:

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

Isomorfier

Låt $(X, \preceq_X)$ och $(Y, \preceq_Y)$ vara partiellt ordnade mängder. En ordningsisomorfi är en bijektiv funktion $f:X \to Y$ som uppfyller

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

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

$(X, \preceq) \cong (Y, \subseteq)$

Se även

Ekvivalensrelation

Referenser

Svensson, Per-Anders: Abstrakt algebra, Studentlitteratur, 2001. ISBN 91-44-01262-4.
Devlin, Keith: The Joy of Sets, Springer-Verlag, 1993. ISBN 3-540-94094-4.

Partiellt ordnad mängd

Från Rilpedia

Innehåll

Definition

Exempel

Största och minsta element

Cartesiska produkter

Isomorfier

Se även

Referenser

Visningar

Personliga verktyg

Sök

Navigering

Bibeln

Övrigt

Verktygslåda

På andra språk