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.