Cyclische orde
In de ordetheorie, een onderdeel van de wiskunde, is een cyclische orde of cyclische ordening op een verzameling een ordening van de elementen van , zodat zij een cirkel vormen. Een cyclische ordening van een verzameling kan als een bijectie van naar een deelverzameling van een cirkel worden gedefinieerd. Als 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: , waarin '' de relatie tussen twee opeenvolgende elementen 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 als , dan . 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:
- voor een willekeurige
waarin het aantal elementen van 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 brengt deze een aftelling voort door de keuze van een element en:
- .
In die aftelling moet de voorganger van voorkomen, zeg Maar dan is 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 en in die volgorde staan in het geval dat als men met de klok mee van naar gaat, men tegenkomt voor men bij 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 is een ternaire relatie die wordt genoteerd als waarvoor geldt:
- verschillend
- verschillend
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 naar gaat, komt men of tegen voor men bij is, of pas na , een van tweeën.
- Eis 4 betekent dat vanuit gezien voor en achter ligt.
- Eis 5 ten slotte maakt de relatie tot een cyclische.
Eis 4 moet ook als gevolg hebben. Dat volgt uit het ongerijmde. Stel namelijk dat de volgorde is: , dus ook . Samen met , dus , levert dat via eigenschap 5: . Maar dat is in tegenspraak met .
Voor een eindige verzameling is deze de laatste definitie equivalent met de definitie via een functie 'opvolger'. Als uit elementen bestaat en betekent opvolger, definiëren we de ternaire relatie op voor de hand liggende wijze, door:
- er zijn en , zodat en en en , waarbij er geen is, , zodat ook
Daarmee is dan vanzelf aan 1 voldaan.
Als en verschillend zijn, is:
- en en en en en en
dus
- hetzij hetzij
waarmee aan 2 en 3 voldoet.
Tevens volgt:
zodat want
- en
Daarmee is ook aan 5 voldaan.
Als behalve ook geldt, is:
- en
Daaruit volgt het in 4 geëiste:
Omgekeerd kan voor een eindige met ten minste drie elementen, anders is het triviaal, bij een cyclische ordening een opvolgerfunctie gedefinieerd worden door voor het element te nemen, waarvoor en er geen is met . De functie is injectief en omdat eindig is dus bijectief, want stel:
- en en ,