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.

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.

Definitie 
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 orde 
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 .

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

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

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

Minimum en maximum 
Een eindige totaal geordende verzameling heeft een kleinste en een grootste element, aangeduid als minimum  voor het kleinste en maximum  voor het grootste.
 is de waarde  waarvoor , voor alle 
 is de waarde  waarvoor , 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.

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

Termen 'voldoende groot' en 'uiteindelijk' 
Bij een oneindige totaal geordende verzameling  waarop een eigenschap  is gedefinieerd, wordt 'voor voldoend grote  in  geldt ', ook geformuleerd als 'uiteindelijk geldt ', gedefinieerd als 

Dit wordt vooral toegepast bij verzamelingen reële getallen, waaronder verzamelingen natuurlijke getallen. Bij natuurlijke getallen kan het ook geformuleerd worden als 'voor alle  op een eindig aantal na geldt '.

Voorbeelden:
 Elk voldoende groot priemgetal is een zesvoud plus of min 1. / Uiteindelijk zijn de priemgetallen een zesvoud plus of min 1.
 Uiteindelijk zijn de kwadraten van de priemgetallen een 24-voud plus 1.
 Uiteindelijk zijn de faculteiten van natuurlijke getallen een tienvoud.
 Elk voldoende groot oneven natuurlijk getal kan geschreven worden als de som van drie priemgetallen (stelling van Vinogradov).

Websites 
 Ely Bendersky. Partial and Total Orders, 1 oktober 2018.

Ordetheorie