Totale orde

Voorbeeld van een strikte 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 $X$ met een totale orde ieder paar van elementen van $X$ met elkaar kan worden vergeleken. Een totale orde op een verzameling bepaalt een totale relatie. Van het viertal $\leq$, $<$, $\geq$ en $>$ volgen dus weer uit elk eenduidig de overige drie.

Definitie

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

• antisymmetrie: voor alle $x,y\in X$ geldt: als $x\leq y$ en $y\leq x$, dan $x=y$,
• transitiviteit: voor alle $x,y,z\in X$ geldt: als $x\leq y$ en $y\leq z$, dan $x\leq z$, en
• totaliteit: voor alle $x,y\in X$ geldt: $x\leq y$ of $y\leq x$, of beide.

Het is door de antisymmetrie onmogelijk, dat er in $X$ een cykel bestaat, die door de relatie $\leq$ is bepaald. Er is dus geen cirkel van elementen $x_{i}\in X$ met $x_{1}\leq x_{2}\leq \ldots \leq x_{n}\leq x_{1}$.

Strikte totale orde

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

$x<y$, als $x\leq y$ en $x\neq y$

of alternatief door:

$x<y$, als $y\not \leq x$

Omgekeerd is er bij elke strikte totale orde $<$ een bijbehorende totale orde $\leq$, gedefinieerd door:

$x\leq y$, als $x<y$ of $x=y$

of alternatief door:

$x\leq y$, als $y\not <x$

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 $X$ heet asymmetrisch, als voor alle $x,y\in X$ met $x<y$ geldt: $y\not <x$ en ze heet connex als voor alle $x,y\in X$ geldt dat $x<y$, $y<x$ of $x=y$. Een strikte totale orde is asymmetrisch, transitief en connex.

Er is een bijectie tussen alle totale ordes op een verzameling $X$ en alle strikte totale ordes op dezelfde verzameling $X$, die verkregen wordt door iedere totale orde af te beelden op zijn reflexieve reductie. Van iedere totale orde op $X$ is zijn reflexieve reductie namelijk een strikte totale orde op $X$. Deze wordt ook de bijbehorende strikte totale orde genoemd. De reflexieve reductie van een totale orde op $X$ 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 $X$ is een totale orde op $X$. 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 $\geq$.

Eigenschappen

• De relatie $<$ is transitief: $x<y$ en $y<z$ impliceert $x<z$.
• De relatie $<$ is een trichotomie, dus is precies een van de relaties $x<y,\ y<x$ en $x=y$ waar.
• De relatie $<$ is een strikte zwakke orde, met gelijkheid als de bijbehorende equivalentie.

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

Voorbeelden

• Op de aftelbare verzameling $X=\{x_{1},x_{2},\ldots \}$ met $x_{i}\neq x_{j}{\text{ voor }}i\neq j$ wordt een totale orde gedefinieerd door de elementen te ordenen naar hun plaats in de aftelling, dus $x_{i}\leq x_{i+1}$. Iedere permutatie van de elementen bepaalt een nieuwe totale orde op $X$, die alle onderling isomorf zijn.
• De letters van het alfabet onder de alfabetische volgorde zijn totaal geordend.
• Een deelverzameling van een totaal geordende verzameling $X$ is zelf ook totaal geordend onder de restrictie van de orde op $X$.
• Elke verzameling kardinaalgetallen of ordinaalgetallen is totaal geordend, deze zijn zelfs welgeordend.
• Als $X$ een verzameling is en $f$ een injectieve functie die $X$ afbeeldt op in een totaal geordende verzameling, bepaalt $f$ een totale orde op $X$ door $x<y$ te nemen als $f(x)<f(y)$.
• De reële getallen onder de gebruikelijke ordening $\leq$ of $\geq$ 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 $X$ met ten minste twee elementen is ook geen verzameling met een totale orde. Neem twee elementen $a$ en $b$ van $X$, dan is noch ${a}\subset {b}$, noch ${b}\subset {a}$

Minimum en maximum

Een eindige totaal geordende verzameling heeft een kleinste en een grootste element, aangeduid als minimum ($\min$) voor het kleinste en maximum ($\max$) voor het grootste.

$\min(\{a_{1},\ldots ,a_{n}\})$ is de waarde $a_{j}$ waarvoor $a_{j}\leq a_{i}$, voor alle $i$

$\max(\{a_{1},\ldots ,a_{n}\})$ is de waarde $a_{k}$ waarvoor $a_{k}\geq a_{i}$, voor alle $i$

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 $X$ is een totale orde op $X$ met de eigenschap dat elke niet-lege deelverzameling van $X$ 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 $V$ waarop een eigenschap $P$ is gedefinieerd, wordt 'voor voldoend grote $x$ in $V$ geldt $P(x)$', ook geformuleerd als 'uiteindelijk geldt $P(x)$', gedefinieerd als

$\exists a\in V:\forall x\in V:x\geq a\Rightarrow P(x)$

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

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.