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 getallenlijn. Totale orde is een begrip uit de ordetheorie. Een verzameling met daarop een totale orde heet een totaal geordende, of lineair geordende verzameling. Een dergelijke 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.

Voorbeeld van een strikte totale orde.

Een totale orde is een speciaal geval van een partiële orde, namelijk dat in een verzameling met een totale orde ieder paar van elementen van met elkaar kan worden vergeleken. Een totale orde op een verzameling bepaalt een totale relatie. Van het viertal , , en volgen dus weer uit elk eenduidig de overige drie.

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.

Het is door de antisymmetrie onmogelijk, dat er in   een cykel bestaat, die door de relatie   is bepaald. Er is dus geen cirkel van elementen   met  .

Strikte totale ordeBewerken

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

 , als   en  

of alternatief door:

 , als  

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

 , als   of  

of alternatief door:

 , als  

Merk op dat een strikte totale orde geen totale orde is omdat ze niet reflexief en daarom niet totaal is. Een relatie   op een verzameling   heet asymmetrisch, als voor alle   met   geldt:   en ze heet connex als voor alle   geldt dat  ,   of  . Een strikte totale orde is asymmetrisch, transitief en connex.

Er is een bijectie tussen alle totale ordes op een verzameling   en alle strikte totale ordes op dezelfde verzameling  , die verkregen wordt door iedere totale orde af te beelden op zijn reflexieve reductie. Van iedere totale orde op   is zijn reflexieve reductie namelijk een strikte totale orde op  . Deze wordt ook de bijbehorende strikte totale orde genoemd. De reflexieve reductie van een totale orde op   is geen equivalentierelatie, maar nog wel transitief. Verder is het zo dat de inverse van deze bijectie een strikte totale orde op zijn reflexieve afsluiting afbeeldt. De reflexieve afsluiting van een strikte totale orde op   is een totale orde op  . Deze wordt ook de bijbehorende totale orde genoemd. De strikte totale orderelatie wordt meestal genoteerd als  , en wordt dan wel 'kleiner dan' genoemd. De inverse wordt dan genoteerd   en 'groter dan' genoemd. Het is zelf ook een strikte totale orde, en de reflexieve reductie van  .

EigenschappenBewerken

  • De relatie   is transitief:   en   impliceert  .
  • De relatie   is een trichotomie, dus is precies een van de relaties   en   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

  • Op de aftelbare verzameling   met   wordt een totale orde gedefinieerd door de elementen te ordenen naar hun plaats in de aftelling, dus  . Iedere permutatie van de elementen bepaalt een nieuwe totale orde op  , die alle onderling isomorf zijn.
  • 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, bepaalt   een totale orde op   door   te nemen 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.

TegenvoorbeeldenBewerken

  • De relatie 'kan worden gedeeld door' op de natuurlijke relatie is geen relatie met een totale orde. Er zijn koppels getallen getallen, waarin noch het eerste door het tweede, noch het tweede door het eerste getal kan worden gedeeld.
  • De machtsverzameling van een verzameling   met tenminste twee elementen is ook geen verzameling met een totale orde. Neem twee elementen   en   van  , dan is noch  , noch  

Minimum en maximumBewerken

Een eindige totaal geordende verzameling heeft een kleinste en een grootste element, aangeduid als minimum ( ) voor het kleinste en maximun ( ) voor het grootste.

 , voor alle  
 , voor alle  

Als de verzameling oneindig groot is, bestaan deze niet altijd. Bij een verzameling reële getallen geldt dat als deze naar beneden of naar boven begrensd is, respectievelijk het infimum of het supremum bestaat.

Een welordening op een verzameling   is een totale orde op   met de eigenschap dat elke niet-lege deelverzameling van   in deze ordening een kleinste element heeft.

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 maar één klant tegelijk wordt 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. Dit zijn de andere twee volgordes van de multiset  1,1,2 , samen drie mogelijkheden, terwijl dit aantal volgordes niet voorkomt bij verzamelingen.

WebsitesBewerken