Ordeningsrelatie

Een ordeningsrelatie is een binaire relatie op een verzameling die reflexief, antisymmetrisch en transitief is.

Motivatie

Ordenen is een gewoon begrip waarmee we ook in het dagelijks leven werken. Heel veel dingen kunnen we op een of andere manier ordenen — woorden alfabetisch, leerlingen in een klas op lengte, producten op prijs. Dit alles wordt beschreven door de ordeningsrelatie, die we meestal noteren met het symbool ≤. Verwante symbolen zijn: <, >, ≥. Hun betekenis is duidelijk.

Wat zouden we van zo'n relatie verwachten? Al uit het symbool is duidelijk dat in de ordeningsrelatie elementen zitten die gelijk zijn — het gaat ons dus om het definiëren van de eigenschappen van de relatie kleiner dan of gelijk aan. Zo'n relatie zou reflexief moeten zijn. Er moet gelden dat a ≤ a.

Wat nog meer? Symmetrie zal zeker niet gelden — als we ordenen op prijs en een auto is goedkoper dan een brood, dan is het brood zeker niet tegelijk goedkoper dan de auto. Wat zouden we in het algemeen verwachten als het zou gebeuren dat a ≤ b en tegelijk b ≤ a? Zou dat ooit zin hebben? Ja, als a = b zou gelden. Het enige geval waarin de volgorde van de elementen in de relatie er niet toe doet, is wanneer die elementen gelijk zijn — de ordening is dus antisymmetrisch.

Tot slot: als we weten dat een auto duurder is dan een brood en een vliegtuig nog duurder is dan een auto, dan verwachten we dat een vliegtuig zeker duurder is dan een brood. Dat beschrijft de transitiviteit.

Partiële ordening

Wat we net hebben gedefinieerd is eigenlijk alleen een partiële ordening, geen totale. Waarom is die niet totaal? We proberen een ordening op verzamelingen te definiëren. Hoe kunnen we twee verzamelingen vergelijken?

We zeggen dat de verzameling A kleiner dan of gelijk aan de verzameling B is als A ⊆ B, dus als A een deelverzameling van B is. Dat is logisch, want als we A = {1, 2} en B = {1, 2, 3} hebben, dan kunnen we van A zeggen dat die kleiner is — B bevat dezelfde elementen als A en bovendien nog het getal drie. Er zal bijvoorbeeld gelden:

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

Het probleem ontstaat als we deze verzamelingen willen vergelijken: A = {a, b} en B = {a, c}. Welke van de twee is kleiner of groter? Het probleem is dat beide verzamelingen weliswaar het element a bevatten, maar het tweede element is steeds anders. Geen van beide verzamelingen is een deelverzameling van de andere, dus er geldt noch A ≤ B noch B ≤ A. Zulke verzamelingen zijn met onze ordening onvergelijkbaar.

Daarom definiëren we een totaal geordende verzameling of ook keten: een verzameling waarin elke twee elementen vergelijkbaar zijn. Zulke verzamelingen zijn bijvoorbeeld getalverzamelingen met de klassieke ordening. Voor elke twee reële getallen a, b kun je beslissen of a ≤ b of b ≤ a.

Voorbeelden uit het dagelijks leven

Een voorbeeld waarbij het loont om niet te vergelijken, kan ordenen op aantrekkelijkheid zijn, waarbij de relatie < dan “minder mooi zijn” zou betekenen. Misschien moeten we het juist andersom definiëren, > als “mooier zijn”, om correcter te zijn :-). Het heeft waarschijnlijk zin om twee vrouwen met elkaar te vergelijken, bijvoorbeeld “Emma” < “Sophie” in de zin dat Sophie mooier is dan Emma. Of twee mannen: “Bram” < “Daan” in de zin dat Daan mooier is dan Bram.

Het probleem is dat we de schoonheid van een man en een vrouw waarschijnlijk moeilijk kunnen vergelijken. Is Sophie mooier of Daan? Is Emma minder mooi dan Bram, of Bram minder mooi dan Emma? Laten we dat maar niet onderzoeken…

Als we ons in het laatste voorbeeld bijvoorbeeld beperken tot vrouwen, kunnen we zeggen dat we een totaal geordende verzameling hebben, omdat we de schoonheid van alle vrouwen kunnen vergelijken.

Minimaal en maximaal element, kleinste en grootste element

Als we een geordende verzameling M hebben, noemen we een element min ∈ M minimaal als er geen x ∈ M bestaat zodat x < min. We kunnen dus geen element vinden dat kleiner is dan het element min.

Een element max ∈ M noemen we maximaal als er geen x ∈ M bestaat zodat x > max. We kunnen dus geen element vinden dat groter is.

De voorgaande twee begrippen verschillen van de begrippen kleinste en grootste.

Een element a ∈ M noemen we kleinste als voor alle x ∈ M geldt dat a ≤ x. Het kleinste element a is dus kleiner dan of gelijk aan alle andere elementen van de verzameling M.

