Totale orde

In de wiskunde is een totale orde of lineaire orde een ordeningsrelatie op een verzameling die het meest lijkt op de ordening zoals die bekend is van de getallenrechte. Een verzameling met een dergelijke orde erop, heet een totaal geordende, of lineair geordende verzameling. Een totaal of lineair geordende verzameling kan, zoals de term lineair al doet vermoeden, voorgesteld worden als een rechte lijn of een deelverzameling daarvan, met aan de ene kant van een element de opvolgers ervan en aan de andere kant zijn voorgangers. Een totaal geordende verzameling wordt met betrekking tot de ordening wel aangeduid als keten.

Schematische weergave van een totale of lineaire orde. Merk op dat alleen de transitief-reflexieve reductie getoond wordt.

DefinitieBewerken

Een totale orde of lineaire orde op de verzameling   is een homogene tweeplaatsige relatie  , die antisymmetrisch, transitief en totaal is. Er geldt dus:

  • (antisymmetrie) voor alle   geldt: als   en  , dan  ,
  • (transitiviteit) voor alle   geldt: als   en  , dan  , en
  • (totaliteit) voor alle   geldt:   of   (of beide).

Strikte totale ordeBewerken

Bij elke totale orde   is er een bijbehorende relatie   die een strikte totale orde genoemd wordt en die gedefinieerd is door:

  •   dan en slechts dan als   en  

of alternatief door:

  •   dan en slechts dan als niet  

Omgekeerd is er bij elke strikte totale orde   een bijbehorende totale orde  , gedefinieerd door:

  •   dan en slechts dan als   of  

of alternatief door:

  •   dan en slechts dan als niet  

EigenschappenBewerken

  • De relatie   is transitief:   en   impliceert  .
  • De relatie   is een trichotomie, d.w.z. precies een van de relaties   en   is waar.
  • De relatie   is een strikte zwakke orde, met gelijkheid als de bijbehorende equivalentie.

Twee andere geassocieerde ordes zijn de complementen   en  , die het viertal   en   complementeren. Elk van deze vier orderelaties kan gebruikt worden om de totale orde op een verzameling te definiëren.

VoorbeeldenBewerken

  • De letters van het alfabet onder de alfabetische volgorde zijn totaal geordend.
  • Een deelverzameling van een totaal geordende verzameling   is zelf ook totaal geordend onder de restrictie van de orde op  .
  • Elke verzameling kardinaalgetallen of ordinaalgetallen is totaal geordend (deze zijn zelfs welgeordend).
  • Als   een verzameling is en   een injectieve functie die   afbeeldt op in een totaal geordende verzameling, induceert   een totale orde op   door de relatie   als  .
  • De reële getallen onder de gebruikelijke ordening   of   zijn totaal geordend. Dus zijn ook de deelverzamelingen de natuurlijke getallen, de gehele getallen en de rationale getallen totaal geordend. Tevens geldt:
    • de natuurlijke getallen vormen de kleinste totaal geordende verzameling zonder bovengrens;
    • de gehele getallen vormen de kleinste totaal geordende verzameling met geen boven- of ondergrens;
    • de rationale getallen vormen de kleinste totaal geordende verzameling die dicht ligt in de reële gtallen.

Minimum en maximumBewerken

De functie min geeft de kleinste waarde, het minimum, van haar argumenten aan; de functie max, het maximum, de grootste.

 
 

De functies kunnen ook meer argumenten hebben. Ook kunnen de argmumenten geïndiceerd zijn of afhangen van een parameter en is de index of de parameter beperkt tot bepaald bereik.

Het betekent steeds het kleinste en grootste element. Als de verzameling waarden oneindig groot is bestaan deze niet altijd.

De functies hebben de eigenschap dat toepassen van een monotoon niet-dalende functie op de argumenten hetzelfde oplevert als het toepassen van die functie op het resultaat. Bij een monotoon niet-stijgende functie verandert min in max en omgekeerd.

Zie ook inf en sup.

VoorbeeldenBewerken

 
 
 

VolgordeBewerken

Het alledaagse begrip volgorde correspondeert, in het geval van verschillende elementen, met een totale orde op de verzameling elementen. Bij bijvoorbeeld de volgorde waarin klanten worden geholpen gaat het dan wel om situaties waarin niet meerdere klanten tegelijk worden geholpen.

Bij de volgorde van de elementen van een multiset, bijvoorbeeld de volgorde van de cijfers in een getal, gaat dit niet op. Voor bijvoorbeeld het getal 112 zijn de andere getallen met dezelfde cijfers 121 en 211, samen drie mogelijkheden, terwijl dit aantal volgordes niet voorkomt bij verzamelingen.

Zie ookBewerken