Алгоритмические проблемы теории групп и полугрупп. 1994 г.

при некотором У , Рассмотрим следующие два случая, которые могут иметь место в (9 ) : /А* / < 1вуг I и IXel > / f y l > В первом докажем теоремы непосредственно, во втором сведем к индуктивному предположению. § 4 . Доказательство теорем 1 ,2 в случае "малого" левого остатка слова X Итак, пусть IXe I < /Ар'р) • ПРЕДЛОЖЕНИЕ 1 . Если IX/ / < / V . то в равенствах / 9-10J p = s и МГЧ/ </ * •>/• ДОКАЗАТЕЛЬСТВО. Сокращая (9 ) сл ева на Xg и справа на Хх получаем при некотором f £ t- £ £ ) JH) «) м Ai< Aii = 6'< > °</р и - непустые слова. Для после,днего равенства ' " откуда p i S . Кроме > / (13 ) (14 ) (15) причем с Ц выполнены условия леммы 3 , поэтому f ~ p т о го , по лемме 5 В(г ~ Aj, Ajf> 4 ip Подставим в (10 ^ выражения ( 1 2 ) : K H Xt М / , ... AJp = в с , . . . Вс, ŸX , Заменим слова Xg , Хх их выражениями У s а*> У = А°" А Xt - Оу> > " • л ‘ 5 и домножим второе равенство е (1 4 ) справа на 6 j Наконец, используя ( 1 3 ) , из последнего равенства получаем V A™ è i , . . . à £t s &it - X 4 % - - A i s в % . Левая и правая части это го соотношения имеют одинаковую дли­ ну; кроме того^ $ - / > - $ . Следовательно, p - S .Т о г д а (1 5 ) влечет X ^%Alf> , причем, как отмечалось выше, А¿р £ X . Предложение 1 доказано. Таким образом, равенство (9 ) перепишется в виде JH) J K I A i p Bjfi В.Vf ( 16 ) ПРЕДЕОЖЕНИЕ 2 . Если 1X^1<IAcsl , то в равенствах ( 9 - 1 0 ) Р - S и IX e l < 16 ^ 1 . Это утверждение доказывается аналогично предндутш.'у. Для упрощения записи введем обозначения: 2 > = £ > ЕГ AJ\ • • • AJp , > - , 'Vt ■ Заметим, что слова £ и •V (Н) *> с =А< , „ . .,к> п С непусты и L = Ь: .. . о : Jp л ИЗ ( рм - О*))-