Cyclische orde

In de ordetheorie, een onderdeel van de wiskunde, is een cyclische orde of cyclische ordening op een verzameling ${\displaystyle V}$ een ordening van de elementen van ${\displaystyle V}$, zodat zij een cirkel vormen. Een cyclische ordening van een verzameling ${\displaystyle V}$ kan als een bijectie van ${\displaystyle V}$ naar een deelverzameling van een cirkel worden gedefinieerd. Als ${\displaystyle V}$ maar eindig veel elementen heeft, kunnen die voorgesteld worden als aparte punten op een cirkel, waarbij men steeds als volgend punt de opvolger aantreft en alle elementen tegenkomt. Een cirkel van elementen kan bijvoorbeeld als volgt worden genoteerd: ${\displaystyle x_{1}\leq x_{2}\leq \ldots \leq x_{n}\leq x_{1}}$, waarin '${\displaystyle \leq }$' de relatie tussen twee opeenvolgende elementen ${\displaystyle x_{i}}$ geeft. Een deelverzameling van een reële getallenverzameling kan gegeven de relatie, die de waarde van twee getallen met elkaar vergelijkt, dus nooit cyclisch zijn.

Wanneer aan een verzameling met een bepaalde ordening de voorwaarde wordt gesteld, dat die antisymmetrisch is, kunnen er in de ordening geen cykels voorkomen. Een relatie heet antisymmetrisch als zowel ${\displaystyle x\leq y}$ als ${\displaystyle y\leq x}$, dan ${\displaystyle x=y}$. Er kunnen in een verzameling met een totale orde of met een partiële orde daarom geen cykels voorkomen, maar in een verzameling met een totale preorde is binnen een equivalentieklasse elke rij elementen te sluiten tot een cirkel.

Voor eindige verzamelingen kan een cyclische orde opgevat worden als homogene tweeplaatsige relatie in de vorm van een permutatie. Zo'n afbeelding voegt aan ieder element een opvolger toe, en kan worden genoteerd in cykelnotatie, bijvoorbeeld ${\displaystyle (}$lente zomer herfst winter${\displaystyle )}$, zonder komma's. Zonder de eis dat uitgaande van een van de elementen de hele verzameling doorlopen moet worden, ontstaat slechts een partiële cyclische ordening, bestaande uit een of meer cykels van elkaar opvolgende elementen. Is er maar één cykel, dan heet de hele ordening cyclisch. Daartoe wordt geëist dat:

${\displaystyle V=\{f^{k}(v)|k=1,\ldots ,n\}}$ voor een willekeurige ${\displaystyle v\in V,}$

waarin ${\displaystyle n}$ het aantal elementen van ${\displaystyle V}$ is. Uitgaande van ieder ander element wordt ook de hele verzameling doorlopen.

Deze manier om een cyclische orde te definiëren kan niet gegeneraliseerd worden voor niet-eindige verzamelingen. Als namelijk zo'n opvolger zou bestaan voor elk element in een aftelbaar oneindige verzameling ${\displaystyle V,}$ brengt deze een aftelling voort door de keuze van een element ${\displaystyle v}$ en:

${\displaystyle v_{n}=f^{n}(v)}$.

In die aftelling moet de voorganger van ${\displaystyle v}$ voorkomen, zeg ${\displaystyle f^{-1}(v)=v_{m}.}$ Maar dan is ${\displaystyle v_{m+1}=v,}$ wat inhoudt dat er maar eindig veel opvolgers zouden zijn.

Voor oneindige verzamelingen is het ook mogelijk een cyclische ordening te definiëren. De verzameling is bijvoorbeeld een cirkel of een oneindige deelverzameling daarvan. De ordening 'met de klok mee' houdt dan in dat drie verschillende punten ${\displaystyle a,b}$ en ${\displaystyle c}$ in die volgorde staan in het geval dat als men met de klok mee van ${\displaystyle a}$ naar ${\displaystyle c}$ gaat, men ${\displaystyle b}$ tegenkomt voor men bij ${\displaystyle c}$ is. Dit leidt tot de volgende definitie, die voor eindige verzamelingen equivalent is met het bovengenoemde begrip "opvolger".

Een cyclische orde op een verzameling ${\displaystyle V}$ is een ternaire relatie ${\displaystyle R\subset V^{3},}$ die wordt genoteerd als ${\displaystyle abc=R(a,b,c),}$ waarvoor geldt:

1. ${\displaystyle abc\Rightarrow a,b,c}$ verschillend
2. ${\displaystyle a,b,c}$ verschillend ${\displaystyle \Rightarrow abc\lor acb}$
3. ${\displaystyle \lnot (abc\land acb)}$
4. ${\displaystyle abc\land acd\Rightarrow bcd}$
5. ${\displaystyle abc\Rightarrow bca}$

