WikiDer > Zyklischer Auftrag

In dem Ordnungstheorie, Teil von dem Mathematik, ist ein zyklische Ordnung oder zyklische Ordnung auf einer Sammlung ${Anzeigestil V}$ ein schwer zu definierender Begriff. Solange es endlich viele Elemente gibt ${Anzeigestil V}$ kann als Punkte auf a dargestellt werden Kreis, wobei man als nächster Punkt immer den Nachfolger findet und auf alle Elemente stößt.

Vor dem endliche Mengen kann a zyklische Ordnung wahrgenommen werden als bijektivBild${displaystyle f}$ von ${Anzeigestil V}$ auf ${Displaystil V.}$ Ein solches Bild fügt jedem Element seinen Nachfolger hinzu. Ohne die Forderung, dass ausgehend von einem der Elemente die ganze Menge durchlaufen werden muss, entsteht nur eine partielle zyklische Ordnung, bestehend aus einem oder mehreren Fahrräder von aufeinander folgenden Elementen. Gibt es nur einen Zyklus, dann heißt der Auftrag zyklisch. Dazu ist Folgendes erforderlich:

${Anzeigestil {f^{k}(v)|k=1,ldots,n}=V}$ für eine zufällige ${displaystyle vin V,}$

in welchem ${displaystyle n}$ die Anzahl der Elemente von ${Anzeigestil V}$ ist.

Es ist nicht schwer zu erkennen, dass ausgehend von jedem anderen Element dann die gesamte Kollektion durchlaufen wird.

Diese Art der Definition einer zyklischen Ordnung kann nicht für nicht endliche Mengen verallgemeinert werden. Denn wenn für jedes Element einer Abzählbarkeit ein solcher Nachfolger existierte unendliche Sammlung${Anzeigestil V,}$ es erzeugt einen Countdown durch die Wahl eines Elements ${Anzeigestil v}$ und:

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

In diesem Countdown, der Vorgänger von ${Anzeigestil v}$ verhindern, sagen wir ${Anzeigestil f^{-1}(v)=v_{m}.}$ Aber dann ${displaystyle v_{m 1}=v,}$ was bedeutet, dass es nur eine endliche Anzahl von Nachfolgern geben würde.

Dennoch erlaubt eine unendliche Menge ein Konzept der "zyklischen Ordnung". Die Menge ist beispielsweise ein Kreis oder eine unendliche Teilmenge davon. Die Reihenfolge "im Uhrzeigersinn" bedeutet dann, dass drei verschiedene Punkte a, b und c in dieser Reihenfolge liegen, falls einer im Uhrzeigersinn von ${Anzeigestil a}$ zu ${Anzeigestil c}$ Geh ${displaystyle b}$ Begegnungen vor eins ${Anzeigestil c}$ ist. Allgemeiner kann man eine zyklische Ordnung einer Menge finden ${Anzeigestil V}$ definiere durch eine Bijektion von ${Anzeigestil V}$ zu einer Teilmenge eines Kreises (a Injektion von ${Anzeigestil V}$ zu einem Kreis).

Dies führt zu der folgenden Definition, die für endliche Mengen dem obigen Konzept des "Nachfolgers" entspricht.

Definition

EIN zyklische Ordnung auf einer Sammlung ${Anzeigestil V}$ ist ein Drei-Wege-Beziehung${displaystyle Rsubset V^{3},}$ was der Einfachheit halber als ${Anzeigestil abc=R(a,b,c),}$ wofür:

1. ${displaystyle abcRechtspfeil a,b,c}$ anders
2. ${Anzeigestil a,b,c}$ anders ${displaystyle Abclor nach rechts acb}$
3. ${displaystyle innot(abcland acb)}$
4. ${displaystyle abcland acdRightarrow bcd}$
5. ${displaystyle abcRightarrow bca}$

Bemerkungen:

• Anforderung 1 bedeutet, dass nur unterschiedliche Elemente miteinander verglichen werden.
• Anforderungen 2 und 3 bedeuten, dass von den beiden Wegen durch ein Trio zu gehen nur eine der Reihenfolge entspricht: wenn man ${Anzeigestil a}$ zu ${Anzeigestil c}$ geht, einer kommt oder ${displaystyle b}$ gegen für einen bei ${Anzeigestil c}$ ist, oder erst danach ${Anzeigestil c}$, einer von zwei.
• Anforderung 4 bedeutet, dass von ${Anzeigestil a}$ gesehen ${displaystyle b}$ für und ${displaystyle d}$ hinter ${Anzeigestil c}$ Lügen.
• Bedingung 5 schließlich macht die Beziehung zyklisch.

Logischerweise sollte 4 auch zu führen ${displaystyle abd}$ sind in dieser Reihenfolge. Angenommen, die Folge ist: ${displaystyle-adb}$, Desweiteren ${Bad im Anzeigestil}$. Zusammen mit ${displaystyle abc}$, So ${displaystyle bca}$, gibt das über Eigenschaft 5 zurück: ${Anzeigestil-CAD}$. Aber das widerspricht ${displaystyle-acd}$.

Äquivalenz für endliche Mengen

Für eine endliche Menge entspricht diese letzte Definition der Definition über eine "Nachfolger"-Funktion. wenn ${Anzeigestil V}$${displaystyle n}$ hat Elemente und ${displaystyle f}$ bedeutet Nachfolger, wir definieren die ternäre Relation ${Anzeigestil R}$ auf offensichtliche Weise durch:

${displaystyle abcLeftarrow Rightarrow b=f^{k}(a)Land c=f^{m}(b)Land 0$

Dies bedeutet, dass 1 automatisch erfüllt ist. wenn ${Anzeigestil a, b}$ und ${Anzeigestil c}$ anders sein ist:

${displaystyle b=f^{k}(a)Land c=f^{m}(b)Land 0$

So

${displaystyle kmRightarrow acb,}$

wodurch ${Anzeigestil R}$ trifft 2 und 3. Außerdem folgt:

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

so dass ${displaystyle bca,}$ weil

${displaystyle c=f^{m}(b)land m$

Somit ist auch 5 erfüllt. wie neben ${displaystyle abc}$ ebenfalls ${displaystyle-acd}$ gilt ist:

${Anzeigestil d=f^{r}(a),;r>mk}$.

Daraus folgt direkt die Forderung in 4: ${displaystyle bcd}$.

Umgekehrt für ein endliches ${Anzeigestil V}$ mit mindestens 3 Elementen (sonst trivial) in zyklischer Reihenfolge ${Anzeigestil R}$ eine Nachfolgeposition ${displaystyle f}$ definiert sein durch for ${Anzeigestil f(a)}$ das Element ${displaystyle b}$ für was nehmen ${displaystyle abc}$ und keine ${Anzeigestil v}$ ist mit ${displaystyle avb}$. Die Funktion ${displaystyle f}$ ist injektiv und weil ${Anzeigestil V}$ endlich ist also bijektiv, denn angenommen:

${Anzeigestil f(a)=f(b)=c,d=f(c)Pfeil nach rechts und bcd}$,

so muss ${displaystyle abc}$ oder ${displaystyle bac}$, aber das widerspricht der Definition von ${Anzeigestil f.}$