Partiële orde

Schematische weergave (gerichte graaf) van een partiële orde
Schematische weergave (gerichte graaf) van een partiële orde
Schematische weergave (gerichte graaf) van een partiële orde

In de ordetheorie, een deelgebied van de wiskunde, is een partiële orde of partiële ordening op een verzameling een relatie op die verzameling, meestal genoteerd als "", die aangeeft welke van de elementen met elkaar vergeleken kunnen worden als volgend op elkaar. In een partiële orde worden niet noodzakelijk alle elementen met elkaar vergeleken, maar kunnen er paren elementen zijn waarvan niet uitgemaakt is welke van de twee in de orde voorafgaat aan de ander. In een extreem geval is zelfs geen enkel tweetal vergelijkbaar. Een partiële orde is een generalisatie van het begrip totale orde, waarin van elk tweetal elementen vaststaat welke van de twee de opvolger is van het andere.

Definitie

Hasse-diagram van de verzameling van alle delers van 60, partieel geordend op basis van deelbaarheid[1]
Algebraïsche structuren met onderling een partiële orde

Een partiële orde op een verzameling is een homogene tweeplaatsige relatie op die reflexief, transitief en antisymmetrisch is. Dat houdt in dat voor alle geldt:

  • reflexiviteit:
  • transitiviteit: als en , dan ook
  • antisymmetrie: als en , dan

Het is door de antisymmetrie onmogelijk, dat er gegeven de relatie een cykel in bestaat, dus dat er elementen zijn met .

De verzameling waarop een partiële ordening gedefinieerd is, heet een partieel geordende verzameling, in Engelstalige wetenschappelijke publicaties vaak verkort tot poset, van partially ordered set. Het verschil met een totale orde is dat in een verzameling met een totale orde twee elementen altijd met elkaar zijn te vergelijken, in een verzameling met een partiële orde wordt die eis niet gesteld.

Getallenverzamelingen

De orderelatie wordt meestal genoteerd als en wordt dan wel genoemd 'kleiner dan of gelijk aan'. Er is een bijbehorende orderelatie , 'groter dan of gelijk aan', zo dat dan en slechts dan als . Deze wordt de inverse van de orde genoemd en bepaalt zelf ook een orde. Definities van begrippen als grootste en kleinste element, infimum, supremum, maximaal en minimaal element, bovengrens en ondergrens worden steeds gedaan voor verzamelingen met ten minste één partiële ordening. Men zegt in andere soorten verzamelingen in plaats van , gelezen als 'kleiner of gelijk', ook dat een 'voorganger' van is als .

Voorbeeld

De relatie , 'kleiner dan of gelijk aan', bepaalt op de complexe getallen een partiële ordening, namelijk voor zover het de reële getallen betreft, immers:

  • voor alle ,
  • en impliceert voor alle ,
  • en impliceert voor alle .

Grafen

Een partiële orde op een eindig domein kan weergegeven worden als een gerichte graaf. In een context met alleen partiële ordes kan worden afgesproken dat de lussen (kromme lijnen van een knoop naar zichzelf) niet weergegeven worden, dat met de weergegeven graaf de transitieve afsluiting ervan wordt bedoeld en dat alleen de transitieve reductie ervan wordt weergegeven. Bij vaste posities van de elementen kan elke partiële orde weergegeven worden, maar het wordt vaak overzichtelijker als de posities van de elementen afhankelijk van de partiële orde worden gekozen. Bij een hasse-diagram worden de posities van de elementen sowieso deels bepaald door de partiële orde.

Deelverzameling

Een partiële orde op een verzameling bepaalt op natuurlijke wijze een partiële orde op een deelverzameling van door de restrictie van tot . Als voor twee elementen geldt: , dan is ook in de restrictie .

Een keten van een orderelatie is een deelverzameling zodat de restrictie een totale orde is.[2]

Een antiketen is een deelverzameling zodat de restrictie alleen lussen bevat, d.w.z.

[2]

Strikte partiële orde

Inleiding

Bij een partiële orde behoort altijd een overeenkomstige relatie die irreflexief is. Voor bijvoorbeeld de relatie 'groter dan of gelijk aan' is dit de relatie 'groter dan'. Een dergelijke ordening noemt men een strikte partiële orde. Hetzelfde verschil wordt tussen een totale orde en een strikte totale orde gemaakt.

Definitie

Een transitieve tweeplaatsige relatie, die asymmetrisch is, is ook irreflexief, neem , en een transitieve tweeplaatsige relatie, die irreflexief is, is ook asymmetrisch. Het verschil tussen antisymmetrie en asymmetrie is dat er in een antisymmetrische relatie elementen kunnen voorkomen met en in een asymmetrische relatie niet.

Een homogene tweeplaatsige relatie op de verzameling heet een strikte partiële orde, als transitief en asymmetrisch is, maar kan dus ook als een relatie worden gedefinieerd die transitief en irreflexief is. Een strikte partiële orde is dus geen partiële orde. Een partiële orde is antisymmetrisch, een strikte partiële orde asymmetrisch. Sommige auteurs noemen een partiële orde zoals hier genoemd een zwakke partiële orde.

