Ordningsrelasjoner

En ordningsrelasjon er en binær relasjon på en mengde som er refleksiv, antisymmetrisk og transitiv.

Motivasjon

Ordning er et vanlig begrep som vi bruker også i hverdagen. Mange ting kan vi ordne på en eller annen måte — ord etter alfabetet, elever i en klasse etter høyde, varer etter pris. Alt dette beskrives av ordningsrelasjonen, som vi vanligvis skriver med symbolet ≤. Beslektede symboler er: <, >, ≥. Betydningen av dem er åpenbar.

Hva ville vi forvente av en slik relasjon? Allerede av symbolet er det klart at det i en ordningsrelasjon vil være elementer som er like — vi vil altså definere egenskapene til relasjonen mindre enn eller lik. En slik relasjon bør være refleksiv. Det må gjelde at a ≤ a.

Hva mer? Symmetri vil sikkert ikke gjelde — hvis vi har en ordning etter pris, og bilen er billigere enn brødet, så vil sikkert ikke brødet samtidig være billigere enn bilen. Hva ville vi generelt forvente hvis det skjedde at a ≤ b og samtidig b ≤ a? Ville det noen gang gi mening? Ja, hvis a = b. Det eneste tilfellet der rekkefølgen på elementene i relasjonen ikke spiller noen rolle, er når elementene er like — ordningen er altså antisymmetrisk.

Til slutt, hvis vi vet at bilen er dyrere enn brødet og flyet er enda dyrere enn bilen, forventer vi at flyet sikkert er dyrere enn brødet. Det beskriver transitivitet.

Partiell ordning

Det vi nettopp har definert, er i virkeligheten bare en partiell ordning, den er ikke total. Hvorfor er den ikke total? La oss prøve å definere en ordning på mengder. Hvordan kunne vi sammenligne to mengder?

Vi sier at mengden A er mindre enn eller lik mengden B hvis A ⊆ B, altså hvis A er en delmengde av B. Det gir mening, for hvis vi har A = {1, 2} og B = {1, 2, 3}, kunne vi si at A er mindre — B inneholder de samme elementene som A og dessuten tallet tre. Så for eksempel vil det gjelde:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Problemet er imidlertid når vi vil sammenligne disse mengdene: A = {a, b} og B = {a, c}. Hvilken av dem er mindre eller større? Problemet er at begge mengdene riktignok inneholder elementet a, men det andre elementet er alltid forskjellig. Ingen av mengdene er en delmengde av den andre, så verken A ≤ B eller B ≤ A gjelder. Slike mengder er usammenlignbare med ordningen vår.

Derfor definerer vi en totalt ordnet mengde eller også en kjede hvis hvert par av elementer i mengden er sammenlignbare. Slike mengder er for eksempel tallmengdene med den vanlige ordningen. For to vilkårlige reelle tall a, b kan du avgjøre om a ≤ b eller b ≤ a.

Eksempler fra hverdagen

Et eksempel på at det lønner seg å la være å sammenligne, kan være en ordning etter hvor pen man er, der relasjonen < skulle bety «å være styggere». Kanskje burde vi heller definere det omvendt, > som «å være penere», for å være mer korrekte :-). Det gir sikkert mening å sammenligne to kvinner, for eksempel «Ida» < «Nora» i betydningen at Nora er penere enn Ida. Eller to menn: «Per» < «Lukas» i betydningen at Lukas er penere enn Per.

Problemet er at vi neppe kan sammenligne hvor pen en mann og en kvinne er. Er Nora eller Lukas penest? Er Ida eller Per styggest? Best å la være å undersøke…

Hvis vi i det siste eksempelet for eksempel begrenser oss til kvinner, kan vi si at vi har en totalt ordnet mengde, fordi vi kan sammenligne alle kvinnene.

Minimalt og maksimalt element, minste og største element

Hvis vi har en ordnet mengde M, kaller vi et element min ∈ M minimalt hvis det ikke finnes noe x ∈ M slik at x < min. Vi kan altså ikke finne et element som er mindre enn elementet min.

Et element max ∈ M kaller vi maksimalt hvis det ikke finnes noe x ∈ M slik at x > max. Vi kan altså ikke finne et element som er større.

De to foregående begrepene er forskjellige fra begrepene minste og største.

Et element a ∈ M kaller vi minste element hvis det for alle x ∈ M gjelder at a ≤ x. Det minste elementet a er altså mindre enn eller lik alle andre elementer i mengden M.

