Partiële orde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Schematische weergave van een partiële orde

Een partiële orde of partiële ordening is een tweeplaatsige relatie (genoteerd als ≤) die reflexief, anti-symmetrisch en transitief is.

Definitie[bewerken]

Zij R een relatie op een verzameling V. Dan is R een partiële ordening op V als

  • R reflexief is, dat wil zeggen x R x.
  • R antisymmetrisch is, dat wil zeggen: als x R y en y R x, dan x=y
  • R transitief is, dat wil zeggen: x R y en y R z impliceert x R z

V is dan een partieel geordende verzameling, in Engelstalige wetenschappelijke publicaties vaak verkort tot poset (van partially ordered set).

Voorbeeld[bewerken]

Zij V = \mathbb{R} (de reële getallen) en R de relatie "≥" (groter dan of gelijk aan). R is een partiële ordening op V:

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

Strikte partiële orde[bewerken]

Een tweeplaatsige endorelatie < op X is dan en slechts dan een strikte partiële orde als < asymmetrisch en transitief is. Asymmetrie impliceert bovendien irreflexiviteit. Een strikte partiële orde kan ook gedefinieerd worden als een irreflexieve, transitieve tweeplaatsige endorelatie, want irreflexiviteit en transitiviteit samen asymmetrie impliceren.

Er is een een-op-een-correspondentie 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. Verder is het zo dat de inverse van deze een-op-een-correspondentie strikte partiële ordes afbeeldt op hun reflexieve afsluiting.[1] De reflexieve afsluiting van een strikte partiële orde op X is een partiële orde op X. Merk op dat de inverse van het complement van een partiële orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte partiële orde < de reflexieve afsluiting van < is.

De inverse van een partiële orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een partiële orde. De inverse van een strikte partiële orde < wordt vaak genoteerd als > en is zelf ook een strikte partiële orde. Het complement van een partiële orde is een strikte partiële orde en vice versa.

Tralie[bewerken]

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

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

Lexicografische orde[bewerken]

De lexicografische ordening \le op het Cartesisch product A\times B van twee partieel geordende verzamelingen A en B wordt gedefinieerd als

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

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

De lexicografische ordening kan analoog ook worden gedefinieerd voor meer dan twee verzamelingen.

De naam is ontleend aan een bekende toepassing: het ordenen van woorden (alfabetische volgorde) op basis van de volgorde van letters in het alfabet.

Zie ook[bewerken]

Voetnoten

  1. N.B. In het algemeen is het niet zo dat voor een tweeplaatsige endorelatie R geldt dat (R) = = R.

Bronnen

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