Ordetheorie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de wiskunde houdt de ordetheorie zich bezig met de verschillende manieren waarop objecten geordend kunnen zijn. Daartoe wordt het intuïtieve begrip van ordening of rangschikking gemodelleeerd als een tweeplaatsige relatie of in het geval van een cyclische orde drieplaatsige relatie met kenmerkende eigenschappen tussen de elementen van eenzelfde verzameling.

Een bekend voorbeeld is de ordening van getallen. Van twee verschillende getallen is steeds een van beide kleiner dan het andere. Men noteert bijvoorbeeld 3 < 7 voor de relatie 'kleiner dan' tussen de getallen 3 en 7. Er zijn ook andere vormen van ordening, zoals in het spel 'steen, papier, schaar', waarin de ordening, aangegeven door '<' (zwakker), cyclisch van aard is: steen < papier < schaar < steen, waarna men weer bij het begin is.

Men onderscheidt wel:

Partiële ordes[bewerken]

Een tweeplaatsige endorelatie ≤ op X is een partiële orde dan en slechts dan als de relatiereflexief, anti-symmetrisch en transitief is.

Een tweeplaatsige endorelatie < op X is een strikte partiële orde dan en slechts dan als < asymmetrisch en transitief is. Asymmetrie impliceert bovendien irreflexiviteit. Een strikte partiële orde kan ook gedefinieerd worden als een irreflexieve, transitieve tweeplaatsige endorelatie, want irreflexiviteit en transitiviteit impliceren samen asymmetrie.

Er is een een-op-een-correspondentie tussen alle partiële ordes op een verzameling X en alle strikte partiële ordes op dezelfde verzameling X die verkregen wordt door iedere partiële orde af te beelden op zijn reflexieve reductie. Van iedere partiële orde op X is zijn reflexieve reductie namelijk een strikte partiële orde op X. Verder is het zo dat de inverse van deze een-op-een-correspondentie strikte partiële ordes afbeeldt op hun reflexieve afsluiting.[1] De reflexieve afsluiting van een strikte partiële orde op X is een partiële orde op X. Merk op dat de inverse van het complement van een partiële orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte partiële orde < de reflexieve afsluiting van < is.

De inverse van een partiële orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een partiële orde. De inverse van een strikte partiële orde < wordt vaak genoteerd als > en is zelf ook een strikte partiële orde. Het complement van een partiële orde is een strikte partiële orde en vice versa.

Een partiële orde waarbij ieder paar argumenten een gezamenlijk infimum en een gezamenlijk supremum heeft, heet een tralie.

Totale ordes[bewerken]

Een tweeplaatsige endorelatie ≤ op X is een totale ordening dan en slechts dan als ≤ antisymmetrisch, transitief en totaal is. Totaliteit impliceert reflexiviteit, waardoor iedere totale orde ook een partiële orde is.

Een tweeplaatsige endorelatie < op X is een strikte totale ordening dan en slechts dan als < transitief en trichotoom is. Trichotomie impliceert asymmetrie, waardoor iedere strikte totale orde ook een strikte partiële orde is.

Op dezelfde wijze als bij partiële ordes kan er een een-op-een-correspondentie geconstrueerd worden tussen alle totale ordes op een verzameling X en alle strikte totale ordes op dezelfde verzameling X. Ook hierbij geldt dat de inverse van het complement van een totale orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte totale orde < de reflexieve afsluiting van < is.

De inverse van een totale orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een totale orde. De inverse van een strikte totale orde < wordt vaak genoteerd als > en is zelf ook een strikte totale orde. Het complement van een totale orde is een strikte totale orde en vice versa.

Preorde[bewerken]

Een tweeplaatsige endorelatie \lesssim op X is een preorde dan en slechts dan als \lesssim reflexief en transitief is. Voor iedere tweeplaatsige endorelatie R is de reflexief-transitieve afsluiting R * een preorde.

Een tweeplaatsige endorelatie \lesssim op X is een totale preorde dan en slechts dan als \lesssim transitief en totaal is. Merk op dat totaliteit reflexiviteit impliceert.

