Loading AI tools
Van Wikipedia, de vrije encyclopedie
In de wiskunde houdt de ordetheorie zich bezig met de verschillende manieren om de elementen van een verzameling te sorteren, ze in een gekozen volgorde te kunnen plaatsen. Daartoe wordt de volgorde vastgelegd als een relatie tussen twee elementen die aangeeft welke van de elementen opvolger is van het andere. Kenmerkend voor een dergelijke orde is dat die transitief is. Er worden in de ordetheorie vormen van orde beschreven, waarin nog niet alle elementen volledig zijn gesorteerd. De vier meest voorkomende vormen van orde zijn de totale orde, de partiële orde, de totale preorde en de preorde. De elementen zijn in een totale orde volledig gesorteerd, maar in een preorde is er alleen nog maar een eerste ordening.
Deel van een serie artikelen over Wiskunde | ||||
---|---|---|---|---|
Formules van een stochastisch proces | ||||
Kwantiteit | ||||
Complex getal · Geheel getal · Natuurlijk getal · Oneindigheid · Reëel getal · Rekenkunde | ||||
Structuur en ruimte | ||||
Algebra · Functie · Getaltheorie · Goniometrie · Groepentheorie · Meetkunde · Topologie | ||||
Verandering | ||||
Analyse · Chaostheorie · Differentiaalrekening · Dynamische systemen · Vectoren | ||||
Toegepaste wiskunde | ||||
Discrete wiskunde · Grafentheorie · Informatietheorie · Kansrekening · Statistiek · Wiskundige natuurkunde | ||||
|
De elementen van een te sorteren verzameling kunnen dus wel worden geordend, hun onderlinge volgorde kan worden bepaald. Die onderlinge volgorde wordt erdoor bepaald welk element een opvolger van welk element is. Dat kan door middel van een tweeplaatsige relatie. De elementen kunnen niet door hun plaats in de verzameling worden bepaald, anders was het geen verzameling maar een rij. Er moet bij het sorteren onder andere op worden gelet, dat er cirkels in de te sorteren verzameling ontstaan. De cyclische orde is ervoor gedefinieerd om te kunnen onderkennen dat dit in een verzameling het geval is en wordt daartoe als een ternaire relatie gedefinieerd.
Een bekend voorbeeld is de ordening van de gehele getallen. Van twee verschillende getallen is steeds een van beide kleiner dan het andere. Men noteert bijvoorbeeld 3 < 7 voor de relatie 'kleiner dan' tussen de getallen 3 en 7. Er zijn ook andere vormen van ordening, zoals in het spel 'steen, papier, schaar', waarin de volgorde tussen de elementen, aangegeven door <, of zwakker, cyclisch van aard is: steen < papier < schaar < steen, waarna men weer bij het begin is.
Een orde wordt meestal gedefinieerd door een homogene tweeplaatsige relatie.
De duidelijkste vorm van ordening is de totale orde. Twee elementen in een verzameling met een totale orde kunnen altijd met elkaar worden vergeleken. Een totale orde kan opgevat worden als een keten van elementen, waarvan van elk tweetal geldt dat ofwel het eerste vóór het tweede komt, ofwel het tweede vóór het eerste. Een totale orde wordt ook lineaire orde genoemd. De gehele getallen zoals hierboven is aangegeven, vormen een verzameling met een totale ordening. Op de verzameling met vier elementen is bijvoorbeeld de relatie een totale orde,[1] evenals iedere andere permutatie van de elementen.
In een partiële orde kunnen elementen voorkomen die niet met elkaar kunnen worden vergeleken. Als we natuurlijke getallen ordenen door deelbaarheid dan ontstaat bijvoorbeeld een partiële orde. Zo is in die partiële orde 10 kleiner dan 30 omdat 30 door 10 kan worden gedeeld, maar zijn 30 en 12 niet met elkaar te vergelijken, omdat geen van beide door de ander kan worden gedeeld. Op de verzameling met zes elementen is bijvoorbeeld de relatie en een partiële orde. Een tralie is verzameling met een partiële orde waarvan iedere eindige deelverzameling zowel een supremum als een infimum heeft. Een hasse-diagram is een grafische afbeelding van een eindige verzameling met een partiële orde.
Een totale preorde, of zwakke orde, onderscheidt zich er van een totale orde in, dat er equivalente elementen in kunnen voorkomen. Een totale preorde is een preorde waarin van elke twee niet equivalente elementen een van beide kleiner is dan het andere. Een totale preorde staat net als een partiële orde tussen de preorde en de totale orde in. In het ene opzicht is een totale preorde sterker, in een ander opzicht zwakker dan een partiële orde. Het gebruikelijke symbool om een totale preorde aan te geven is hetzelfde als voor een preorde in het algemeen, dat is .
Een preorde is een nog ruimer begrip dan een partiële orde en een totale preorde. In een preorde kunnen elementen en voorkomen die niet met elkaar vergeleken kunnen worden, of die van elkaar verschillen, maar equivalent geacht worden, dat wil zeggen dat ze op dezelfde plaats in de ordening staan. De relatie is te omschrijven als 'kleiner of equivalent' in plaats van 'kleiner of gelijk'. Het gebruikelijke symbool om een preorde aan te geven is , dat de symbolen voor kleiner en equivalent combineert. Een preorde is reflexief en transitief. Een preorde op een verzameling wordt gekarakteriseerd door een partitie van die verzameling waarvan de klassen partieel zijn geordend.
De nevenstaande figuur toont de samenhang tussen de verschillende ordes: totale orde, partiële orde, totale preorde en preorde. De pijlen geven aan 'is een bijzonder geval van'.
De totale preorden op een verzameling corresponderen één op één met het geheel van de totale orden op de partities van de verzameling. De preorden op een verzameling corresponderen één op één met het geheel van de partiële orden op de partities van de verzameling.
Bijbehorende irreflexieve ordesoorten zijn de strikte totale orde, de strikte partiële orde, en de bij de totale preorde behorende strikte zwakke orde, een ondersoort van de strikte partiële orde. Voor de preorde in het algemeen is er niet zo'n bijbehorende soort.
Voor elke definitie en stelling in de ordetheorie is er een inverse, waarbij termen als kleinste, grootste, infimum, supremum, minimaal en maximaal kunnen worden vervangen door de tegenhanger, met bijbehorende vervanging van tekens als '<' door het tegengestelde of verwisseling van de operanden. Een dergelijke inverse is een tegenovergestelde categorie.
Evenzo kan men in toepassingen een orde omgekeerd definiëren. Soms is een van beide mogelijkheden voor de hand liggend en de andere verwarrend, maar in andere gevallen is deze willekeurig. Op een traject van via en naar kan men '<' definiëren als 'is dichter bij dan', dan geldt , maar even goed als 'is dichter bij dan', dan geldt .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.