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

и 5 4 С > во всех остальных случаях. Пусть J , ^ f i Для % 4 Г или J « ^ C имеем * F* * * ( & ) • Пусть g e f , ?г е Г и Тогда, согласно свойству б множества ^(Г), найдется исЭщ г) u(St)+f ,«.» т .е . ^ 4 2 * Таким образом, и/(?4)* £ и Следовательно, W e ^ r) и '3'w-CUAftr т -е » Мы показали, что 2И является полной решеткой подмножеств, удовлетворяющей условию С*) . Определим отображение У : 2 1 ц г Г*’2 2 , согласно которому У№ )г9и '4/г). Легко показать, что это отображение является изоморфизмом. ПРВД1КЖЕШЕ. Пусть 2И -полная решетка подмножеств неко­ торого множества, удовлетворямцая условию (-#•) . 0 £ 2 • ДОКАЗАТЕЛЬСТВО. Пусть - пересечение всех множеств из 22 Если , то найдется «С из & . Тогда ЧТО противоречит выбору .£> . Пусть 2 2 - полная решетка подмножеств некоторого мно­ жества. Обозначим через (21,f)) полугруппу с операцией пере­ сечение. TE0PE.IA 2 . Для всякой полной решетки подмножеств 221 не­ которого множества Г , удовлетворяющей условию (*■) , найдет­ ся упорядоченное множество 22 , у которого является по­ лугруппой, изоморфной с (Л З ,Л ). ДОКАЗАТЕЛЬСТВО. Для к аж д о г о Г через £> обозначим пересечение всех множеств из 72 , содержащих <4 . На множестве Г зададим отношение, согласно которому тогда и только тогда, когда ■2сS 1' 2 ,р (Г ). Покажем,что полугруппа ^ Г) изоморфна f e ,/) ) . 1. Для каждого ие& (г) 9й(\Р принадлежит ZI . В самом деле, если £ Л Г « 0 , ТО по предыдущему предложению. Если 1 ЗйГ\Г*’ Ф , то через обозначим пересечение всех множеств из 2 j , содержащих £Гм/) Г . 0 , так как Г & 2 2 . Если / е & К П Г 1) , то . бМ *З с £ " . Р а с с м о т р и м Ь 1(б * '1*3)62 и Однако / S ' 1*" * что противоречит выбору 2. Для всякого ^ , ^ 2 найдется такой, что Для этого достаточно рассмотреть и^Tjpfrj, согласно которому * если УФ -&1 и ^ ( s ) = ^ bo всех остальных слу­ чаях. Ясно, что /V - направленное идемпотентное преобразование. 7?