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

2 . dCе £ Г Пусть S'), Г и S не максимальный в Г . o tiji <s=> jb * f ( $ ) или , где Цб Г и Xz-Ъ . Пусть d * ( 0 ,5 ) , S€ Г . Л * /1 <?*> j» * (Ч ,£ ). В дальнейшем мы не будем делать различия между (0,1) и 8 , если (Уб-Г 1 . ДлЯ всякого Г будем обозначать S = ( i , 8 )_. Тогда любой элемент o(£^(ir) имеет вид или d.= 8 Для некоторого 8 с Г , Рассмотрим некоторые свойства упорядоченного множества ^ ri 1. Для всякого //(Г) и д 6 ^ ( г ) «М =<А» так как элемент оС максимален в 4 (Г), 2. Для всякого ,rf= 8 , « е ^ ( Г) и имеет место U (*) =c Л. . ДОКАЗАТЕЛЬСТВО. Если элемент 5 максимален в Г , то о мак­ симален в 2 f . В Ы(Г) не существует элемента больше $ , т .е . 8 максимален в}(Г), _ Если в Г существует Jf?S х то 1*8 в£Р. С другой сто­ роны, у( 5 ) 7 $ , и покрывает 8 в /( Г ) . Тогда для всяко­ го f (£ ) И $ ± ц ( 5 ) с ц ( й ) . ТогдаU(S*fZ[>, . т . е . U( j)= 8 . 3. Если ,(А е /(Р ) и то о С принадлежит Г , Доказательство следует из свойств I и2. 4. Если d€$(r) и иб iW для некоторого « е < ^ , то с ^ Р и и(+)-£. ДОКАЗАТЕЛЬСГЮ. Согласно свойству 3, принадлежит Г . Легко видеть, что <£покрывает <f- в £ (г) , Тогда вС< и (ы )* ц (Л ) . По свойству 2 это означает, что иО-)-£. 5 . ^£х(г) является полугруппой. ДОКАЗАТЕЛЬСТВО. Пусть и , 1 г е ^ г ) и о ^ ( г ) . Если , то согласно свойствам I и 2 . Если die Г , т» или иС*)-2 . Тогда WVH- VU и rtve.fiа. . 6 . Если 5 , 8 е Р ,че£ }(п ) ,*(%)+$ , S r J , то м (£ )+Ъ . ДОКАЗАТЕЛЬСТВО. По свойству 4 д ф - J , т .е . , S ' (0,8) • но ( 0 ,5 ) ? (A t) • 7 . Для всякой полугруппы <£я. найдется упорядоченное множество Г с Q . , ЧТО полугруппы 2?£г. и o£-f(r) изоморфны. ДОКАЗАТЕЛЬСТВО. Согласно теореме I, подмножество Jk cQ. непусто. Обозначим через Г множество Q \ Л я . , На множестве Г введем отношение порядка таким образом, ч т о в Г , если ней- 69