Ordetheorie

In de wiskunde houdt de ordetheorie zich bezig met de verschillende manieren om de elementen van een verzameling te sorteren, ze in een gekozen volgorde te kunnen plaatsen. Daartoe wordt de volgorde vastgelegd als een relatie tussen twee elementen die aangeeft welke van de elementen opvolger is van het andere. Kenmerkend voor een dergelijke orde is dat die transitief is. Er worden in de ordetheorie vormen van orde beschreven, waarin nog niet alle elementen volledig zijn gesorteerd. De vier meest voorkomende vormen van orde zijn de totale orde, de partiële orde, de totale preorde en de preorde. De elementen zijn in een totale orde volledig gesorteerd, maar in een preorde is er alleen nog maar een eerste ordening.

De elementen van een te sorteren verzameling kunnen dus wel worden geordend, hun onderlinge volgorde kan worden bepaald. Die onderlinge volgorde wordt erdoor bepaald welk element een opvolger van welk element is. Dat kan door middel van een tweeplaatsige relatie. De elementen kunnen niet door hun plaats in de verzameling worden bepaald, anders was het geen verzameling maar een rij. Er moet bij het sorteren onder andere op worden gelet, dat er cirkels in de te sorteren verzameling ontstaan. De cyclische orde is ervoor gedefinieerd om te kunnen onderkennen dat dit in een verzameling het geval is en wordt daartoe als een ternaire relatie gedefinieerd.

Voorbeelden

Een bekend voorbeeld is de ordening van de gehele 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 volgorde tussen de elementen, aangegeven door <, of zwakker, cyclisch van aard is: steen < papier < schaar < steen, waarna men weer bij het begin is.

Soorten orde gedefinieerd door een tweeplaatsige relatie

Voor meer toelichting, zie de aparte artikelen.

Een orde wordt meestal gedefinieerd door een homogene tweeplaatsige relatie.

Reflexieve soorten

Totale orde

De duidelijkste vorm van ordening is de totale orde. Twee elementen in een verzameling met een totale orde kunnen altijd met elkaar worden vergeleken. Een totale orde kan opgevat worden als een keten van elementen, waarvan van elk tweetal geldt dat ofwel het eerste vóór het tweede komt, ofwel het tweede vóór het eerste. Een totale orde wordt ook lineaire orde genoemd. De gehele getallen zoals hierboven is aangegeven, vormen een verzameling met een totale ordening. Op de verzameling $A=\{a,b,c,d\}$ met vier elementen is bijvoorbeeld de relatie $a\leq b\leq c\leq d$ een totale orde, evenals iedere andere permutatie van de elementen.

Partiële orde

In een partiële orde kunnen elementen voorkomen die niet met elkaar kunnen worden vergeleken. Als we natuurlijke getallen ordenen door deelbaarheid dan ontstaat bijvoorbeeld een partiële orde. Zo is in die partiële orde 10 kleiner dan 30 omdat 30 door 10 kan worden gedeeld, maar zijn 30 en 12 niet met elkaar te vergelijken, omdat geen van beide door de ander kan worden gedeeld. Op de verzameling $B=\{a,b,c,d,e,f\}$ met zes elementen is bijvoorbeeld de relatie $a\leq b\leq c$ en $d\leq e$ een partiële orde. Een tralie is verzameling met een partiële orde waarvan iedere eindige deelverzameling zowel een supremum als een infimum heeft. Een hasse-diagram is een grafische afbeelding van een eindige verzameling met een partiële orde.

Totale preorde

Een totale preorde, of zwakke orde, onderscheidt zich er van een totale orde in, dat er equivalente elementen in kunnen voorkomen. Een totale preorde is een preorde waarin van elke twee niet equivalente elementen een van beide kleiner is dan het andere. Een totale preorde staat net als een partiële orde tussen de preorde en de totale orde in. In het ene opzicht is een totale preorde sterker, in een ander opzicht zwakker dan een partiële orde. Het gebruikelijke symbool om een totale preorde aan te geven is hetzelfde als voor een preorde in het algemeen, dat is $\lesssim$.

• De complexe getallen vormen een verzameling met een totale preorde. Twee complexe getallen kunnen met elkaar worden vergeleken door hun absolute waarde met elkaar te vergelijken. De orde moet dus gelezen worden als "heeft een kleinere of dezelfde absolute waarde". Bijvoorbeeld: $2\lesssim 1+2i,\quad 1\lesssim i\quad$ en ook $\quad i\lesssim 1$.

Preorde

Een preorde is een nog ruimer begrip dan een partiële orde en een totale preorde. In een preorde kunnen elementen $x$ en $y$ voorkomen die niet met elkaar vergeleken kunnen worden, of die van elkaar verschillen, maar equivalent geacht worden, dat wil zeggen dat ze op dezelfde plaats in de ordening staan. De relatie is te omschrijven als 'kleiner of equivalent' in plaats van 'kleiner of gelijk'. Het gebruikelijke symbool om een preorde aan te geven is $\lesssim$, dat de symbolen voor kleiner en equivalent combineert. Een preorde is reflexief en transitief. Een preorde op een verzameling wordt gekarakteriseerd door een partitie van die verzameling waarvan de klassen partieel zijn geordend.

De relatie 'is een bijzonder geval van' tussen vier ordesoorten. Pijlen van items naar zichzelf zijn weggelaten. Deze relatie is zelf een partiële orde.

Samenhang

De nevenstaande figuur toont de samenhang tussen de verschillende ordes: totale orde, partiële orde, totale preorde en preorde. De pijlen geven aan 'is een bijzonder geval van'.

De totale preorden op een verzameling corresponderen één op één met het geheel van de totale orden op de partities van de verzameling. De preorden op een verzameling corresponderen één op één met het geheel van de partiële orden op de partities van de verzameling.

Bijbehorende irreflexieve soorten

Bijbehorende irreflexieve ordesoorten zijn de strikte totale orde, de strikte partiële orde, en de bij de totale preorde behorende strikte zwakke orde, een ondersoort van de strikte partiële orde. Voor de preorde in het algemeen is er niet zo'n bijbehorende soort.

Dualiteit

Voor elke definitie en stelling in de ordetheorie is er een inverse, waarbij termen als kleinste, grootste, infimum, supremum, minimaal en maximaal kunnen worden vervangen door de tegenhanger, met bijbehorende vervanging van tekens als '<' door het tegengestelde of verwisseling van de operanden. Een dergelijke inverse is een tegenovergestelde categorie.

Evenzo kan men in toepassingen een orde omgekeerd definiëren. Soms is een van beide mogelijkheden voor de hand liggend en de andere verwarrend, maar in andere gevallen is deze willekeurig. Op een traject van $A$ via $B$ en $C$ naar $D$ kan men '<' definiëren als 'is dichter bij $A$ dan', dan geldt $B<C$, maar even goed als 'is dichter bij $D$ dan', dan geldt $C<B$.

Overige

Cyclische orde

Er bestaat de cyclische orde, die men zich kan voorstellen als een orde op een cirkel. Op een cirkel met drie plaatsen $x,y$ en $z$ ligt in een bepaalde richting het element $y$ voor $x$, $x$ voor $z$, maar $z$ weer voor $y$.

Strikte zwakke orde

Het complement van een totale preorde is een strikte zwakke orde en omgekeerd. Voor een strikte zwakke orde geldt dat voor alle $x,y,z\in X$:

$x<y\Longrightarrow x<z\ {\text{ of }}\ z<y$, of beide.

Voetnoten