Zerlegung einer endlichen Transformation

Question

Jede Permutation auf einer endlichen Menge kann als Produkt disjunkter Zyklen ausgedrückt werden.
((https://groupprops.subwiki.org/wiki/Cycle_decomposition_theorem_for_permutations)

Was ist mit einer Transformation (eine beliebige Karte einer Menge auf sich selbst)?
Kann es als Produkt disjunkter Transformationen bestimmter Art ausgedrückt werden?

Ich versuche, den Beweis aus dem verlinkten Artikel an Transformationen anzupassen:

Lassen $t$ eine Transformation auf einer endlichen Menge sein $T$.
Wir können die Kraft eines Elements einführen$a$ von $T$ auf die folgende Weise:

• $a^0 = a$,
• $a^{n+1} = t(a^n)$.

Ähnlich wie bei zyklischen Halbgruppen können wir den Kern eines Elements von einführen$T$. (https://en.wikipedia.org/wiki/Monogenic_semigroup)

Lassen $K_a$sei der Kern von$a$:: $K_a = \{ a^{m}, a^{m+1}, ..., a^{m+r-1}\}$, wo $m$ist der Index und$r$ist der Zeitraum von$a$.
Sagen wir ein Element$x$ von $T$ fällt auf$K_a$ wenn es eine nicht negative ganze Zahl gibt $k$ so dass $x^k \in K_a$.
Bezeichnen wir die Menge aller Elemente von$T$ das fällt auf $K_a$ wie $F_a$.
$F_a$ induziert die folgende Transformation (nennen wir es einfach ):

• $f_a(x) = t(x)$ wenn $x \in F_a$;;
• $f_a(x) = x$ wenn $x \notin F_a$.

Bezeichnen wir die Komplementmenge von $F_a$ wie $\overline F_a$.
$\overline F_a$ induziert die folgende Transformation:

• $\overline f_a(x) = t(x)$ wenn $x \in \overline F_a$;;
• $\overline f_a(x) = x$ wenn $x \notin \overline F_a$.

Das lässt sich leicht überprüfen $f_a$ und $\overline f_a$sind disjunkt (https://math.stackexchange.com/q/3834607/427611).
Fortsetzung des Prozesses für$\overline F_a$werden wir eine Zerlegung von bekommen $t$auf disjunkte einfache Transformationen.
Ist das richtig?

Transformationen sind auch eng mit Halbgruppen verbunden (https://planetmath.org/cayleystheoremforsemigroups).
Gibt es einen Satz zur Zerlegung von Halbgruppen in Unterhalbgruppen von Elementen, die denselben Kernel teilen?

Ich entschuldige mich für meine eigene Terminologie: Ich konnte nicht die richtigen Begriffe finden.

Answer 1

Eine beliebige Karte $f : X \to X$von einer endlichen Menge zu sich selbst hat eine "Zyklusbaumzerlegung"; Dies ist eine sehr grundlegende und fundamentale Tatsache, aber etwas schockierend. Ich kenne nur eine einzige Referenz dafür, nämlich Bergeron, Labelle und Lerouxhttp://bergeron.math.uqam.ca/Species/especes.html (Kapitel 3), und nachdem ich mich in diesem Kapitel umgesehen habe, ist es weniger explizit und enthält weniger Details, als ich mich irgendwie erinnere.

Es geht so. $f$hat ein letztendliches Bild $\text{im}^{\infty}(f)$ was als Schnittpunkt beschrieben werden kann $\cap_n \text{im}(f^n)$. Die Elemente des endgültigen Bildes sind genau die periodischen Punkte von$f$und diese zerlegen sich wie Permutationen in Zyklen. Die restlichen Elemente von$X$ die nicht periodisch sind, treffen irgendwann einen periodischen Punkt (durch eine Schublade), und wenn die Flugbahn von zwei beliebigen Punkten jemals bei einigen zusammenfällt $f^n$danach fallen sie für immer zusammen, sodass sich die nichtperiodischen Punkte in verwurzelten Bäumen organisieren, die an jedem Punkt eines der Zyklen verwurzelt sind. Insbesondere werden die "verbundenen Komponenten" durch jeden Zyklus (und alle damit verbundenen Bäume) angegeben.

Dies ist eine Art satztheoretischer Verwandter der jordanischen Normalform, bei der die periodischen Punkte analog zu Eigenvektoren und die nichtperiodischen Punkte analog zu verallgemeinerten Eigenvektoren sind. Wenn Sie mit der Theorie von vertraut sindhttps://en.wikipedia.org/wiki/Combinatorial_species es kann elegant wie folgt ausgedrückt werden (alle Mengen sind hier endlich): "Eine Endofunktion ist eine Menge von Zyklen verwurzelter Bäume", oder mit anderen Worten, die Art der Endfunktionen ist eine dreifache Zusammensetzung $\text{End} = \text{Set} \circ \text{Cyc} \circ \text{Tree}$. Die entsprechende Artenzerlegung für Permutationen ist, dass "eine Permutation eine Menge von Zyklen ist"$\text{Perm} = \text{Set} \circ \text{Cyc}$. Diese Zersetzung ergibt unter anderem:https://golem.ph.utexas.edu/category/2019/12/a_visual_telling_of_joyals_pro.html. Dieser Blog-Beitrag enthält ein Bild einer Zyklusbaumzerlegung, die hoffentlich helfen wird:

Der Fall, dass $X$ist unendlich ist schwieriger und ich habe nicht so detailliert darüber nachgedacht. Es gibt jetzt eine neue Art von einschränkendem Verhalten "halb unendlich nach rechts".$0 \to 1 \to 2 \to \dots$ das ist nicht periodisch, sondern "entkommt ins Unendliche" und eine neue Baumart "halb unendlich nach links" $\dots -2 \to -1 \to 0$das kann einspeisen. Das eventuelle Bild ist möglicherweise leer. Ich bin mir nicht sicher, wie ich hier alle Möglichkeiten am saubersten beschreiben kann.

Answer 2

Die beste Referenz zu diesem Thema ist [1]. Abschnitt I.2, Diagramm einer (Teil-) Transformation , behandelt ausführlich die Diagrammzerlegung, die auch in der Antwort von Qiaochu Yuan erwähnt wurde. Vielleicht interessieren Sie sich auch für Kapitel III, Generieren von Systemen .

[1] Ganyushkin, Olexandr; Mazorchuk, Volodymyr. Klassische endliche Transformationshalbgruppen. Eine Einleitung. Algebra und Anwendungen, 9. Springer-Verlag London, Ltd., London, 2009. xii + 314 S. ISBN: 978-1-84800-280-7