Cyclische orde

In de ordetheorie, een onderdeel van de wiskunde, is een cyclische orde of cyclische ordening op een verzameling $V$ een ordening van de elementen van $V$, zodat zij een cirkel vormen. Een cyclische ordening van een verzameling $V$ kan als een bijectie van $V$ naar een deelverzameling van een cirkel worden gedefinieerd. Als $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: $x_{1}\leq x_{2}\leq \ldots \leq x_{n}\leq x_{1}$, waarin '$\leq$' de relatie tussen twee opeenvolgende elementen $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 $x\leq y$ als $y\leq x$, dan $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.

Definitie als opvolgersafbeelding

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 $($lente zomer herfst winter$)$, 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:

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

waarin $n$ het aantal elementen van $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 $V,$ brengt deze een aftelling voort door de keuze van een element $v$ en:

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

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

Cyclische orde op een oneindige verzameling

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 $a,b$ en $c$ in die volgorde staan in het geval dat als men met de klok mee van $a$ naar $c$ gaat, men $b$ tegenkomt voor men bij $c$ is. Dit leidt tot de volgende definitie, die voor eindige verzamelingen equivalent is met het bovengenoemde begrip "opvolger".

Definitie

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

1. $abc\Rightarrow a,b,c$ verschillend
2. $a,b,c$ verschillend $\Rightarrow abc\lor acb$
3. $\lnot (abc\land acb)$
4. $abc\land acd\Rightarrow bcd$
5. $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 $a$ naar $c$ gaat, komt men of $b$ tegen voor men bij $c$ is, of pas na $c$, een van tweeën.
• Eis 4 betekent dat vanuit $a$ gezien $b$ voor en $d$ achter $c$ ligt.
• Eis 5 ten slotte maakt de relatie tot een cyclische.

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

Equivalentie voor eindige verzamelingen 

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

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

Daarmee is dan vanzelf aan 1 voldaan.

Als $a,b$ en $c$ verschillend zijn, is:

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

dus

hetzij $\ k<m\Rightarrow abc\$ hetzij $\ k>m\Rightarrow acb$

waarmee $R$ aan 2 en 3 voldoet.

Tevens volgt:

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

zodat $bca$ want

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

Daarmee is ook aan 5 voldaan.

Als behalve $abc$ ook $acd$ geldt, is:

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

Daaruit volgt het in 4 geëiste: $bcd$

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

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

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