Partiële orde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
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.

Definitie[bewerken]

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

  • R reflexief is, dat wil zeggen xRx.
  • R antisymmetrisch is, dat wil zeggen: als xRy en yRx, dan x=y
  • R transitief is, dat wil zeggen: als xRy en yRz, dan ook xRz

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

Terminologie en notatie; inverse[bewerken]

De orderelatie R 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 a ≤ b dan en slechts dan als b ≥ a. 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 a is een voorganger van b als a\neq b,a\leq b.

zegt men wel voor a als op orderelatie "≥" kan worden toegepast, is bijvoorbeeld het gebruik van "R" voor de relatie, en A R B samen met A is niet B uit te drukken als "A is een voorganger van B" in plaats van "A is kleiner dan B". Dit zou echter ook neutrale termen vergen voor kleinste, grootste, infimum, supremum, minimaal, maximaal, en dergelijke.

Voorbeeld[bewerken]

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

  • x\geq x voor alle x\in \R,
  • x\geq y en y\geq x impliceert x = y,
  • x\geq y en y\geq z impliceert x \geq z.

Strikte partiële orde[bewerken]

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.

Definitie[bewerken]

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

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 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. De reflexieve afsluiting van een strikte partiële orde op X is een partiële orde op X.

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 R, dan wordt voor de betekenis van begrippen als "kleiner" uitgegaan van die welke hoort bij de notatie "≤" of "<".

Voor twee elementen a en b zijn er vier mogelijkheden: gelijk, kleiner, groter en onvergelijkbaar. Bij een totale orde komt de laatste niet voor.

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

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

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