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

знаем, что . Если же будет таким, как в случае 3, то мы знаем, что возвращается в I

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

Эти свойства позволяют построить последующий автомат.

2.18. Замечание. Пусть J будет F классом полугруппы S. Вспом­ним определение идеала F (J) (см. обозначения 2.2 из микромодуля 9). В случае полугруппы, представляющей собой объединение групп, нуль разде­ляет S/F (J), поэтому S — F(J) будет подполугруппой полугруппы S. J есть ядро полугруппы S — F (J).

Из этого следует, что для i = 1, ..., n— 1 имеется включение S — F (Ji) S — К, так как

Положим тогда Si|S/K. Отметим, что любой элемент последовательностипринадлежащий F (Ji), не влияет на выход автомата Fi.

Теперь с помощью имеющихся у нас сведений, включая лемму 2.17, нетрудно проверить следующие соотношения для автоматов при i =1, 2, ..., n-1:

(2.7)

Из соотношения (7) получаем

Тогда согласно следствию 2.12 имеем:

Но поскольку St\SIK, i — 1, ..., п—1, то справедливо соотношение

(6)

Теперь, применяя неравенства (2.5б) и (6), получаем

Но S/K есть образ гомоморфизма полугруппы S, поэтому

Тем самым фундаментальная лемма для сложности доказана (т. е. теорема 2.15).

Таким образом, мы доказали, что Оставшаяся часть

доказательства теоремы 2.5 основывается на нескольких леммах.

2.19. Лемма.

Доказательство. Сначала рассмотрим последовательность (б) определения 2.4. Пусть и т. д.

Заметим, что в силу теоремы 1.14 из микромодуля 9 (или предложения 3.19 из микромодуля 9) последовательность должна достигать полугруппы S.

Можно утверждать, что где j пробегает совокупность всех таких эпиморфизмов, что

и где j пробегает совокупность всех таких эпиморфизмов, что , и существуют такие эпиморфизмы, что и т. д. Для того чтобы доказать это, положим По определению полугруппы S-1 имеем где SC — максимальный гомоморфный комбинаторный образ полугруппы S. Теперь поскольку прямые суммы и ограничения L и γ гомоморфизмов являются L и γ гомоморфизмами соответственно. Так как имеем

С другой стороны, поэтому

Следовательно, Продолжая эти рассуждения, мы докажем, что для всех i = 1, 2, ... Пусть k — такое наименьшее целое число, что

Сейчас мы докажем, что число собственных L гомоморфизмов в по­следовательности

(б)

[т. е. θb (S)] не превосходит числа собственных L гомоморфизмов в любой последовательности, состоящей из чередующихся γ и L гомо­морфизмов полугруппы и начинающейся с γ гомоморфизма.

Пусть k — четное число. Тогда последовательность (б) начинается с L гомоморфизма. Предположим, что последовательность, состоящая из чередующихся L и γ гомоморфизмов полугруппы S и начинающая­ся с γ гомоморфизма, достигает {0} за k— 1 шагов. Тогда из имею­щихся результатов для мы получаем, что Это противоречие. Если в последовательности, с которой мы имеем дело, {0} получается на k— 2 шаге, то, добавляя тривиальное отображение к концу последовательности, мы получаем последователь­ность длины k — 1 и снова приходим к противоречию. Следовательно, длина последовательности должна быть не меньше k и утверждение для случая, когда k —четное число, доказано.

Пусть число k— нечетное, так что последовательность (б) начинает­ся с γ гомоморфизма. Если длина последовательности чередующихся гомоморфизмов не превосходит числа k — 2, то снова возникает про­тиворечие. Поэтому в рассматриваемом случае длина последователь­ности должна быть равна самое меньшее k— 1. Но легко видеть, что для L гомоморфизмов утверждение справедливо, поэтому все доказано.

Теперь мы применим аппарат, развитый в п. 3.8 микромодуля 9, для того, чтобы получить коммутативную диаграмму (см. рис. 3.2).

Рис. 3.2

Если последовательность (б) начинается с L гомоморфизма, доба­вим в начале тождественное отображение, чтобы она начиналась с γ гомоморфизма. Тогда заметим, что так как для полугруппы, являющейся объединением группы, SF будет комбинатор­ной полугруппой. Тогда каждое γ отображение, исключая последнее, будет γ+F отображением. Следовательно, квадрат 1 коммутативен.

Так как мы имеем последовательность

Коммутативность квадрата 2 следует из пункта б) предложения 3.2 из микромодуля 9.

Так как имеется последовательность

квадрат 3 коммутативен в силу утверждения 3.15 из микромодуля 9. Продолжаем действовать таким же способом на соединении последовательностей (б) и (в).

Из замечания 3.16 в микромодулe 9 теперь следует коммутативность квадра­тов 4 и 7. Так как то квадраты 5 и 8 коммутативны. Для квадрата 6 имеем:

Для квадрата 9 в силу утверждения 3.7 из микромодуля 9 имеем:

Продолжая далее эти рассуждения, получим коммутативность всей диаграммы.

Так как S-1 — комбинаторная полугруппа, полугруппы

также комбинаторные. Покажем, что если Т —

комбинаторная полугруппа, то

Последние два равенства следуют из пункта а) утверждения 3.25 из микромодуля 9. Для доказательства первого напомним, что Но Tγ = {0}. Следовательно, справедливы соотношения ' поэтому они изоморфны.