Opmerkingen:

• Eis 1 houdt in dat alleen verschillende elementen met elkaar worden vergelijken.
• Eisen 2 en 3 betekenen dat van de twee manieren om door een drietal heen te lopen er maar een volgens de ordening is: als men van ${\displaystyle a}$ naar ${\displaystyle c}$ gaat, komt men of ${\displaystyle b}$ tegen voor men bij ${\displaystyle c}$ is, of pas na ${\displaystyle c}$, een van tweeën.
• Eis 4 betekent dat vanuit ${\displaystyle a}$ gezien ${\displaystyle b}$ voor en ${\displaystyle d}$ achter ${\displaystyle c}$ ligt.
• Eis 5 ten slotte maakt de relatie tot een cyclische.

Eis 4 moet ook ${\displaystyle abd}$ als gevolg hebben. Dat volgt uit het ongerijmde. Stel namelijk dat de volgorde is: ${\displaystyle adb}$, dus ook ${\displaystyle bad}$. Samen met ${\displaystyle abc}$, dus ${\displaystyle bca}$, levert dat via eigenschap 5: ${\displaystyle cad}$. Maar dat is in tegenspraak met ${\displaystyle acd}$.

Equivalentie voor eindige verzamelingen 

Voor een eindige verzameling is deze de laatste definitie equivalent met de definitie via een functie 'opvolger'. Als ${\displaystyle V}$ uit ${\displaystyle n}$ elementen bestaat en ${\displaystyle f}$ betekent opvolger, definiëren we de ternaire relatie ${\displaystyle R}$ op voor de hand liggende wijze, door:

${\displaystyle abc\quad \Leftrightarrow \quad }$ er zijn ${\displaystyle n,k}$ en ${\displaystyle m\in \mathbb {N} }$, zodat ${\displaystyle a=f^{n}(a)}$ en ${\displaystyle b=f^{k}(a)}$ en ${\displaystyle c=f^{m}(b)}$ en ${\displaystyle 0<k+m<n}$, waarbij er geen ${\displaystyle i<n}$ is, ${\displaystyle i\in \mathbb {N} }$, zodat ook ${\displaystyle a=f^{i}(a)}$

Daarmee is dan vanzelf aan 1 voldaan.

Als ${\displaystyle a,b}$ en ${\displaystyle c}$ verschillend zijn, is:

${\displaystyle b=f^{k}(a)}$ en ${\displaystyle c=f^{m}(b)}$ en ${\displaystyle 0<k}$ en ${\displaystyle 0<m}$ en ${\displaystyle k\neq m}$ en ${\displaystyle (k}$ en ${\displaystyle m<n)}$

dus

hetzij ${\displaystyle \ k<m\Rightarrow abc\ }$ hetzij ${\displaystyle \ k>m\Rightarrow acb}$

waarmee ${\displaystyle R}$ aan 2 en 3 voldoet.

Tevens volgt:

${\displaystyle a=f^{-k}(b)=f^{n-k}(b)}$

zodat ${\displaystyle bca}$ want

${\displaystyle c=f^{m}(b)}$ en ${\displaystyle m<n-k}$

Daarmee is ook aan 5 voldaan.

Als behalve ${\displaystyle abc}$ ook ${\displaystyle acd}$ geldt, is:

${\displaystyle d=f^{r}(a)}$ en ${\displaystyle r>m+k}$

Daaruit volgt het in 4 geëiste: ${\displaystyle bcd}$

Omgekeerd kan voor een eindige ${\displaystyle V}$ met ten minste drie elementen, anders is het triviaal, bij een cyclische ordening ${\displaystyle R}$ een opvolgerfunctie ${\displaystyle f}$ gedefinieerd worden door voor ${\displaystyle f(a)}$ het element ${\displaystyle b}$ te nemen, waarvoor ${\displaystyle abc}$ en er geen ${\displaystyle v}$ is met ${\displaystyle avb}$. De functie ${\displaystyle f}$ is injectief en omdat ${\displaystyle V}$ eindig is dus bijectief, want stel:

${\displaystyle f(a)=f(b)=c}$ en ${\displaystyle d=f(c)\Rightarrow acd}$ en ${\displaystyle bcd}$,

dus moet ${\displaystyle abc}$ of ${\displaystyle bac}$. Dat is in strijd met de definitie van ${\displaystyle f}$, want als ${\displaystyle abc}$ is ${\displaystyle f(a)\neq c}$ en als ${\displaystyle bac}$ is ${\displaystyle f(b)\neq c}$.