Totale orde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Schematische weergave van een totale of lineaire orde. Merk op dat alleen de transitief-reflexieve reductie getoond wordt.

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.

Definitie[bewerken]

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 orde[bewerken]

Bij elke totale orde ≤ is er een bijbehorende asymmetrische (dus niet-reflexieve) 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

Eigenschappen[bewerken]

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

Voorbeelden[bewerken]

  • 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 rationele getallen vormen de kleinste totaal geordende verzameling die dicht ligt in de reële gtallen.

Minimum en maximum[bewerken]

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.

Voorbeelden[bewerken]

Zie ook[bewerken]