Ordningsrelation

En ordningsrelation är en binär relation på en mängd som är reflexiv, antisymmetrisk och transitiv.

Motivering

Ordning är ett vanligt begrepp som vi använder även i vardagen. Mycket kan vi ordna på något sätt — ord i alfabetisk ordning, elever i skolan efter längd, varor efter pris. Allt detta beskrivs av en ordningsrelation, som vi vanligen betecknar med symbolen ≤. Närliggande symboler är: <, >, ≥. Deras betydelse är uppenbar.

Vad skulle vi förvänta oss av en sådan relation? Redan av symbolen är det klart att element som är lika står i ordningsrelationen — vi vill alltså definiera egenskaperna hos relationen mindre än eller lika med. En sådan relation borde vara reflexiv. Det måste gälla att a ≤ a.

Vad mer? Symmetri kommer säkert inte att gälla — om vi har en ordning efter pris och bilen är billigare än brödet, så är säkert inte brödet samtidigt billigare än bilen. Vad skulle vi i allmänhet förvänta oss om det hände att a ≤ b och samtidigt b ≤ a? Skulle det någonsin vara rimligt? Ja, om a = b gällde. Det enda fallet där ordningen på elementen i relationen inte spelar någon roll är när elementen är lika — ordningen är alltså antisymmetrisk.

Slutligen, om vi vet att bilen är dyrare än brödet och flygplanet är ännu dyrare än bilen, så förväntar vi oss att flygplanet säkert är dyrare än brödet. Det beskriver transitiviteten.

Partiell ordning

Det vi nyss definierade är i själva verket bara en partiell ordning, den är inte total. Varför är den inte total? Låt oss försöka definiera en ordning på mängder. Hur skulle vi kunna jämföra två mängder?

Vi säger att mängden A är mindre än eller lika med mängden B, om A ⊆ B, alltså om A är en delmängd av B. Det är rimligt, för om vi har A = {1, 2} och B = {1, 2, 3}, så kan vi säga att A är mindre — B innehåller samma element som A och dessutom talet tre. Det kommer alltså till exempel att gälla:

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

Problemet uppstår när vi vill jämföra de här mängderna: A = {a, b} och B = {a, c}. Vilken av dem är mindre eller större? Problemet är att båda mängderna visserligen innehåller elementet a, men det andra elementet är olika. Ingen av mängderna är en delmängd av den andra, så varken A ≤ B eller B ≤ A gäller. Sådana mängder är med vår ordning ojämförbara.

Därför definierar vi en totalt ordnad mängd, även kallad kedja, som en mängd där varje par av element är jämförbart. Sådana mängder är till exempel talmängderna med den vanliga ordningen. För varje par av reella tal a, b kan du avgöra om a ≤ b eller b ≤ a.

Exempel från vardagen

Ett exempel där det kan löna sig att inte jämföra är ordning efter snygghet, där relationen < skulle betyda ”att vara fulare”. Kanske borde vi hellre definiera det omvänt, > som ”att vara snyggare”, för att vara mer korrekta :-). Det är nog rimligt att jämföra två kvinnor med varandra, till exempel ”Elsa” < ”Alice” i betydelsen att Alice är snyggare än Elsa. Eller två män: ”William” < ”Hugo” i betydelsen att Hugo är snyggare än William.

Problemet är att vi nog knappast kan jämföra snyggheten hos en man och en kvinna. Är Alice eller Hugo snyggare? Är Elsa eller William fulare? Bäst att inte undersöka…

Om vi i det sista exemplet begränsar oss till bara kvinnor, så kan vi säga att vi har en totalt ordnad mängd, eftersom vi kan jämföra snyggheten hos alla kvinnor.

Minimalt och maximalt element, minsta och största element

Om vi har en ordnad mängd M, så kallar vi ett element min ∈ M minimalt, om det inte finns något x ∈ M sådant att x < min. Vi kan alltså inte hitta något element som är mindre än elementet min.

Ett element max ∈ M kallar vi maximalt, om det inte finns något x ∈ M sådant att x > max. Vi kan alltså inte hitta något element som är större.

De två föregående begreppen skiljer sig från begreppen minsta och största.

Ett element a ∈ M kallar vi minsta, om det för alla x ∈ M gäller att a ≤ x. Det minsta elementet a är alltså mindre än eller lika med alla andra element i mängden M.

