Ordetheorie

(Doorverwezen vanaf Ordening (wiskunde))

In de wiskunde houdt de ordetheorie zich bezig met de verschillende manieren op basis waarvan objecten in een gegeven verzameling in een volgorde geplaatst kunnen worden. Daartoe wordt voor de definitie van de volgorde, van de ordening tussen de elementen van die verzameling een tweeplaatsige relatie of in het geval van een cyclische orde bijvoorbeeld een drieplaatsige relatie met kenmerkende eigenschappen tussen de elementen van eenzelfde verzameling als leidraad genomen.

Deel van een serie artikelen over

Analyse van "Galton-Watson-model" aan de hand van wiskundige vergelijkingen.
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 · Calculus · Chaostheorie · Dynamisch systeem · Vectoren


––– Toegepaste wiskunde –––

Discrete wiskunde · Grafentheorie · Informatietheorie · Kansrekening · Statistiek · Wiskundige fysica


Portaal Portaalicoon Wiskunde

VoorbeeldBewerken

Een bekend voorbeeld is de ordening van 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.

Soorten orde gedefinieerd door een tweeplaatsige relatieBewerken

Voor precieze definities, zie de aparte artikelen.
Totale orde

De sterkste vorm van ordening is de totale orde. 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.

Partiële orde

Een zwakkere vorm is de partiële orde. 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.

Totale preorde

De totale preorde of zwakke orde genoemd, staat net als de partiële orde tussen de preorde en de totale orde en is in het ene opzicht sterker, in het andere zwakker dan de partiële orde. Het gebruikte symbool om een tweeplaatsige relatie met totale preorde aan te geven is  .

  • De complexe getallen vormen een verzameling met een totale preorde. Twee complexe getallen kunnen met elkaar worden vergeleken door hun absolute waarde met elkaar te vergelijken.   en  .
Preorde

Een nog zwakkere vorm is de preorde, die zoals de naam al aangeeft geen orde is, maar bijna een partiële orde. Verschillende elementen   en   kunnen in een preorde voorkomen, waarvan ieder 'kleiner of gelijk' aan het andere is. Hetzelfde symbool wordt weer gebruikt. De tweeplaatsige relatie die de elementen in een verzameling met preorde bepaalt is reflexief en transitief:

  •  , reflexief en
  •   transitief.

Een verzameling met een totale orde is een verzameling met preorde, waarin de tweeplaatsige relatie die de preorde bepaalt antisymmetrisch is:

  •  

Voorbeelden:

  • De knopen in een gerichte graaf vormen een verzameling met een preorde, door te stellen dat voor twee knopen   en   de relatie   in de graaf bestaat, als er een gericht pad van   naar   bestaat.


OverigeBewerken

Cyclische orde

Er bestaat daarnaast nog de cyclische orde, die men zich kan voorstellen als een orde op een cirkel. Op een cirkel met drie plaatsen   en   ligt het element   linksom voor  ,   voor  , maar   weer voor  .

Strikte zwakke orde

Het complement van een strikte zwakke orde is een totale preorde en omgekeerd. Voor de tweeplaatsige relatie die een verzameling met strikte zwakke orde bepaalt geldt het volgende:

  •   met   en   dan  , of natuurlijk beide.