Partiële orde

Schematische weergave 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

Een tweeplaatsige relatie   op een verzameling   heet een partiële ordening op   als

  •   reflexief is, dat wil zeggen  .
  •   antisymmetrisch is, dat wil zeggen: als   en  , dan  
  •   transitief is, dat wil zeggen: als   en  , dan ook  

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).

Terminologie en notatie; inverseBewerken

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 partiële orde " " genoemd en is zelf ook een partiële orde.

Definities van termen als kleinste, grootste, infimum, supremum, minimaal, maximaal worden steeds gedaan uitgaande van een relatie met de terminologie en notatie van " ". Deze toepassen op een relatie met de terminologie en notatie van " " zou verwarring geven; waarschijnlijk bedoelt men dan de definities toe te passen op de inverse.

In plaats van de notatie " ", gelezen als "kleiner of gelijk", voor de orderelatie, gebruikt men wel de neutrale aanduiding   is een voorganger van   als  .

VoorbeeldBewerken

Op de reële getallen   is de relatie " " (groter dan of gelijk aan) een partiële ordening, immers:

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

DeelverzamelingBewerken

Als   een partiële orde is op een verzameling   en   is een deelverzameling van   dan definieert de restrictie van   tot  

 

een partiële orde op  .

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

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

 [1]

Strikte partiële ordeBewerken

Bij een partiële orde behoort altijd een overeenkomstige relatie die niet reflexief is. In plaats van de relatie "groter dan of gelijk aan" geldt alleen de ordening "groter dan". Een dergelijke ordening noemt men een strikte partiële orde.

DefinitieBewerken

Een tweeplaatsige endorelatie " " op de verzameling   heet een strikte partiële orde, als " " asymmetrisch en transitief is. (Asymmetrie betekent dat niet zowel   en   waar kan zijn, dus, als  , dan niet  .)

Merk op dat een strikte partiële orde geen partiële orde is. Sommige auteurs noemen een partiële orde zoals hier genoemd, een zwakke partiële orde.

Asymmetrie impliceert bovendien irreflexiviteit. Een strikte partiële orde kan ook gedefinieerd worden als een irreflexieve, transitieve tweeplaatsige endorelatie, omdat irreflexiviteit en transitiviteit samen asymmetrie impliceren.

Er is een een-op-een-correspondentie 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  . Verder is het zo dat de inverse van deze een-op-een-correspondentie 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  .

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 symbolen en de bijbehorende termen 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 onvergelijkbaar. Bij een totale orde komt de laatste niet voor.

Soms wordt in plaats van "  is kleiner dan  " wel gezegd "  komt vóór  " of "  is een voorganger van  ".

TralieBewerken

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

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 chronologische). 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.[2], 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:[3] 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  

Afwijkend gebruik van de uitdrukking "niet te vergelijken"Bewerken

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

Zie ookBewerken