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.

DefinitieBewerken

 
Hasse-diagram van de verzameling van alle delers van 60, partieel geordend op basis van deelbaarheid[1]

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.

GetallenverzamelingenBewerken

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  .

VoorbeeldBewerken

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  .

GrafenBewerken

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.

DeelverzamelingBewerken

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 ordeBewerken

InleidingBewerken

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.

DefinitieBewerken

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.

TralieBewerken

  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 ordeBewerken

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. Een datumnotatie als 21 maart 2020 is dat ook, op de volgorde van notatie na. 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. Voor een tekst met onderdelen met een nummering als 3.1.1, 3.2.1.5, enz.,[3] is de gebruikelijke volgorde van deze onderdelen overeenkomstig.

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.

Geordende vectorruimteBewerken

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:[4] Voor alle   met   en  , geldt

  1.  
  2.  

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  

AantallenBewerken

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[5] 12
OEIS A001035[6] A000112[7]

SpraakgebruikBewerken

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.