АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1990 г.

дутся такие элементы из Г 4j5*.4 ••4 ft* * “'•г- ("в С2) , что для всякого i-J, г,..,,П и i fQ ,£ ( /!$ .,(в Q ) ^ не принадле­ жит J q .. Покажем, что полугруппы дбп. и изоморфны. Для каждого рассмотрим й^Т^усогласно которому и М - К , если оСб Г и и «(*•) = л. во всех остальных случаях. Легко видеть, что 1 / направленное и идемпотентное преобразо­ вание. Покажем, чт o-U - эндоморфизм. Пусть «ф<<^ (**,*,?ft(Г)). 1. llM - d - i . Тогда И 2 . . Тогда cf<e Г и . Если и «***& в i ( T J , то<У*=£, в К р)« Пусть теперь и г/£*)=4 Посколь­ ку в >ГГ) , Г , найдется в Г цепь di=J>,&-. 6 <Li_ такая, что для всякого не принадлежит J sl . Пусть jii+ i такой наименьший элемент этой цепи, что При,)f a Тог- Да f t i < f a t. Как следует из доказательства теоремы Щ М г Таким образом, случай d , < , fa d ft V , и&щ)ч/^ в Г не име­ ет'м еста, т .е . U"d£±(r). < Рассмотрим отображение У • ^ o .^ a C fr\, согласно которому Y ftO-tL . Нетрудно показать, что У инъективное отображение. Покажем, что у сюръективно. Пусть Для каждого через %' обозначим элемент из Л я ., покрьшаиций 5 b Q . Рас­ смотрим преобразование и * Та,согласно которому U($)=g', если Ле Г ,&(£)*$и u (g )-g во всех остальных случаях. Ясно, что •U- является направленным идемпотентным преобразованием. пусть ( i д а > I . = или ^ Г 1 • Тогда ■ и . Пусть и Тогда,по следствию 2 теоремы l .S t ^ Z L и ’H ' ( Z i ) ' U f e d ~ f f t Пусть теперь Г • Благодаря следствию 2 теоремы I . И, наконец, согласно свойству б множества /( Г ) случай , U(t,)+fa Г никогда не имеет места. Легко видеть, что для этого w f / n . fM ~ U, Заметим, что СЛ Р -ЗаА Г . Тогда для любых и* , как c/si. полугруппа, имеет место Принимая во внимание сказанное выше, имеем У(й|)^г)- 70