Cyclische orde - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Cyclische orde.

Cyclische orde

Uit Wikipedia, de vrije encyclopedie

In de ordetheorie, een onderdeel van de wiskunde, is een cyclische orde of cyclische ordening op een verzameling een lastig algemeen precies te definiëren begrip. Als er maar eindig veel elementen in zijn, kunnen die voorgesteld worden als punten op een cirkel, waarbij men rechtsomgaand steeds als volgend punt de opvolger aantreft en alle elementen tegenkomt.

Voor eindige verzamelingen kan een cyclische orde opgevat worden als een bijectieve afbeelding van op Zo'n afbeelding voegt aan elk element z'n opvolger toe. 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 ordening cyclisch. Daartoe wordt geëist dat:

voor een willekeurige

waarin het aantal elementen van is.

Het is niet moeilijk in te zien dat dan ook uitgaande van elk ander element de hele verzameling doorlopen wordt.

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.

Toch laat een oneindige verzameling wel een begrip "cyclische ordening" toe. 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 naar gaat, men tegenkomt voor men bij is. Meer algemeen kan men een cyclische ordening van een verzameling definiëren via een bijectie van naar een deelverzameling van een cirkel (een injectie van naar een cirkel).

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 drieplaatsige relatie die voor het gemak even genoteerd wordt als waarvoor geldt:

  1. verschillend
  2. 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.

Logischerwijze moet 4 ook als gevolg hebben dat in die volgorde liggen. Stel namelijk dat de volgorde is: , dus ook . Samen met , dus , levert dat via eigenschap 5: . Maar dat is in tegenspraak met .

Equivalentie voor eindige verzamelingen

Voor een eindige verzameling is deze de laatste definitie equivalent met de definitie via een functie "opvolger". Als elementen heeft en betekent opvolger, definiëren we de ternaire relatie op voor de hand liggende wijze, door:

Daarmee is dan vanzelf aan 1 voldaan. Als en verschillend zijn, is:

dus

waarmee aan 2 en 3 voldoet. Tevens volgt:

zodat want

Daarmee is ook aan 5 voldaan. Als naast ook geldt, is:

.

Daaruit volgt direct het in 4 geëiste: .

Omgekeerd kan voor een eidige met ten minste 3 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:

,

dus moet of , maar dat is in strijd met de definitie van

{{bottomLinkPreText}} {{bottomLinkText}}
Cyclische orde
Listen to this article