Delvis ordning

I matematikken er ei **delvis ordning** av ei mengd *A* ein binær relasjon ≼ over *A* som generaliserer forholdet «≤», altså «mindre enn eller lik», mellom elementa i *A*. Relasjonen er kalla «delvis» ordna fordi ulikt t.d. ordninga ≤ av tala, har det lov til å finnast par *a*, *b* av element i mengda *A* som ikkje kan samanliknast ved ≼, altså at korkje *a* ≼ *b* eller *b* ≼ *a*. Om *A* har ei delvis ordning ≼, er paret (*A*, ≼) kjent som ei **delvis ordna mengd**, eller «poset», avkorta frå det engelske . Delvise ordningar er kjenneteikna som dei relasjonane som er refleksive, antisymmetriske og transitive.

## Definisjonar

Lat ≼ vere ein homogen, binær relasjon over ei mengd *A*. ≼ er ei *delvis ordning* av *A* dersom dei følgjande eigenskapane er sanne for alle element *a*, *b*, *c* i *A*:
* *a* ≼ *a* (≼ er *refleksiv*),
* viss *a* ≼ *b* og *b* ≼ *a*, så er *a* =*b* (≼ er *antisymmetrisk*),
* og viss *a* ≼ *b* og *b* ≼ *c*, så er *a* ≼ *c* (≼ er *transitiv*).

Om ≼ i tillegg er *total*, altså at for kvart par av element *a*, *b* så gjeld anten *a* ≼ *b* eller *b* ≼ *a*, så vert ≼ kalla ei *total ordning*. Dette er altså ei ordning der alle elementa kan sorterast i forhold til einannan, som t.d. heiltala under den vanlege ≤-ordninga. Det er verdt å merkje seg at under desse definisjonane er totale ordningar eit sertilfelle av delvise ordningar, og ikkje noko separat.

For kvar delvise ordning ≼, finst det òg ei *irrefleksiv* ordning som her vert notert ≺, som vert laga ved å fjerne paret (*a*, *a*) for kvart eit element *a* i *A*. Denne relasjonen vert kalla ei *streng delvis ordning* av *A*.

Ein ser greitt at delvise ordningar "oppfører" seg slik som ein ventar av storleikssamanlikning. Om (A, \preceq) er ei delvis ordna mengd og ≺ er den tilsvarande strenge delvise ordninga, så kan det ikkje finnast ein krins av element a_1\prec a_2\prec\ldots\prec a_k\prec a_1. Om ein slik krins hadde funnest, så hadde a_1\prec a_k på grunn av transitivitet, men sidan a_k\prec a_1, så går det mot at ≺ er antisymmetrisk, så ein slik krins kan ikkje finnast.

## Omgrep kring delvis ordna mengder

### Nærskylde element

Eit par {*a*, *b*} ∈ *A*  er *samanliknbare* ved (*A*, ≼) dersom det held at *a* ≼ *b* eller *b* ≼ *a*. I motsett fall er dei *usamanliknbare*.

Eit element *b* ∈ *A* *dekkjer over* eit anna element *a* ∈ *A* dersom *a* ≺ *b* og det ikkje finst noko anna element *c* slik at *a* ≺ *c* ≺ *b*.

### Hassediagram

Eit Hassediagram er ei teikning av ei delvis ordna mengd (*A*, ≼) som vert laga ved å skrive ned alle elementa i *A* på eit ark, og for kvart par (*a*, *b*) slik at *b* dekkjer over *a*, teiknar ein ein strek frå *b* ned mot *a*. Då må naturlegvis elementa plasserast slik at *b* står ovanfor *a*. Hassediagram er mykje brukte for å visualisere delvis ordna mengder.

Eit Hassediagram kan òg tenkjast på som ein retta graf der mengda av hjørne er gjeven av *A*, og det går ein retta kant frå *b* til *a* viss og berre viss *b* dekkjer over *a*.

### Største og minste element

Eit element *m* er kalla *maksimalt* i (*A*, ≼) dersom det gjeld for kvar ein *a* ∈ *A* at *a* ≼ *m*. Om *m* ≼ *a* for kvar ein *a* ∈ *A*, er *m* kalla *minimal* i (*A*, ≼). Viss mengda *A* er endeleg, så vil det alltid finnast minst eitt maksimalt og eitt minimalt element i (*A*, ≼). *m* er kalla det *minste* (forholdsvis *største*) elementet i (*A*, ≼) dersom *m* er det einaste minimale (forholdsvis maksimale) elementet i (*A*, ≼).

