Totale preorde
In de ordetheorie, een onderdeel van de wiskunde, heet een tweeplaatsige relatie op een verzameling een totale preorde als het een transitieve totale relatie is. Deze wordt vaak genoteerd met het symbool . De strikte totale preorde '<' van een totale preorde is het complement van de inverse ervan, en tevens de inverse van het complement, dus met gedefinieerd als niet . De strikte totale preorde is een vorm van de strikte zwakke orde.
Een functie met een totaal geordende verzameling bepaalt een totale preorde op door te nemen als . Er geldt als en als . Zoals de notatie suggereert geldt dus dan en slechts dan als of .
- Als deze met een strikt stijgende functie wordt gecombineerd, dan bepaalt de nieuwe functie dezelfde totale preorde.
- Als een injectieve functie is kan het teken 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 kunnen we de equivalentierelatie definiëren, met als en . Deze equivalentierelatie betekent in termen van preferenties geen voorkeur bij de keuze tussen en . De preorde leidt tot een relatie op de equivalentieklassen ( als ) en deze relatie is een totale orde.
Voorbeelden
[bewerken | brontekst bewerken]- 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: , en ook .
- De reflexief-transitieve afsluiting van de relatie , , , , , en op de verzameling met vijf elementen is een totale preorde. De elementen en zijn equivalent: , 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
[bewerken | brontekst bewerken]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/3/3c/13-Weak-Orders.svg/260px-13-Weak-Orders.svg.png)
Het aantal mogelijke totale preordes van een verzameling hangt van het aantal elementen in 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 twee elementen heeft dan zijn er drie totale preordes. In termen van preferenties: liever het ene, liever het andere of geen voorkeur.
- Als 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.