Ordeningsstructuren

Ordeningsstructuren zijn wiskundige structuren die bestaan uit een verzameling en een orde-relatie op die verzameling. Die relatie drukt uit hoe elementen zich tot elkaar verhouden, bijvoorbeeld of een element kleiner, gelijk of onvergelijkbaar is met een ander. De basale vormen zijn preorders en partiële ordeningen.

In de meest eenvoudige vorm is een ordeningsstructuur vaak een partiële orde (poset): een relatie die reflexief, antisymmetrisch en transitief is. Als iedere twee elementen vergelijkbaar zijn (elke twee elementen zijn bana wel één van beide relaties) spreekt men van een totale orde. Een veelgebruikt beeld hierbij is een Hasse-diagram dat de verhoudingen tussen elementen schematisch weergeeft.

Een belangrijke bouwsteen binnen ordeningsstructuren is de lattice. Een meet/joinstructuur houdt in dat voor elk paar elementen een grootste onderste buur (meet) en een kleinste bovenliggende buur (join) bestaan. Distributieve en modulaire lattices zijn speciale voorbeelden. Boolean-algebras vormen een klasse van distributieve, volledig complementaire ordeningsstructuren die veelvuldig in logica en informatica voorkomen.

Andere concepten zijn dualiteit (de ordening omkeren levert een tegengestelde structuur), volledige en compacte ordeningen (waar elk subset een supremum en infimum heeft), en verschillende typen morphismen zoals orderbehoudende functies (monotone functies), order-embeddings en ordenisomorfismen.

Veelvoorkomende voorbeelden zijn de natuurlijke getallen met ≤, de reële getallen met ≤, de deling-orde op natuurlijke getallen, en de verzameling van deelverzamelingen met inclusie, die samenluie tot lattices en boolean algebra. Ordeningsstructuren hebben toepassingen in informatica (prioriteitschema’s, algoritmen), formele conceptanalyse, en domains in de theoretische computerwetenschap.