Gjeve ei delmengd *S* ⊆ *A*, så er eit element  *u* ∈ *A* kalla ein *øvre skranke* for *S* dersom det for kvart eit element *s* ∈ *S* held at *s* ≼ *u*. Om *u* ≼ *s* for kvar ein *s* ∈ *S* er *u* kalla ein *nedre skranke* for *S*. Om det finst ein øvre skranke  *u* som er mindre enn alle andre øvre skrankar, vert *u* kalla ein *minste øvre skranke*, og om *u* er ein nedre skranke som er større enn alle andre nedre skrankar, er *u* ein *største nedre skranke*. Ein nedre/øvre skranke for mengda *A* vil vere det minste/største elementet i *A*, og er dermed automatisk ein største nedre/minste øvre skranke. Ei delvis ordna mengd der kvar delmengd har ein største nedre og minste øvre skranke vert kalla eit gitter. Dette er ei viktig klasse av delvise ordningar.

### Funksjonar mellom delvise ordningar

For kvar ei delmengd *S* ⊆ *A*, kan ein definere ei avgrensing ≼*S* av ≼ slik: a\preceq_S b \Leftrightarrow \{a,b\}\subseteq S \wedge a\preceq b  
. (*S*, ≼*S*) er då ei delvis ordna mengd og vert kalla *delordninga* av (*A*, ≼) gjeven av *S*.

Gjeve to delvis ordna mengder (*A*, ≼*A*) og (*S*, ≼*S*), seier ein at (*S*, ≼*S*) kan ''innfellast'' i (*A*, ≼*A*) dersom det finst ein funksjon *f*: *S* → *A* slik at det for kvart eit par av element {s, t} ⊆ *S* held at s\preceq_S t \Leftrightarrow f(s)\preceq_A f(t). Ein slik funksjon *f* må naudsynt vere injektiv. Om det finst ei innfelling der funksjonen òg er surjektiv, seier ein at (*A*, ≼*A*) og (*S*, ≼*S*) er *isomorfe*. Det tyder at (*A*, ≼*A*) og (*S*, ≼*S*) er to «forkledde» variantar av kvarandre.

### Kjeder og antikjeder

Ei delmengd *S* av ei delvis ordna mengd (*A*, ≼) er kalla ei *kjede* dersom alle elementa i *S* er samanliknbare (altså at delordninga (*S*, ≼*S*) er ei total ordning). I motsett fall, om *ingen* av elementa i *S* er samanliknbare (altså at delordninga (*S*, ≼*S*) er ei tom ordning bortsett frå dei refleksive forholda), er *S* kalla ei *antikjede*. Storleiken på den største kjeda i (*A*, ≼) er kjend som *høgda* på (*A*, ≼), medan storleiken på den største antikjeda i (*A*, ≼) er kjend som *breidda* på (*A*, ≼).

Det er to velkjende teorem som relaterer storleikane på kjeder og antikjeder: Dilworths teorem og Mirskys teorem. Dilworths teorem seier at breidda på (*A*, ≼) er lik det minste talet på kjeder som (*A*, ≼) kan partisjonerast inn i, medan Mirskys teorem seier at høgda på (*A*, ≼) er lik det minste talet på antikjeder som (*A*, ≼) kan partisjonerast inn i.

## Døme

### Heiltal ordna under storleik

Eit døme som alt er teke opp er den totalt ordna mengda (\mathbb{N}, \leq), altså dei positive heiltala ordna under «mindre-enn-eller-lik»-relasjonen.

### Heiltal ordna under delbarheit

Det finst fleire måtar å ordne heiltala på. Gjeve to heiltal *a* og *b*, skriv ein *a* | *b* dersom *b* er deleleg på *a* (ein seier at *a* *deler* *b*). (\mathbb{N}, |) er då ei delvis ordna mengd: relasjonen | er refleksiv sidan kvart eit tal deler seg sjølv, han er antisymmetrisk sidan eit positivt heiltal ikkje kan dele eit positivt heiltal som er mindre enn seg sjølv, og han er transitiv, sidan viss *a* | *b*, så er *a* ein faktor av *b*. Så for tre tal *a*, *b*, *c*, der *a* | *b* og *b* | *c*, så er *a* ein faktor av ein faktor av *c*, så *c* må vere deleleg på *a*.

