Ordningsrelation

En ordningsrelation er en binær relation på en mængde, som er refleksiv, antisymmetrisk og transitiv.

Motivation

Ordning er et almindeligt begreb, som vi også arbejder med i hverdagen. En masse ting kan vi ordne på en eller anden måde — ord efter alfabetet, elever i skolen efter højde, varer efter pris. Alt dette beskriver ordningsrelationen, som vi sædvanligvis skriver med symbolet ≤. Beslægtede symboler er: <, >, ≥. Deres betydning er indlysende.

Hvad ville vi forvente af en sådan relation? Allerede af symbolet er det klart, at der i en ordningsrelation vil være elementer, som er ens — det handler altså om at definere egenskaberne ved relationen mindre end eller lig med. En sådan relation burde altså være refleksiv. Der skal gælde, at a ≤ a.

Hvad ellers? Symmetri vil helt sikkert ikke gælde — hvis vi har en ordning efter pris, så hvis en bil er billigere end et brød, vil brødet helt sikkert ikke samtidig være billigere end bilen. Hvad ville vi generelt forvente, hvis det skete, at a ≤ b og samtidig b ≤ a? Ville det nogensinde give mening? Ja, hvis a = b gælder. Det eneste tilfælde, hvor rækkefølgen af de elementer, vi sætter ind i relationen, er ligegyldig, er, når elementerne er ens — ordningen er altså antisymmetrisk.

Endelig, hvis vi ved, at en bil er dyrere end et brød, og et fly er endnu dyrere end bilen, så forventer vi, at flyet helt sikkert er dyrere end brødet. Det beskriver transitivitet.

Partiel ordning

Det, vi lige har defineret, er i virkeligheden kun en partiel ordning, den er ikke total. Hvorfor er den ikke total? Lad os prøve at definere en ordning på mængder. På hvilken måde kunne vi sammenligne to mængder?

Vi siger, at mængden A er mindre end eller lig med mængden B, hvis A ⊆ B, altså hvis A er en delmængde af B. Det giver mening, for hvis vi har A = {1, 2} og B = {1, 2, 3}, kunne vi sige om A, at den er mindre — B indeholder de samme elementer som A og desuden tallet tre. Der vil altså for eksempel gælde:

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

Problemet er imidlertid, når vi vil sammenligne disse mængder: A = {a, b} og B = {a, c}. Hvilken af dem er mindre eller større? Problemet er, at begge mængder ganske vist indeholder elementet a, men det andet element er altid forskelligt. Ingen af mængderne er en delmængde af den anden, så hverken A ≤ B eller B ≤ A gælder. Sådanne mængder er med vores ordning ikke sammenlignelige.

Derfor definerer vi en totalt ordnet mængde eller en kæde, hvis ethvert par af elementer i mængden er sammenligneligt. Sådanne mængder er for eksempel talmængderne med den klassiske ordning. For to vilkårlige reelle tal a, b kan du afgøre, om a ≤ b eller b ≤ a.

Eksempler fra hverdagen

Et eksempel på, at det kan betale sig ikke at sammenligne, kunne være en ordning efter skønhed, hvor relationen < ville betyde »at være grimmere«. Måske skulle vi hellere definere det omvendt, > som »at være kønnere«, for at være mere korrekte :-). Det giver nok mening at sammenligne to kvinder indbyrdes, for eksempel »Ida« < »Freja« i betydningen, at Freja er kønnere end Ida. Eller to mænd: »Oscar« < »William« i betydningen, at William er kønnere end Oscar.

Problemet er, at vi nok vanskeligt kan sammenligne skønheden hos en mand og en kvinde. Er Freja eller William kønnest? Er Ida eller Noah grimmest? Lad os hellere lade være med at undersøge det…

Hvis vi i det sidste eksempel begrænser os for eksempel kun til kvinder, kan vi sige, at vi har en totalt ordnet mængde, fordi vi kan sammenligne skønheden hos alle kvinder.

Minimalt og maksimalt element, mindste og største element

Hvis vi har en ordnet mængde M, så kalder vi elementet min ∈ M minimalt, hvis der ikke findes noget x ∈ M, så x < min. Vi kan altså ikke finde et element, som er mindre end elementet min.

Elementet max ∈ M kalder vi maksimalt, hvis der ikke findes noget x ∈ M, så x > max. Vi kan altså ikke finde et element, som er større.

De to foregående begreber er forskellige fra begreberne mindste og største.

Elementet a ∈ M kalder vi mindste, hvis det for alle x ∈ M gælder, at a ≤ x. Det mindste element a er altså mindre end eller lig med alle de andre elementer i mængden M.

