Формулировка и доказательство теоремы Крона - Роудза.

Для того чтобы дать точную формулировку теоремы Крона - Роудза, необходимо ввести понятие делимости для полугрупп.

Будем говорить, что полугруппа преобразований (X, S) делит (У, Т): (Х, S) | (У, Т) тогда и только тогда, когда: -существуют подмножество У' множества У и подполугруппа Т' полугруппы Т, такие, что У' инвариантно относительно действия Т'. -существуют отображение 0: Y' X (-"->- обозначает отображение "на") и эпиморфизм ф: T'-*-S, такие, что Q(yt) = Q(y)f(t) для всех г/ е У' и t<=T'.

Реализация данной системы (автомата) при помощи подсистем (автоматов) осуществляется в соответствии с делением полугрупп. Теперь можем сформулировать основную задачу, имеющую непосредственное отношение к теореме Крона - Роудза.

Задача
Если X - пространство состояний, на котором действует конечная полугруппа преобразований то можно ли найти декомпозицию (X, в подполугруппы
преобразований (.Xk, GV), k-\, ..п, такие, что будет получено минимальное решение (X, @~*) \{Хп, G'n) w ¦.. w(Xi, Gj), и если можно, то
каковы структура компонент (Х{, G}) и максимальное значение п? На языке теории автоматов соответствующая задача является факторизацией конечного автомата в наибольшее возможное число автоматов, и ее решение дается так называемой простой декомпозицией первоначального автомата. Прежде чем перейти к формулировке теоремы Крона - Роудза, введем такие понятия, как полугруппа триггера и примарная группа.

Пусть афЬ. Рассмотрим полугруппу ({а, Ь), {Са, Сь, Id}), где хСа = а, хСь = Ь, xld = x для х = а или х~Ъ, которую будем записывать также в виде ({a, b}, U3). Полугруппа ({a, b}, Uг) называется полугруппой триггера порядка три.

Связность структуры больших систем
Конечная группа G примарна, если она простая1), G ф - {Id}. Если S - полугруппа, тогда Primes(S) = {G : G примарна и GJS}.

Теорема примарной декомпозиции для конечных полугрупп, или теорема Крона - Роудза
Пусть (X, ЗГ*) заданная конечная полугруппа. Тогда существует декомпозиция её в узловое произведение (ЛТЬ GI), ..(Хп, Gn), такая, что (х, rr\(xn, G*n)w...w(xl, с;), и для каждого фактора (Xt, G]) либо G) е Primes (^г*), (XI, G'j) - транзитивная группа перестановок, либо (X,, GJ) = ({a, b},U3). Сравнивая эту теорему с теоремой Жордана - Гёльдера, можно заметить, что
теория полугрупп эквивалентна теории конечных групп, дополненной "триггерной" операцией.