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

В дальнейшем под Q будем понимать только упорядоченное множество. Частичный группоид всех операторов замыкания мно­ жества Q обозначим через Х а . Для каждого и- через (Ги. обозначим множество таких элементов , что MCWvt. Известно [3 J , что тогда и только тогда, когда м.* 1 Г . Если uV £& i (u , V t£ o ), то 2 . 1 [5 J . Совокупность всех S ’-и, обозначим через Z l a . Это мно­ жество всюду будем рассматривать относительно действия пере­ сечения, которое в пределах <Со. является частичным. Для всякого &Q через X обозначим множество всех элемен­ тов peQ . таких, что^^-оС . Известно 1 .3 [3 J , что подмножество принадлежит Z a тогда и только тогда, когда для каждого <£.eQ подмножество X i] Г имеет наименьший элемент. И, наконец, через J?Q обозначим • Принимая во внимание 1.3 £3] , имеем ПРЕДЛОЖЕНИЕ. Элемент oC^Q тогда и только тогда принадле­ жит 4а , когда для всякого , не содержащего сС , най­ дется S e Q , 8 , подмножество 8 АПГ не имеет наименьшего элемента. • . .. ЛЕММА. Если oC .jiffi , , то существует vi/б Х а ., Wfo-Ы, . ДОКАЗАТЕЛЬСТВО. Поскольку £ $ 4 а , то u(Jb)tjb для некоторого -и^Хки Рассмотрим ц/е1а>согласно которому для всякого &!$)=£, если f^ J 3 , и W(p)= 4 ($), если &f> • Тогда W (i)-l , и благода­ ря 1 .3 [ 3 ] преобразование W £ % является оператором замыкания. ТЕОРЕМА I . Частичный группоид Х к г тогда и только тогда является полугруппой, когда множество JkfQ . непусто и дла вся­ кого найдется покрывающий «С b Q . ДОКАЗАТЕЛЬСТВО. Пусть подмножество jfcicQ пусто. Тогда для вся­ кого найдется ХЬ. такой, что . Согласно лемме, n '( ( iW )H W , для некоторого Рассматриваяпро­ изведение \iw , получим, что но «- w w u - M ? и ( X и U.(*)f и -и ^М ) , т .е . Х а не полугруппа. Аналогично можно убедиться в том, что если </£ Q NJo . и u(J-)tcC , то и(*-} принадлежит 4 о. . Если u f X s i , ^ceQ\J|a и И(*.)+ 4 С , то покрывает b Q . 67