Elementet b ∈ M kalder vi største, hvis det for alle x ∈ M gælder, at b ≥ x. Det største element b er større end eller lig med alle de andre elementer i mængden M.

Hvad er forskellen mellem et største element og et maksimalt element? Der kan være flere maksimale elementer, fordi mængden ikke nødvendigvis er totalt ordnet. Hvis vi vender tilbage til eksemplet med at sammenligne mennesker ud fra udseende, så kan vi sige, at Freja er den kønneste kvinde, og William er den kønneste mand. Men disse to personer kan vi ikke længere sammenligne indbyrdes, vi ved ikke, om Freja eller William er kønnest.

Begge elementer er altså maksimale. Vi kan ikke finde en person, som er kønnere end William — William er kønnere end alle de andre mænd, og med kvinderne kan vi ikke sammenligne ham. På samme måde for Freja — hun er kønnere end alle kvinder, og med mændene kan vi ikke sammenligne hende.

Men ingen af dem er den største, i denne betydning den kønneste. For for at William kunne være den kønneste/største, skulle han være kønnere end alle personer, også alle kvinder. Men vi har allerede sagt, at vi ikke kan sammenligne ham med kvinderne, derfor kan han ikke være det kønneste menneske, han er blot, i ordningsteoriens terminologi, maksimal.

Det er nok let at se, at hvis en mængde har et største element, så er dette element samtidig også maksimalt. Hvis elementet a er større end alle de andre elementer i mængden (definitionen af største element), så finder vi helt sikkert ikke et element, som er endnu større (definitionen af maksimalt element).

Et eksempel på en mængde, der har et største og et mindste element, er for eksempel det lukkede interval [0; 1]. Hvis vi vælger det samme interval, men åbent, ville det hverken have et største eller et mindste element: ]0; 1[.

Hvis vi ville have uendeligt mange minimale elementer, kunne vi definere ordningen R på denne måde. Først definerer vi hjælpemængderne M_x. Mængderne får denne form: for alle x fra intervallet ]0; 1[ definerer vi mængden M_x = {y ∣ y = x + n}, hvor n er et helt ikke-negativt tal. Derved får vi for eksempel sådanne mængder:

$$\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 mængde M_x definerer vi den klassiske ordning, som vi kalder R_x. Til sidst danner vi bare foreningsmængden af disse ordninger: R = ∪ R_x. I denne ordning kan vi altså altid kun sammenligne inden for de oprindelige kæder. Vi kan således finde ud af, om 0,5 ≤ 2,5, men vi kan ikke finde ud af, om 0,5 ≤ 2,7, fordi disse tal ikke lå i samme mængde M_x, og derfor har vi ikke defineret deres forhold.

I denne ordningsrelation gælder så, at hvert element fra intervallet ]0; 1[ er et minimalt element.

Hassediagrammer

Ordnede mængder kan vi tegne ved hjælp af et Hassediagram. Det er en graf, hvor knuderne repræsenterer mængdens elementer, og en kant mellem knuderne (a, b) fortæller os, at a < b, og at der samtidig ikke findes noget c, så a < c < b. Mellem elementerne a og b er der altså ikke noget andet element. Samtidig skal det gælde, at knuden a ligger lavere end knuden b i grafen. Eksempel på et Hassediagram:

Dette Hassediagram viser den ordnede mængde {A, B, C, D, E, F}. Der gælder: A < B, B < E, desuden gælder selvfølgelig A < E, men mellem disse knuder er der ingen kant, fordi der findes en knude B, for hvilken A < B < E gælder. Elementerne E og D er ikke sammenlignelige, fordi ingen af dem er over eller under den anden.

Selv om Hassediagrammer sædvanligvis tegnes så pænt opstillet, er det ikke ubetinget nødvendigt. Det foregående Hassediagram kan også se sådan ud:

Et andet eksempel kan være mængden: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Det er de naturlige divisorer i tallet 60. Ordningen efter delelighed kan vises således:

Ordning efter delelighed betyder, at (a, b) ∈ R netop når a går op i b. Af diagrammet kan vi se, at hvert tal har over sig de tal, som det går op i. For eksempel er over tallet 6 tallene 12, 30 og 60. Over tallet 4 er tallene 12, 20 og 60. Osv. Omvendt har tallet 3 ikke tallet 10 over sig, fordi det ikke går op i det — pas på, tallet 10 ligger visuelt over tallet 3, men der går ingen streg »nedefra og op« til det. Hvis vi fra tallet 3 kun bevæger os opad, kan vi gå til tallene 15 og 6 og fra dem til tallet 30. Til tallet 10 kunne vi kun komme ved at gå ned igen, hvilket vi ikke må.