Totale preorde

In de ordetheorie, een onderdeel van de wiskunde, heet een tweeplaatsige relatie ${\displaystyle R}$ op een verzameling ${\displaystyle X}$ een totale preorde als het een transitieve totale relatie is. Deze wordt vaak genoteerd met het symbool ${\displaystyle \lesssim }$. De strikte totale preorde '<' van een totale preorde is het complement van de inverse ervan, en tevens de inverse van het complement, dus met ${\displaystyle x<y}$ gedefinieerd als niet ${\displaystyle y\lesssim x}$. De strikte totale preorde is een vorm van de strikte zwakke orde.

Een functie ${\displaystyle f\colon X\to Y}$ met ${\displaystyle Y}$ een totaal geordende verzameling bepaalt een totale preorde op ${\displaystyle X}$ door ${\displaystyle x\lesssim y}$ te nemen als ${\displaystyle f(x)\leq f(y)}$. Er geldt ${\displaystyle x<y}$ als ${\displaystyle f(x)<f(y)}$ en ${\displaystyle x\sim y}$ als ${\displaystyle f(x)=f(y)}$. Zoals de notatie suggereert geldt dus ${\displaystyle x\lesssim y}$ dan en slechts dan als ${\displaystyle x<y}$ of ${\displaystyle x\sim y}$.

• Als deze ${\displaystyle f}$ met een strikt stijgende functie ${\displaystyle g\colon Y\to Y}$ wordt gecombineerd, dan bepaalt de nieuwe functie ${\displaystyle g\circ f}$ dezelfde totale preorde.
• Als ${\displaystyle f}$ een injectieve functie is kan het teken ${\displaystyle \sim }$ vervangen worden door een gelijkteken, is de totale preorde een totale orde en de strikte zwakke orde een strikte totale orde.

Gegeven een totale preorde ${\displaystyle \lesssim }$ kunnen we de equivalentierelatie ${\displaystyle \sim }$ definiëren, met ${\displaystyle x\sim y}$ als ${\displaystyle x\lesssim y}$ en ${\displaystyle y\lesssim x}$. Deze equivalentierelatie betekent in termen van preferenties geen voorkeur bij de keuze tussen ${\displaystyle x}$ en ${\displaystyle y}$. De preorde ${\displaystyle \lesssim }$ leidt tot een relatie op de equivalentieklassen (${\displaystyle [a]_{\sim }\leq [b]_{\sim }}$ als ${\displaystyle a\lesssim b}$) en deze relatie is een totale orde.

Voorbeelden

• 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. Bijvoorbeeld: ${\displaystyle 2\lesssim 1+2i}$, ${\displaystyle 1\lesssim i\quad }$ en ook ${\displaystyle \quad i\lesssim 1}$.

• De reflexief-transitieve afsluiting van de relatie ${\displaystyle a\lesssim b}$, ${\displaystyle b\lesssim c}$, ${\displaystyle b\lesssim d}$, ${\displaystyle c\lesssim d}$, ${\displaystyle d\lesssim c}$, ${\displaystyle c\lesssim e}$ en ${\displaystyle d\lesssim e}$ op de verzameling ${\displaystyle \{a,b,c,d,e\}}$ met vijf elementen is een totale preorde. De elementen ${\displaystyle c}$ en ${\displaystyle d}$ zijn equivalent: ${\displaystyle d\sim e}$, en van elk ander tweetal elementen is een van beide kleiner dan het andere.

• Een preferentierelatie van een goed geïnformeerde logisch denkende consument is een totale preorde. De strikte totale preorde in termen van preferenties komt overeen met 'wordt minder geapprecieerd dan'.

• Als bij sorteren een sorteersleutel wordt gebruikt die soms bij verschillende items gelijk is, wordt gesorteerd op basis van een totale preorde van de items, waarvan het resultaat in principe een rij equivalentieklassen is. In de praktijk is het resultaat van een sorteeralgoritme vaak één rij van items. De items binnen een equivalentieklasse worden dan in principe in een willekeurige volgorde geplaatst.

Aantal mogelijke totale preordes

13 totale preordes op een verzameling met drie elementen

Het aantal mogelijke totale preordes van een verzameling ${\displaystyle X}$ hangt van het aantal elementen ${\displaystyle n}$ in ${\displaystyle X}$ af. Dat aantal wordt in rij A000670^[1] van de OEIS gegeven. Er zijn ook rijen voor het aantal andere soorten homogene tweeplaatsige relaties.

• Als ${\displaystyle X}$ twee elementen heeft dan zijn er drie totale preordes. In termen van preferenties: liever het ene, liever het andere of geen voorkeur.

• Als ${\displaystyle X}$ drie elementen heeft dan zijn er 13 totale preordes. In termen van preferenties: zes met drie verschillende appreciaties, zes met twee verschillende en een zonder enige voorkeur.

Voetnoten

1. A000670