Een element b ∈ M noemen we grootste als voor alle x ∈ M geldt dat b ≥ x. Het grootste element b is groter dan of gelijk aan alle andere elementen van de verzameling M.

Wat is het verschil tussen het grootste element en een maximaal element? Er kunnen meer maximale elementen zijn, omdat de verzameling niet per se totaal geordend hoeft te zijn. Als we teruggaan naar het voorbeeld van mensen vergelijken op uiterlijk, dan kunnen we zeggen dat Sophie de mooiste vrouw is en Daan de mooiste man. Maar deze twee personen kunnen we onderling niet meer vergelijken, we weten niet of Sophie mooier is of Daan.

Beide elementen zijn dus maximaal. We kunnen geen persoon vinden die mooier is dan Daan — Daan is mooier dan alle andere mannen en met vrouwen kunnen we hem niet vergelijken. Net zo voor Sophie — zij is mooier dan alle vrouwen en met mannen kunnen we haar niet vergelijken.

Maar geen van beiden is de grootste, in deze zin de mooiste. Want om de mooiste/grootste te zijn, zou Daan mooier moeten zijn dan alle personen, ook alle vrouwen. Maar we hebben al gezegd dat we hem niet met vrouwen kunnen vergelijken, dus hij kan niet de mooiste mens zijn, hij is alleen, in de terminologie van de ordeningstheorie, maximaal.

Het is waarschijnlijk makkelijk in te zien dat als een verzameling een grootste element heeft, dat element tegelijk ook maximaal is. Als het element a groter is dan alle andere elementen van de verzameling (definitie van het grootste element), dan vinden we zeker geen element dat nog groter is (definitie van het maximale element).

Een voorbeeld van een verzameling die een grootste en een kleinste element heeft, is bijvoorbeeld het gesloten interval [0, 1]. Als we hetzelfde interval kiezen, maar dan open, heeft het geen grootste en geen kleinste element: ⟨0, 1⟩.

Als we oneindig veel minimale elementen willen, kunnen we de ordening R als volgt definiëren. Eerst definiëren we hulpverzamelingen M_x. De verzamelingen hebben deze vorm: voor alle x uit het interval ⟨0, 1⟩ definiëren we de verzameling M_x = {y | y = x + n}, waarbij n een niet-negatief geheel getal is. Zo krijgen we bijvoorbeeld de volgende verzamelingen:

$$\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}$$

Op elke verzameling M_x definiëren we de klassieke ordening, die we R_x noemen. Aan het eind verenigen we deze ordeningen gewoon: R = ∪ R_x. In deze ordening kunnen we dus altijd alleen binnen de oorspronkelijke ketens vergelijken. We kunnen dus nagaan of 0,5 ≤ 2,5, maar we kunnen niet nagaan of 0,5 ≤ 2,7, omdat deze getallen niet in dezelfde verzameling M_x zaten en hun verband dus niet is gedefinieerd.

In deze ordeningsrelatie geldt dan dat elk element uit het interval ⟨0, 1⟩ een minimaal element is.

Hassediagrammen

Geordende verzamelingen kunnen we tekenen met een hassediagram. Dat is een graaf waarin de knopen de elementen van de verzameling voorstellen en een lijn tussen de knopen (a, b) ons zegt dat a < b en tegelijk dat er geen c bestaat zodat a < c < b. Tussen de elementen a en b zit dus geen ander element meer. Daarbij moet gelden dat in de graaf de knoop a lager ligt dan de knoop b. Een voorbeeld van een hassediagram:

Dit hassediagram stelt de geordende verzameling {A, B, C, D, E, F} voor. Daarbij geldt: A < B, B < E, en vanzelfsprekend geldt ook A < E, maar tussen deze knopen loopt geen lijn, omdat er een knoop B bestaat waarvoor geldt A < B < E. De elementen E en D zijn onvergelijkbaar, omdat geen van beide boven of onder de ander ligt.

Hoewel hassediagrammen meestal zo mooi uitgelijnd worden getekend, is dat niet per se nodig. Het vorige hassediagram kan er ook zo uitzien:

Een ander voorbeeld is de verzameling: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Dat zijn de natuurlijke delers van het getal 60. De ordening naar deelbaarheid kan zo worden weergegeven:

Ordening naar deelbaarheid betekent dat (a, b) ∈ R precies dan als a een deler van b is. In het diagram zie je dat boven elk getal de getallen staan die het deelt. Boven het getal 6 staan bijvoorbeeld de getallen 12, 30 en 60. Boven het getal 4 staan de getallen 12, 20 en 60. Enzovoort. Boven het getal 3 staat daarentegen niet het getal 10, omdat 3 dat niet deelt — let op, het getal 10 staat visueel boven het getal 3, maar er loopt geen lijn “van onder naar boven” naartoe. Als we vanaf het getal 3 alleen omhoog gaan, kunnen we naar de getallen 15 en 6 en vanaf daar naar het getal 30. Bij het getal 10 zouden we alleen komen door naar beneden te klimmen, en dat mag niet.