Дискретно-непрерывная математика (стр. 92 )

гдеи где

1) ht является тождественным на

и

3) h3 является тождественным на Отметим,

что элементы с всегда встречаются в паре.

2.11. Лемма. Пусть S— полугруппа. Тогда

Доказательство. Будем вести доказательство по индукции отно­сительно Если то S — или группа, или комбинаторная полугруппа. Если S — группа, то

Если S — комбинаторная полугруппа, то S делит узловое произведе­ние полугрупп U3. Мы покажем, что РР (Sf)s есть комбинаторная по­лугруппа. Пусть U3 (длина полугруппы S) есть наименьшее целое п, такое, что (п раз). Предположим, что U3 (длина полу-

группы S) равна 1. Тогда S|U3, поэтому. Далее есть комбина­торная полугруппа, поэтому будет также комбинаторной полугруппой. Тогда основываясь на изложенном ранее и пользуясь соотношением (1) и методом индукции относительно U3 — длины, нетрудно доказать, что полугруппа будет комбинаторной тогда и только тогда, когда комбинаторной будет полугруппа S. Сле­довательно,

утверждение справедливо.

Предположим, что утверждение справедливо для Пусть

теперь Тогда существуют полугруппы S1 и S2, такие, что

и

Пустьнапомним, что Теперь и из соотношения (1) получаем,

чтогде С1 и С2 — комбинаторные полугруппы. По предположению индукции имеем

Тогда или или

В обоих случаях

2.12. Следствие.

Доказательство. Так как имеем

Неравенство в другую сторону получено согласно лемме 2.11.

2.13. Замечание. Вспомним некоторые важные свойства полугрупп, представляющих собой объединение групп (см. предложение 2.24 из микромодуля 8). Пусть S — такая полугруппа. Каждый класс полугруппы S будет простой полугруппой и отношение эквивалентности F будет конгруэнтностью. Если являются F классами полугруппы S, эпиморфизм, ассоциированный с конгруэнтностью F, можно пред­ставить как эпиморфизм θ из S на М = ({1, ..., п), *), где операция * определяется следующим образом: еслито есть коммутативная связка.

2.14. Определение. Комбинаторным идеалом полугруппы будем называть идеал, максимальные подгруппы которого тривиальны.

2.15. Теорема (основная лемма для сложности). Пусть S— полу­группа, являющаяся объединением групп с комбинаторным идеалом I. Тогда

Доказательство. Для того чтобы сделать более ясными обозначения, предположим, что комбинаторный идеал обозначается символом К, вместо I. S — К есть объединение F классов полугруппы S; зануме­руем эти F классы J1, ..., Jп-1 так, что неравенство Ji> Jj влечет i<j. Тогда, поскольку каждый F класс полугруппы S есть подполу­группа, легко видеть, что упорядоченный набор из п членов (J1, ..., ..., Jn-1, К) будет системой для S.

Введем автоматы

следующим образом. ПустьТогда

Для большей прозрачности дадим явное индуктивное определение. Если имеет длину 1, т. е., например, α = s1 то для i = 1, ..., п

(2а)

Пусть теперь Тогда для i =1, ..., п

(2б)

Заметим, что для Fn (α) случай 3 не может возникнуть.

Теперь легко проверить следующее соотношение для автоматов:

(2.3)

где (п раз) — диагональное отображение, т. е.

и отображение задается соотношением

Из равенства (3) следует, что

(2.4)

Теперь запишем для Fn соотношение, включающее идеал К и авто­маты а именно

(2.5а)

Эторавенство легко проверить. Здесь и для

и

Тогда

и, так как—комбинаторные полугруппы, имеем

Поэтому в силу соотношения (4) получаем

(2.5б)

Теперь приступим к основному этапу доказательства теоремы и пока­жем, что

(2.6)

Применяя соотношение (6) к формуле (5б), получим теорему.

Сейчас будет построен комбинаторный автомат Mi, i =1, ..., п, который содержит след состояния автомата Fi. Более точно , Mi: ∑S →{i, ..., п, 1} — комбинаторный автомат, который будет по зна­чению Mi(α) определять, какой случай соотношения (2) для Fi(α) выполняется (α ∑S).

2.16. Определение. Пусть для i = 1, ..., п.

Определим автомат