Partiële ordening

Een partiële ordening op een verzameling is een binaire relatie die reflexief, antisymmetrisch en transitief is.

In de meeste gevallen noteren we de partiële ordening met het \(\boldsymbol{\preceq}\) symbool en soms met het \(\boldsymbol{\le}\) symbool.

Dus, voor een verzameling \(X\) is \(\preceq\) een partiële ordening op \(X\) als

1. Voor iedere \(x\in X\): \(x\preceq x\);
2. Voor alle \(x,y\in X\): als \(x\preceq y\) en \(y\preceq x\), dan \(x=y\);
3. Voor alle \(x,y,z\in X\): als \(x\preceq y\) en \(y\preceq z\), dan \(x\preceq z\).

Een partiële ordening \(\preceq\) noemen we een totale ordening of lineaire ordening op \(X\) als voor alle \(x,y\in X\) geldt dat \(x\preceq y\) of \(y\preceq x\), of beide.

Voorbeelden

De relatie "is kleiner dan of gelijk aan" op de verzameling van reële getallen is een totale ordening.

De relatie "is groter dan of gelijk aan" op de verzameling van reële getallen is een totale ordening.

De relatie "is deler van" op de verzameling \(\mathbb{N}\backslash\{0\}\) is partiële ordening. Dit is geen totale ordening omdat bijvoorbeeld \(2\) geen deler is van \(5\), maar \(5\) ook geen deler is van \(2\).

De relatie "is deler van" op de verzameling \(\{1,2,4,8\}\) is een totale ordening.

De relatie "is een deelverzameling van" op de machtsverzameling \({\Large\wp}(X)\) van een zekere verzameling \(X\) is een partiële ordening. Dit is geen totale ordening, tenzij \(X\) de lege verzameling is of maar één element bevat.

Onder- en bovengrenzen

Stel \(X\) is een verzameling met een partiële ordening \(\preceq\), en \(S\subset X\).

• \(y\in X\) heet een bovengrens van \(S\) als \(x\preceq y\) voor alle \(x\in S\).
• \(z\in X\) heet een kleinste bovengrens of supremum van \(S\), genoteerd als \(z=\mathrm{sup}(S)\), als \(z\) een bovengrens is van \(S\) en bovendien voor iedere (andere) bovengrens \(y\) van \(S\) geldt dat \(z\preceq y\).
• Analoog heet \(y\in X\) heet een ondergrens van \(S\) als \(y\preceq x\) voor alle \(x\in S\).
• \(z\in X\) heet een grootste ondergrens of infimum van \(S\), genoteerd als \(z=\mathrm{inf}(S)\), als \(z\) een ondergrens is van \(S\) en bovendien voor iedere (andere) ondergrens \(y\) van \(S\) geldt dat \(y\preceq z\).

Als er een supremum of infimum van \(S\) bestaat, dan is deze uniek.

Voorbeeld

We bekijken de partiële ordening "is deler van" op de verzameling \(X=\{1,2,3,4,6,8,9,12,18,24\}\).

Voor \(S=\{4,6\}\) zijn \(1\) en \(2\) de ondergrenzen van \(S\) en \(\mathrm{inf}(S)=2\). De getallen \(12\) en \(24\) zijn bovengrenzen van \(S\) en \(\mathrm{sup}(S)=24\).

Voor \(S=\{3,4,6\}\) is \(1\) de enige ondergrens van \(S\) en dus \(\mathrm{inf}(S)=1\). De getallen \(12\) en \(24\) zijn de bovengrenzen van \(S\) en \(\mathrm{sup}(S)=12\).

Voor \(S=\{4,6,9\}\) is \(1\) de enige ondergrens van \(S\) en dus \(\mathrm{inf}(S)=1\). Er bestaat geen bovengrens van \(S\).