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

Доказательство. Мы должны доказать, что удовлетворяет ак­сиомам 1, 2 и 3 (определение 1.2). Ранее было показано, что слож­ность удовлетворяет аксиоме 1.

Сейчас с помощью нескольких лемм мы докажем, что функция удовлетворяет аксиоме 3.

2.6. Обозначения. Напомним определение сложности полугруппы S. В принятой системе обозначений из равенства С (S) = (п, G), например, следовало, что все минимальные разложения S в узловые произведения имели длину п, причем первая координата (справа) была групповой. Предположим, что п — четное число. Тогда эквивалентное обозначение для С (S) должно быть (С, п); если п нечетное, то Таким образом, мы вводим

а именно:

Изменение обозначений вызвано ранее определенной частичной упорядоченностью.

Наконец, мы переходим к новым обозначениям для операции сложе­ния сложностей. Например,

2.7. Лемма. Пусть S ≠ {0} будет GM полугруппой, отмеченный F класс которой есть объединение групп.. Если S ≠ G0 для некоторой группы G, то С (S) = (G, п) для некоторого п. Конечно,

Доказательство. Пусть J —отмеченный F класс полугруппы S. По условию J есть объединение групп, тогда согласно пункту б) утверж-дения 2.23 из микромодуля 9, если S содержит нуль, то S— {0} будет подполу­группой полугруппы S. Следовательно, вообще S# = S0—{0} будет подполугруппой полугруппы S. Заметим, что S# есть GM полугруппа с отмеченным идеалом J, являющимся ядром полугруппы S#.

Сначала докажем, что если и С — комбинатор-

ная полугруппа, то S#|T. Можно считать, что Теперь

пусть тогда

Можно утверждать, что это следует из построения

минимального γ гомоморфного образа (см. предложение 3.12 и предло­жение 3.4 из микромодуля 9). Из замечания 3.13 в микромодулt 9 известно, что если R S, то Учитывая все эти факты, мы видим, что Но отображение проекции будет γ гомоморфизмом, поэтому

Теперь легко видеть, что С(S#) должна оканчиваться группой, т. е. для некоторого п ≥ 1. В противном случае мы получим противоречие. Теперь или , или Но если S# не является группой.

2.8. Лемма. Пусть S ≠{0} будет RLM полугруппой. Тогда С(S)=(С, п) для некоторого п ≥ 1, т. е. RLM полугруппа оканчивается

комбинаторной полугруппой.

Доказательство. Предположим, что или

Тогда существуют группа преобразований (Х2, G) и моноид Т, такие, чтогдеТогда отображение будет L гомоморфизмом и, следовательно, L ' гомоморфизмом (см. предложение 3.24 из микромодуля 9). Тогда и,

поэтому Но так как S есть RLM полугруппа. Следовательно, S|T, поэтому, предполагая, что для некоторого n ≥ 1, мы приходим к противоречию. Лемма доказана.

2.9. Лемма. Пусть S ≠ {0} и S есть GM полугруппа, представляю­щая собой объединение групп. Тогда

Доказательство. По лемме 2.7 или S будет группой с нулем, или для некоторого п ≥ 1. Предположим, что для

некоторой нетривиальной группы G. Тогда I и поэтому и в этом случае утверждение доказано.

Предположим теперь, чтодля некоторого п ≥ 1.

Пусть I — отмеченный идеал полугруппы S и Тогда в соответствии с пунктом б) предложения 2.17 из микромодуля 8 S|(G0, поэтому Так как RLM(S) оканчивается комбинаторной полугруппой, мы можем получить неравенство:

Далее, поскольку С (S) = (G, п) для некоторого п ≥ 1, легко видеть, чтоТогда

Лемма доказана.

Следовательно, функция удовлетворяет аксиоме 3. Теперь дока­жем, что удовлетворяет аксиоме 2 (основной лемме для сложности).

Основная лемма для сложности (критическая точка всей теории сложности) утверждает, что если I — комбинаторный идеал полугруп­пы S, то Мы доказываем здесь этот факт для полу­групп, являющихся объединением групп, и наше доказательство существенно опирается на свойства этого класса полугрупп.

Представляется естественным получить эту теорему, доказав тот факт, что если I — идеал полугруппы S, то

Теорема из этого результата следовала бы немедленно; в действитель­ности и основная теорема декомпозиции была бы тогда тривиальной. Однако сформулированное утверждение неверно. В самом деле, если I — комбинаторный, то соотношение где С —

некоторая комбинаторная полугруппа, в общем случае неверно. Приступая к доказательству теоремы, мы исследуем вид и слож­ность полугруппы частичного произведения РР (Sf)s автомата Sf с помощью полугруппы S.

2.10. Замечание. Пусть — полупрямое произведение по­лугрупп S1 и S2. Напомним, что имеем

где

и

Автомат можно записать в аналогичной форме,

а именно

(1)