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 "$\leq$", 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

Algebraïsche structuren met onderling een partiële orde

Een partiële orde op een verzameling $V$ is een homogene tweeplaatsige relatie $\leq$ op $V$ die reflexief, transitief en antisymmetrisch is. Dat houdt in dat voor alle $x,y,z\in V$ geldt:

• reflexiviteit: $x\leq x$
• transitiviteit: als $x\leq y$ en $y\leq z$, dan ook $x\leq z$
• antisymmetrie: als $x\leq y$ en $y\leq x$, dan $x=y$

Het is door de antisymmetrie onmogelijk, dat er gegeven de relatie $\leq$ een cykel in $V$ bestaat, dus dat er elementen $x_{i}\in X$ zijn met $x_{1}\leq x_{2}\leq \ldots \leq x_{n}\leq x_{1}$.

De verzameling $V$ 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 $R$ wordt meestal genoteerd als $\leq$ en wordt dan wel genoemd 'kleiner dan of gelijk aan'. Er is een bijbehorende orderelatie $\geq$, 'groter dan of gelijk aan', zo dat $a\leq b$ dan en slechts dan als $b\geq a$. Deze wordt de inverse van de orde $\leq$ 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 $\leq$, gelezen als 'kleiner of gelijk', ook dat $a$ een 'voorganger' van $b$ is als $a\neq b,a\leq b$.

Voorbeeld

De relatie $\leq$, 'kleiner dan of gelijk aan', bepaalt op de complexe getallen $\mathbb {C}$ een partiële ordening, namelijk voor zover het de reële getallen $\mathbb {R}$ betreft, immers:

• $x\leq x$ voor alle $x\in \mathbb {R}$,
• $x\leq y$ en $y\leq x$ impliceert $x=y$ voor alle $x,y\in \mathbb {R}$,
• $x\leq y$ en $y\leq z$ impliceert $x\leq z$ voor alle $x,y,z\in \mathbb {R}$.

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 $\leq$ op een verzameling $V$ bepaalt op natuurlijke wijze een partiële orde op een deelverzameling $W$ van $V$ door de restrictie van $\leq$ tot $W$. Als voor twee elementen $a,b\in W$ geldt: $a\leq b$, dan is ook in de restrictie $a\leq b$.

Een keten van een orderelatie $R$ is een deelverzameling $W\subset V$ zodat de restrictie $R|W$ een totale orde is.

Een antiketen is een deelverzameling $W\subset V$ zodat de restrictie $R|W$ alleen lussen bevat, d.w.z.

$R|W=\{(w,w)\mid w\in W\}$

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 $a=b$, 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 $a$ kunnen voorkomen met $aRa$ en in een asymmetrische relatie niet.

Een homogene tweeplaatsige relatie $<$ op de verzameling $X$ 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 $X$ en alle strikte partiële ordes op dezelfde verzameling $X$, die verkregen wordt door iedere partiële orde af te beelden op zijn reflexieve reductie. Van iedere partiële orde op $X$ is zijn reflexieve reductie namelijk een strikte partiële orde op $X$. 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 $X$ is een partiële orde op $X$. 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 $\geq$.

Van het viertal $\leq$, $<$, $\geq$ 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 $R$, dan wordt voor de betekenis van begrippen als kleiner uitgegaan van die welke hoort bij de notatie $\leq$ of $<$.

Voor twee elementen $a$ en $b$ 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 $\leq$ op het cartesisch product $A\times B$ van twee partieel geordende verzamelingen $A$ en $B$ wordt gedefinieerd als

$(a,b)\leq (a',b')$ dan en slechts dan als $a<a'$ of $(a=a'$ en $b\leq b')$.

Het resultaat is een partiële orde. Als $A$ en $B$ 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. Voor een tekst met onderdelen met een nummering als 3.1.1, 3.2.1.5, enz., is de gebruikelijke volgorde van deze onderdelen overeenkomstig.

Geordende vectorruimte

Een vectorruimte $V$ over het lichaam $\mathbb {R}$ der reële getallen heet geordend, als ze voorzien wordt van een partiële orde $\leq$ die op de volgende manieren de vectorruimtebewerkingen respecteert: Voor alle $u,v,w\in V$ met $u\leq v$ en $\lambda \in \mathbb {R} ,\ \lambda \geq 0$, geldt

1. $u+w\leq v+w$
2. $\lambda u\leq \lambda v$

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 $f$ en $g$ geldt dan $f\leq g$ als voor iedere $x$ in het domein $f(x)\leq g(x).$

Aantallen

Aantal mogelijke partiële ordes op een verzameling met $n$ elementen

$n$	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	12
OEIS	A001035	A000112

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.

voetnoten

literatuur

• (en) Bourbaki, Nicolas (1994), Elements of the History of Mathematics. Springer.
• (en) Russell, Bertrand (1903/1938), The Principles of Mathematics, 2nd ed.. Cambridge University Press.