Een antisymmetrische preorde is een partiële orde en een symmetrische preorde is een equivalentierelatie. Een antisymmetrische totale preorde is een totale orde.

Voor iedere preorde \lesssim op X kan een equivalentierelatie ~ op X gedefinieerd worden waarvoor geldt dat voor alle xy \in X:

x ~ y dan en slechts dan als x\lesssimy en y\lesssimx.

Als vervolgens een relatie ≤ op X/~ afgeleid wordt door te stellen dat voor alle xy \in X geldt dat

[x] ≤ [y] dan en slechts dan als x\lesssimy,

dan is ≤ een partiële orde op X/~. Hieruit kan vervolgens een strikte partiële orde < op X afgeleid worden, zodanig dat voor alle xy \in X geldt dat

x < y dan en slechts dan als [x] ≤ [y] en [x] ≠ [y],

ofwel (de equivalente uitspraak) dat

x < y dan en slechts dan als x\lesssimy en niet x ~ y.

Onder deze constructies geldt voor alle xy \in X dat

x\lesssimy dan en slechts dan als x < y of x ~ y.

Dit verklaart de notatie \lesssim en geeft inzicht in de relatie tussen preordes en (strikte) partiële ordes.

De term "strikte preorde" is niet gedefinieerd. Dit zou immers zoiets als een irreflexieve en transitieve tweeplaatsige endorelatie moeten zijn, maar irreflexiviteit en transitiviteit impliceren samen asymmetrie, wat een strikte partiële orde op zou leveren. Hetzelfde geldt voor de term "strikte totale preorde". Irreflexiviteit en transitiviteit impliceren samen met de voorwaarde

voor alle xy \in X geldt: als x ≠ y dan xRy of yRx (vgl. totaliteit)

namelijk trichotomie, wat een strikte totale orde op zou leveren.

Het is uiteraard wel mogelijk om de inverse van het complement van een totale preorde te nemen. Dit levert een strikte zwakke orde op.

Strikte zwakke orde[bewerken]

Een strikte partiële < orde op X is een strikte zwakke orde dan en slechts dan als de relatie "noch x < y, noch y < x" transitief is. Deze voorwaarde wordt ook wel transitiviteit van onvergelijkbaarheid genoemd. Een alternatieve, equivalente manier om deze voorwaarde te formuleren is:

Voor alle xy \in X geldt: als x < y dan geldt voor alle z \in X dat x < z of z < y (of beide).

Het complement van een strikte zwakke orde is een totale preorde en vice versa.

Cyclische ordening[bewerken]

Een cyclische ordening op een verzameling V is lastiger algemeen precies te definiëren. Als er maar eindig veel elementen zijn, kunnen we die voorstellen als punten op een cirkel, waarbij we rechtsomgaand steeds als volgend punt de opvolger aantreffen en alle elementen tegenkomen.

Voor eindige verzamelingen kan een cyclische ordening opgevat worden als een bijectieve afbeelding f van V op V. Zo'n afbeelding voegt aan elk element z'n opvolger toe. Zonder de eis dat uitgaande van een van de elementen de hele verzameling doorlopen moet worden, ontstaat slechts een partiële cyclische ordening, bestaande uit een of meer cykels van elkaar opvolgende elementen. Is er maar één cykel, dan spreken we van cyclische ordening. Daartoe eisen we:

\{f^k(v)|k=1,...,n\}=V voor een willekeurige v ∈ V,

waarin n het aantal elementen van V is.

Het is niet moeilijk in te zien dat dan ook uitgaande van elk ander element de hele verzameling doorlopen wordt.

Deze manier om een cyclische ordening te definiëren kan niet gegeneraliseerd worden voor niet-eindige verzamelingen. Als namelijk zo'n opvolger zou bestaan voor elk element in een aftelbaar oneindige verzameling V, brengt deze een aftelling voort door de keuze van een element v en:

v_n=f^n(v).

