Rozkład transformacji skończonej

Question

Dowolna permutacja na skończonym zbiorze może być wyrażona jako iloczyn rozłącznych cykli.
(https://groupprops.subwiki.org/wiki/Cycle_decomposition_theorem_for_permutations)

A co z transformacją (dowolną mapą zbioru na siebie)?
Czy można to wyrazić jako wynik pewnego rodzaju rozłącznych przemian?

Próbuję dostosować dowód z połączonego artykułu do transformacji:

Pozwolić $t$ być transformacją na skończonym zbiorze $T$.
Możemy wprowadzić moc żywiołu$a$ z $T$ w następujący sposób:

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

Podobnie jak w przypadku półgrup cyklicznych, możemy wprowadzić jądro elementu$T$. (https://en.wikipedia.org/wiki/Monogenic_semigroup)

Pozwolić $K_a$być jądro z$a$: $K_a = \{ a^{m}, a^{m+1}, ..., a^{m+r-1}\}$, gdzie $m$jest indeksem , a$r$jest okres od$a$.
Powiedzmy element$x$ z $T$ spada na$K_a$ jeśli istnieje nieujemna liczba całkowita $k$ takie że $x^k \in K_a$.
Oznaczmy zbiór wszystkich elementów$T$ które spadają na $K_a$ tak jak $F_a$.
$F_a$ wywołuje następującą transformację (nazwijmy to prostym ):

• $f_a(x) = t(x)$ Jeśli $x \in F_a$;
• $f_a(x) = x$ Jeśli $x \notin F_a$.

Oznaczmy zestaw dopełniający $F_a$ tak jak $\overline F_a$.
$\overline F_a$ wywołuje następującą przemianę:

• $\overline f_a(x) = t(x)$ Jeśli $x \in \overline F_a$;
• $\overline f_a(x) = x$ Jeśli $x \notin \overline F_a$.

Łatwo to sprawdzić $f_a$ i $\overline f_a$są rozłączne (https://math.stackexchange.com/q/3834607/427611).
Kontynuacja procesu dla$\overline F_a$, otrzymamy rozkład $t$na rozłączne proste przekształcenia.
Czy to jest poprawne?

Również transformacje są ściśle związane z półgrupami (https://planetmath.org/cayleystheoremforsemigroups).
Czy istnieje twierdzenie o rozkładzie półgrup na podgrupy elementów, które mają to samo jądro?

Przepraszam za własną terminologię: nie byłem w stanie znaleźć odpowiednich terminów.

Answer 1

Dowolna mapa $f : X \to X$ze zbioru skończonego do siebie ma „rozkład drzewa cykli”; jest to bardzo podstawowy i fundamentalny fakt, ale nieco szokująco znam tylko jedno odniesienie do tego, czyli Bergeron, Labelle i Lerouxhttp://bergeron.math.uqam.ca/Species/especes.html (Rozdział 3), a po przejrzeniu tego rozdziału jest mniej wyraźny i zawiera mniej szczegółów, niż jakoś pamiętam.

Tak to wygląda. $f$ma ostateczny obraz $\text{im}^{\infty}(f)$ które można opisać jako skrzyżowanie $\cap_n \text{im}(f^n)$. Elementy ostatecznego obrazu są dokładnie takie okresowe punkty z$f$a te rozkładają się na cykle, tak jak robią to permutacje. Pozostałe elementy$X$ które nie są okresowo trafione w okresowy punkt ostatecznie (przez szufladkę) i jeśli trajektoria dowolnych dwóch punktów zbiega się w jakimś $f^n$potem pokrywają się na zawsze, więc punkty nieokresowe organizują się w zakorzenione drzewa zakorzenione w dowolnym punkcie dowolnego cyklu. W szczególności „połączone komponenty” są podawane w każdym cyklu (i wszystkich dołączonych do niego drzewach)

Jest to rodzaj teorii mnogości, kuzyn postaci normalnej Jordana, gdzie punkty okresowe są analogiczne do wektorów własnych, a punkty nieokresowe są analogiczne do uogólnionych wektorów własnych. Jeśli znasz teorięhttps://en.wikipedia.org/wiki/Combinatorial_species można to elegancko wyrazić w następujący sposób (wszystkie zbiory są tutaj skończone): „endofunkcja to zbiór cykli zakorzenionych drzew” lub innymi słowy, gatunek endofunkcji to potrójna kompozycja $\text{End} = \text{Set} \circ \text{Cyc} \circ \text{Tree}$. Odpowiedni rozkład gatunków dla permutacji jest taki, że „permutacja jest zbiorem cykli”$\text{Perm} = \text{Set} \circ \text{Cyc}$. Ten rozkład daje między innymihttps://golem.ph.utexas.edu/category/2019/12/a_visual_telling_of_joyals_pro.html. Ten wpis na blogu zawiera obraz rozkładu drzewa cykli, który, mam nadzieję, pomoże:

Sprawa, że $X$jest nieskończony jest trudniejszy i nie zastanawiałem się nad tym szczegółowo. Jest teraz nowy rodzaj ograniczającego zachowania „w połowie nieskończony w prawo”$0 \to 1 \to 2 \to \dots$ to jest nieokresowe, ale zamiast tego „ucieka w nieskończoność” i nowy rodzaj drzewa „w połowie nieskończone w lewo” $\dots -2 \to -1 \to 0$które mogą być zasilane. Ostateczny obraz może być pusty. Nie jestem pewien, jaki jest najczystszy sposób opisania wszystkich możliwości.

Answer 2

Najlepszą referencją na ten temat jest [1]. Sekcja I.2, Wykres (częściowej) transformacji , omawia szczegółowo rozkład wykresów, o którym również wspomina odpowiedź Qiaochu Yuan. Możesz być także zainteresowany rozdziałem III, Generowanie systemów .

[1] Ganyushkin, Olexandr; Mazorczuk, Wołodymyr. Klasyczne półgrupy transformacji skończonej. Wstęp. Algebra and Applications, 9. Springer-Verlag London, Ltd., London, 2009. xii + 314 str. ISBN: 978-1-84800-280-7