Et element b ∈ M kaller vi største element hvis det for alle x ∈ M gjelder at b ≥ x. Det største elementet b er større enn eller lik alle andre elementer i mengden M.

Hva er forskjellen på et største element og et maksimalt element? Det kan finnes flere maksimale elementer, for mengden trenger ikke være totalt ordnet. Hvis vi går tilbake til eksempelet med å sammenligne mennesker ut fra utseende, kan vi si at Nora er den peneste kvinnen og Lukas den peneste mannen. Men disse to personene kan vi ikke lenger sammenligne med hverandre, vi vet ikke om Nora eller Lukas er penest.

Begge elementene er altså maksimale. Vi kan ikke finne en person som er penere enn Lukas — Lukas er penere enn alle andre menn, og med kvinnene kan vi ikke sammenligne ham. På samme måte for Nora — hun er penere enn alle kvinner, og med menn kan vi ikke sammenligne henne.

Men ingen av dem er størst, i denne betydningen penest. For for at Lukas skulle være penest/størst, måtte han være penere enn alle personer, også alle kvinner. Men vi har allerede sagt at vi ikke kan sammenligne ham med kvinnene, derfor kan han ikke være penest, han er bare, i ordningsteoriens terminologi, maksimal.

Det er sikkert lett å se at hvis en mengde har et største element, er dette elementet samtidig også maksimalt. Hvis elementet a er større enn alle andre elementer i mengden (definisjonen av største element), finner vi sikkert ikke et element som er enda større (definisjonen av maksimalt element).

Et eksempel på en mengde som har et største og et minste element, er for eksempel det lukkede intervallet [0, 1]. Hvis vi velger det samme intervallet, men åpent, ville det verken hatt et største eller et minste element: ⟨0, 1⟩.

Hvis vi ville ha uendelig mange minimale elementer, kunne vi definere ordningen R slik. Først definerer vi hjelpemengdene M_x. Mengdene får denne formen: for alle x fra intervallet ⟨0, 1⟩ definerer vi mengden M_x = {y | y = x + n}, der n er et ikke-negativt helt tall. Da får vi for eksempel slike mengder:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

På hver mengde M_x definerer vi den vanlige ordningen, som vi kaller R_x. Til slutt tar vi bare unionen av disse ordningene: R = ∪ R_x. I denne ordningen kan vi altså alltid bare sammenligne innenfor de opprinnelige kjedene. Vi kan finne ut om 0,5 ≤ 2,5, men vi kan ikke finne ut om 0,5 ≤ 2,7, for disse tallene lå ikke i samme mengde M_x, og derfor har vi ikke definert forholdet mellom dem.

I denne ordningsrelasjonen gjelder det da at hvert element fra intervallet ⟨0, 1⟩ er et minimalt element.

Hassediagrammer

Ordnede mengder kan vi tegne ved hjelp av et Hassediagram. Det er en graf der nodene representerer elementene i mengden, og en kant mellom nodene (a, b) forteller oss at a < b og samtidig at det ikke finnes noe c slik at a < c < b. Det finnes altså ikke noe annet element mellom elementene a og b. Samtidig må det gjelde at noden a ligger lavere enn noden b i grafen. Et eksempel på et Hassediagram:

Dette Hassediagrammet viser den ordnede mengden {A, B, C, D, E, F}. Det gjelder: A < B, B < E, og selvfølgelig gjelder også A < E, men det er ingen kant mellom disse nodene, for det finnes en node B som oppfyller A < B < E. Elementene E og D er usammenlignbare, for ingen av dem er over eller under den andre.

Selv om Hassediagrammer vanligvis tegnes så pent og ryddig, er det ikke strengt nødvendig. Det foregående Hassediagrammet kan også se slik ut:

Et annet eksempel kan være mengden: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Det er de naturlige divisorene i tallet 60. Ordningen etter delelighet kan vises slik:

Ordning etter delelighet betyr at (a, b) ∈ R hvis og bare hvis a deler b. Fra diagrammet kan vi se at hvert tall har over seg tallene som det deler. For eksempel er det over tallet 6 tallene 12, 30 og 60. Over tallet 4 er tallene 12, 20 og 60. Osv. Derimot har tallet 3 ikke tallet 10 over seg, for det deler det ikke — obs, tallet 10 ligger visuelt over tallet 3, men det går ingen linje «nedenfra og opp» til det. Hvis vi fra tallet 3 bare beveger oss oppover, kan vi gå til tallene 15 og 6 og fra dem til tallet 30. Til tallet 10 ville vi bare kommet ved å gå ned igjen, og det får vi ikke lov til.