In die aftelling moet de voorganger van v voorkomen, zeg f^{-1}(v)=v_m. Maar dan is v_{m+1}=v, wat inhoudt dat er maar eindig veel opvolgers zouden zijn.

Toch laat een aftelbaar oneindige verzameling wel een cyclische ordening toe, zoals we kunnen inzien door de natuurlijke getallen (even zonder 0) af te beelden op het interval (0,1] door  n \mapsto 1/n en het interval tot een cirkel te maken. We zien nu ook waarom het begrip opvolger hier niet werkt. Weliswaar heeft elk getal n een opvolger, namelijk n+1, maar het getal 1 is van geen getal de (directe) opvolger.

Daarom hanteren we de volgende definitie, die voor eindige verzamelingen equivalent is met het bovengenoemde begrip "opvolger".

Definitie[bewerken]

Een cyclische ordening op een verzameling V is een drieplaatsige relatie R \sub V^3, die we voor het gemak even schrijven als abc = R(a,b,c), waarvoor geldt:

  1. abc \Rightarrow a,b,c verschillend
  2. abc \or acb
  3. \lnot (abc \and acb)
  4. abc \and acd \Rightarrow bcd
  5. abc \Rightarrow bca

Opmerkingen: Eis 1 houdt in dat we alleen verschillende elementen met elkaar willen vergelijken. Eis 2 en 3 betekenen dat van de twee manieren om door een drietal heen te lopen er maar een volgens de ordening is: als we van a naar c gaan, komen we of b tegen voor we bij c zijn, of pas na c, een van tweeën. Eis 4 betekent dat vanuit a gezien b voor en d achter c ligt. Eis 5 tenslotte maakt de relatie tot een cyclische.

Logischerwijze moet 4 ook als gevolg hebben dat abd in die volgorde liggen. Stel namelijk dat de volgorde is: adb, dus ook bad. Samen met abc, dus bca, levert dat via eigenschap 5: cad. Maar dat is in tegenspraak met acd.

Equivalentie voor eindige verzamelingen[bewerken]

Voor een eindige verzameling is deze de laatste definitie equivalent met de definitie via een functie "opvolger". Als V n elementen heeft en f betekent opvolger, definiëren we de ternaire relatie R op voor de hand liggende wijze, door:

abc \Leftarrow \Rightarrow b=f^k(a) \and c=f^m(b) \and 0<k+m<n.

Daarmee is dan vanzelf aan 1 voldaan. Als a,b en c verschillend zijn, is:

b=f^k(a) \and c=f^m(b) \and 0<k, 0<m k\neq m,

dus

k<m \Rightarrow abc; k>m \Rightarrow acb,

waarmee R aan 2 en 3 voldoet. Tevens volgt:

a=f^{-k}(b)=f^{n-k}(b)

zodat bca, want

c=f^m(b) \and m<n-k.

Daarmee is ook aan 5 voldaan. Als naast abc ook acd geldt, is:

d=f^r(a),\;r>m+k.

Daaruit volgt direct het in 4 geëiste: bcd.

Omgekeerd kunnen we voor een eidige V met ten minste 3 elementen (anders is het triviaal) bij een cyclische ordening R een opvolgerfunctie f definiëren door voor f(a) het element b te nemen waarvoor abc en er geen v is met avb. De functie f is injectief en omdat V eindig is dus bijectief, want stel:

f(a)=f(b)=c, d=f(c) \Rightarrow acd \and bcd,

dus moet abc of bac, maar dat is in strijd met de definitie van f.

Voorbeeld[bewerken]

We laten nu zien dat de natuurlijke getallen inderdaad een cyclische ordening toelaten. Daartoe definiëren we de relatie R door:

1 \le k < m < n \Rightarrow kmn \and mnk \and nkm.

Het is niet moeilijk aan te tonen dat R aan de eisen voldoet.

Bronnen, noten en/of referenties
  1. N.B. In het algemeen is het niet zo dat voor een tweeplaatsige endorelatie R geldt dat (R) = = R.