Ordetheorie

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.

Voor meer toelichting, zie de aparte artikelen.

Een orde wordt meestal gedefinieerd door een homogene tweeplaatsige relatie.

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 ${\displaystyle A=\{a,b,c,d\}}$  met vier elementen is bijvoorbeeld de relatie ${\displaystyle a\leq b\leq c\leq d}$  een totale orde,^[1] 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 ${\displaystyle B=\{a,b,c,d,e,f\}}$  met zes elementen is bijvoorbeeld de relatie ${\displaystyle a\leq b\leq c}$  en ${\displaystyle 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 ${\displaystyle \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: ${\displaystyle 2\lesssim 1+2i,\quad 1\lesssim i\quad }$  en ook ${\displaystyle \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 ${\displaystyle x}$  en ${\displaystyle 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 ${\displaystyle \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.

 

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 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.

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 ${\displaystyle A}$  via ${\displaystyle B}$  en ${\displaystyle C}$  naar ${\displaystyle D}$  kan men '<' definiëren als 'is dichter bij ${\displaystyle A}$  dan', dan geldt ${\displaystyle B<C}$ , maar even goed als 'is dichter bij ${\displaystyle D}$  dan', dan geldt ${\displaystyle C<B}$ .

Cyclische orde

Er bestaat de cyclische orde, die men zich kan voorstellen als een orde op een cirkel. Op een cirkel met drie plaatsen ${\displaystyle x,y}$  en ${\displaystyle z}$  ligt in een bepaalde richting het element ${\displaystyle y}$  voor ${\displaystyle x}$ , ${\displaystyle x}$  voor ${\displaystyle z}$ , maar ${\displaystyle z}$  weer voor ${\displaystyle 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 ${\displaystyle x,y,z\in X}$ :

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