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 partially ordered set. 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 ${\displaystyle (A,\preceq )}$ er ei delvis ordna mengd og ≺ er den tilsvarande strenge delvise ordninga, så kan det ikkje finnast ein krins av element ${\displaystyle a_{1}\prec a_{2}\prec \ldots \prec a_{k}\prec a_{1}}$. Om ein slik krins hadde funnest, så hadde ${\displaystyle a_{1}\prec a_{k}}$ på grunn av transitivitet, men sidan ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (\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). ${\displaystyle (\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 ${\displaystyle {\mathcal {A}}}$, så er ${\displaystyle ({\mathcal {A}},\subseteq )}$ ei delvis ordna mengd: ein kan sjå dette ved liknande argument som i avsnittet ovanfor. Dersom ${\displaystyle {\mathcal {A}}}$ er lik potensmengda 2^A av ei grunnmengd A, så er ${\displaystyle ({\mathcal {A}},\subseteq )}$ ein spesiell type delvis ordna mengd som vert kalla boolsk algebra.

Vektorar ordna under punktvis storleik

Gjeve to n-dimensjonale vektorar ${\displaystyle 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 ${\displaystyle U\preceq V\Leftrightarrow \bigwedge _{i=1}^{n}u_{i}\leq v_{i}}$. For kvar ei mengd ${\displaystyle {\mathcal {V}}}$ av vektorar er då ${\displaystyle ({\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 ${\displaystyle 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 ${\displaystyle V=(v_{1},\ldots ,v_{n})}$, kan ein definere den følgjande mengda: ${\displaystyle 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 ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle (\{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. Combinatorics and Partially Ordered Sets. Johns Hopkins University Press, 2002.