Er is een bijectie tussen alle partiële ordes op een verzameling en alle strikte partiële ordes op dezelfde verzameling , die verkregen wordt door iedere partiële orde af te beelden op zijn reflexieve reductie. Van iedere partiële orde op is zijn reflexieve reductie namelijk een strikte partiële orde op . Deze wordt ook de bijbehorende strikte partiële orde genoemd. Verder is het zo dat de inverse van deze bijectie strikte partiële ordes afbeeldt op hun reflexieve afsluiting. De reflexieve afsluiting van een strikte partiële orde op is een partiële orde op . Deze wordt ook de bijbehorende partiële orde genoemd.

De strikte partiële orderelatie wordt meestal genoteerd als en wordt dan wel genoemd 'kleiner dan'. De inverse wordt dan genoteerd en 'groter dan' genoemd. Het is zelf ook een strikte partiële orde, en de reflexieve reductie van .

Van het viertal , , en volgen, zoals uit het bovenstaande blijkt, uit elk eenduidig de overige drie. Na introductie van een van de vier is het dan ook mogelijk de overige relaties te gebruiken zonder ze expliciet te definiëren. Als een orderelatie wordt aangeduid met een ander symbool, bijvoorbeeld , dan wordt voor de betekenis van begrippen als kleiner uitgegaan van die welke hoort bij de notatie of .

Voor twee elementen en zijn er vier mogelijkheden: gelijk, kleiner, groter en niet te vergelijken. De laatste komt bij een totale orde niet voor.

Tralie

Zie Tralie (wiskunde) voor het hoofdartikel over dit onderwerp.

Een partiële orde waarbij ieder paar argumenten een gezamenlijk infimum en een gezamenlijk supremum heeft, heet een tralie.

Lexicografische orde

De lexicografische orde/ordening/volgorde op het cartesisch product van twee partieel geordende verzamelingen en wordt gedefinieerd als

dan en slechts dan als of en .

Het resultaat is een partiële orde. Als en totaal geordend zijn, is de lexicografische orde ook een totale orde.

De lexicografische orde kan analoog ook worden gedefinieerd voor meer dan twee verzamelingen. Het begrip kan ook worden gehanteerd voor de orde van een deelverzameling van een cartesisch product, want de orde van het cartesisch product impliceert de orde van de deelverzameling.

Een datumnotatie als 2020-03-21 is lexicografisch, preciezer gezegd: de lexicografische orde komt overeen met de chronologie. Soms is er in wezen een lexicografische orde, maar worden de onderdelen in een andere volgorde genoteerd, zoals bij een datum in de vorm 11 maart 2020 in plaats van 2020.maart.11. Een tijdsnotatie als 12:27 p.m. is zelfs dat niet (want het is eerder dan 1:27 p.m.), tenzij een orde van de uren wordt gehanteerd met 12 kleiner dan 1. Bij een oude jaarstijl waarbij het jaartal midden in een maand werd opgehoogd, was de datumnotatie ook met zulke voorbehouden niet lexicografisch.

De term lexicografische orde is ontleend aan het ordenen van woorden en frasen (alfabetische volgorde) op basis van de volgorde van letters in het alfabet. Een simpele variant hiervan is gebaseerd op het denkbeeldig aanvullen met spaties van alle te sorteren teksten tot ze alle even lang zijn, en dan lexicografisch te sorteren met de spatie als eerste teken van de tekenset.[3] Voor een tekst met onderdelen met een nummering als 3.1.1, 3.2.1.5, enz.,[4] is de gebruikelijke volgorde van deze onderdelen overeenkomstig.

Geordende vectorruimte

Een vectorruimte over het lichaam der reële getallen heet geordend, als ze voorzien wordt van een partiële orde die op de volgende manieren de vectorruimtebewerkingen respecteert:[5] Voor alle met en , geldt

De reële getallen zelf voorzien van de natuurlijke orde vormen een geordende vectorruimte, maar ook iedere vectorruimte die uit reëelwaardige functies op een gegeven domein bestaat. Voor functies en geldt dan als voor iedere in het domein

Aantallen

Aantal mogelijke partiële ordes op een verzameling met elementen
aantal bij gelabelde elementen aantal bij ongelabelde elementen aantal bij ongelabelde elementen als orde en inverse samengenomen worden
0 1 1 1
1 1 1 1
2 3 2 2
3 19 5 4
4 219 16[6] 12
OEIS A001035[7] A000112[8]

Spraakgebruik

Soms wordt de uitdrukking 'niet te vergelijken' in het gewone spraakgebruik, enigszins verwarrend, gebruikt in een andere betekenis dan bovengenoemd, en wel om aan te geven dat van twee grootheden de ene veel groter is dan de andere.