Ett element b ∈ M kallar vi största, om det för alla x ∈ M gäller att b ≥ x. Det största elementet b är större än eller lika med alla andra element i mängden M.

Vad är skillnaden mellan det största elementet och ett maximalt element? Det kan finnas flera maximala element, eftersom mängden inte nödvändigtvis är totalt ordnad. Om vi går tillbaka till exemplet där vi jämför människor efter utseende, så kan vi säga att Alice är den snyggaste kvinnan och Hugo är den snyggaste mannen. Men de här två personerna kan vi inte jämföra med varandra, vi vet inte om Alice eller Hugo är snyggare.

Båda elementen är alltså maximala. Vi kan inte hitta någon person som är snyggare än Hugo — Hugo är snyggare än alla andra män, och med kvinnor kan vi inte jämföra honom. På samma sätt för Alice — hon är snyggare än alla kvinnor, och med män kan vi inte jämföra henne.

Men ingen av dem är störst, i den här meningen snyggast. För att Hugo skulle vara snyggast/störst skulle han behöva vara snyggare än alla personer, även alla kvinnor. Men vi har redan sagt att vi inte kan jämföra honom med kvinnor, så han kan inte vara den snyggaste människan, han är bara, med ordningsteorins terminologi, maximal.

Det är nog lätt att se att om en mängd har ett största element, så är det elementet samtidigt maximalt. Om elementet a är större än alla andra element i mängden (definitionen av största element), så hittar vi säkert inget element som är ännu större (definitionen av maximalt element).

Ett exempel på en mängd som har ett största och ett minsta element är det slutna intervallet [0, 1]. Om vi väljer samma intervall, men öppet, så skulle det varken ha något största eller något minsta element: ]0, 1[.

Om vi vill ha oändligt många minimala element, kan vi definiera ordningen R så här. Först definierar vi hjälpmängderna M_x. Mängderna får den här formen: för alla x i intervallet ]0, 1[ definierar vi mängden M_x = {y ∣ y = x + n}, där n är ett icke-negativt heltal. Då får vi till exempel sådana här 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å varje mängd M_x definierar vi den vanliga ordningen, som vi betecknar R_x. Till sist tar vi bara unionen av de här ordningarna: R = ∪ R_x. I den här ordningen kan vi alltså bara jämföra inom de ursprungliga kedjorna. Vi kan avgöra om 0,5 ≤ 2,5, men vi kan inte avgöra om 0,5 ≤ 2,7, eftersom de här talen inte låg i samma mängd M_x och deras förhållande därför inte är definierat.

I den här ordningsrelationen gäller att varje element i intervallet ]0, 1[ är ett minimalt element.

Hassediagram

Ordnade mängder kan vi rita med ett Hassediagram. Det är en graf där noderna representerar elementen i mängden och en kant mellan noderna (a, b) säger oss att a < b och samtidigt att det inte finns något c sådant att a < c < b. Mellan elementen a och b finns alltså inget annat element. Dessutom måste det gälla att noden a ligger lägre än noden b i grafen. Exempel på ett Hassediagram:

Det här Hassediagrammet visar den ordnade mängden {A, B, C, D, E, F}. Det gäller att: A < B, B < E, och förstås gäller också A < E, men mellan de här noderna finns ingen kant, eftersom det finns en nod B för vilken A < B < E. Elementen E och D är ojämförbara, eftersom ingen av dem ligger över eller under den andra.

Hassediagram ritas visserligen oftast så här snyggt uppställda, men det är inte absolut nödvändigt. Det föregående Hassediagrammet kan också se ut så här:

Ett annat exempel är mängden: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Det är de positiva delarna till talet 60. Ordningen efter delbarhet kan visas så här:

Ordning efter delbarhet betyder att (a, b) ∈ R om och endast om a delar b. Av diagrammet ser vi att varje tal har ovanför sig de tal som det delar. Till exempel finns talen 12, 30 och 60 ovanför talet 6. Ovanför talet 4 finns talen 12, 20 och 60. Osv. Däremot har talet 3 inte talet 10 ovanför sig, eftersom det inte delar det — obs, talet 10 ligger visuellt ovanför talet 3, men ingen linje leder ”nerifrån och upp” dit. Om vi från talet 3 bara rör oss uppåt, kan vi gå till talen 15 och 6 och från dem till talet 30. Till talet 10 skulle vi bara komma genom att gå ner, vilket vi inte får.