### Mengder ordna under delmengd

Gjeve ei mengd av mengder \mathcal{A}, så er (\mathcal{A}, \subseteq) ei delvis ordna mengd: ein kan sjå dette ved liknande argument som i avsnittet ovanfor. Dersom \mathcal{A} er lik potensmengda 2*A* av ei grunnmengd *A*, så er (\mathcal{A}, \subseteq) ein spesiell type delvis ordna mengd som vert kalla boolsk algebra.

### Vektorar ordna under punktvis storleik

Gjeve to *n*-dimensjonale vektorar U = (u_1,\ldots,u_n), V = (v_1,\ldots,v_n), så kan ein definere *U* ≼ *V* dersom kvart element av *U* er mindre enn eller lik det tilsvarande elementet i *V*. Med andre ord er U\preceq V \Leftrightarrow \bigwedge_{i=1}^n u_i \leq v_i. For kvar ei mengd \mathcal{V} av vektorar er då (\mathcal{V}, \preceq) ei delvis ordna mengd.

Eit praktisk døme her er tredimensjonale vektorar der kvart element er eit positivt reelt tal. Ein vektor V = (v_1,v_2,v_3) kan då sjåast på som dimensjonane (høgd, breidd, lengd) på ei kasse. For to kasser *U* og *V* gjeld då *U* ≼ *V* dersom kassa *U* kan setjast oppi kassa *V* utan å snuast på.

#### Binære vektorar

Eit eige tilfelle oppstår med *binære* vektorar, vektorar der kvart tal berre kan ha verdiane 0 eller 1. Ei delvis ordna mengd av binære vektorar er ekvivalent til ei mengd av mengder ordna under delmengd-relasjonen. Det kan ein sjå ved den følgjande operasjonen: Gjeve ein *n*-dimensjonal vektor V = (v_1,\ldots,v_n), kan ein definere den følgjande mengda: S_V = \{i: v_i = 1\}. *S**V* er altså ei delmengd av {1,…,n}, og for to vektorar *U* og *V* gjeld det at *U* ≼ *V* viss og berre viss S_U \subseteq S_V. Denne operasjonen kan òg snuast, så ein ser at kvar mengd av mengder ordna under delmengd er isomorf til ei mengd av binære vektorar ordna under punktvis storleik, og omvendt.

#### Dimensjon

Det er eit velkjent faktum at kvar ei endeleg ordna mengd (*A*, ≼) er isomorf til ei mengd av mengder ordna under delmengd. Dette kan ein sjå ved å definere den følgjande mengda for kvart element *a* ∈ *A*: S_a = \{x\in A: x\preceq a\}. Då er *a* ≼ *b* viss og berre viss *S**a* ⊆ *S**b*. I tillegg såg me ovanfor at mengda (\{S_a: a\in A\}, \subseteq) er isomorf til ei mengd av *n*-dimensjonale binære vektorar ordna under punktvis storleik, der *n* er lik storleiken på *A*. Men dette er ikkje nødvendigvis dei "stuttaste" vektorane ein kan setje (*A*, ≼) i eit ein-til-ein-forhold med. *Dimensjonen* åt ei delvis ordna mengd (*A*, ≼) er definert som det minste talet *k* slik at det finst ei mengd av *k*-dimensjonale vektorar som er isomorf med (*A*, ≼). *2-dimensjonen* åt (*A*, ≼) er definert likeins, der ein er ute etter dei stuttaste *binære* vektorane som er isomorfe med (*A*, ≼).

## Kjelder

* T. Britz og P. Cameron. Partially ordered sets.
* D.A. Simovicki og C. Djeraba. Chapter 4: Partially ordered sets. Frå *Mathematical Tools for Data Mining*. Springer, 2008. 
* W.T. Trotter. *[https://press.jhu.edu/books/title/1329/combinatorics-and-partially-ordered-sets Combinatorics and Partially Ordered Sets]*. Johns Hopkins University Press, 2002.