Индуцированные порядки в булевых решетках и фактор-отношениях универсального отношения Одинцов, Вадим Анатольевич

Введение к работе

Актуальность темы. Важную роль в развитии теории решеток играет специфическая связь между свойствами решеток, рассматриваемых с одной стороны как частично упорядочение множества, а с другой -как универсальные алгебры с двумя бинарными операциями. В обзоре Дилуорса [8] эта связь прослеживается по следующим четырем направлениям.

1. Роль диаграмм Хассе в теории решеток не только как средства изображения, но и как важнейшего инструмента исследования, к примеру, характеризация многообразий решеток с помощью диаграмм конечных "запрещенных" подрешеток.

2. Роль частичного упорядочения при изучении проблем вложения, когда рассматриваются различные операторы вложения частично упорядоченных множеств в полные решетки и различные конструкции их пополнения для решения теоретико-решеточных проблем.

3. Роль связи между теоретико-решеточными свойствами дистрибутивных решеток и теоретико-порядковыми свойствами частично упорядоченных множеств их \/-неприводимых (т.е. неразложимых в объединение) элементов.

4. Роль свойств решеток конгруэнции ConL в теории многообразий решеток.

В настоящей диссертации в контексте направлений 2, 3 изучается частичный порядок на совокупностях неподвижных точек \/-эндоморфизмов (т.е. эндоморфизмов по объединению) булевой решетки конечной длины и контексте направлений 1,4-частичный порядок на фактор-отношениях универсального отношения по эквивалентностям Риса, выделенными классами которых являются дополнения частичных порядков. При этом эквивалентностью Риса или Р-равенством на непустом множестве L в рабо-

те называется эквивалентность, индуцирующая равенство на подмноже-стве Р и универсалы-"ю эквивалентность на дополнении L\P, именуемом выделенным классом Р-равенства.

Пусть tp — изотопное преобразование полной решетки L и L_v - множество неподвижных точек оператора >р. По теореме Тарского о неподвижной точке Lp ф 0. Биркгоф в комментарии к этой теореме [2, стр.154] поставил следующий вопрос: образуют ли решетку в индуцированной частичной упорядоченности неподвижные точки изотопного отображения полной решетки в себя?

Когаловский СР. и Туманова Т.А. [6] показали, что для подмножества X полной решетки L равносильны следующие условия:

1.Х- множество всех неподвижных точек некоторого изотонного преобразования решетки L;

2. X — ретракт решетки L, т.е. существует изотопное отображение решетки L на ч.у. множество X, тождественное на Х\

3. X - полная решетка в индуцированной частичной упорядоченности.

Естественно поставить вопрос изучения строения ретракта X в конкретных случаях. К настоящему времени имеются отдельные примеры его решения. Так, Ханлон [9] изучил ретракт X, когда он состоит из неподвижных точек автоморфизма решетки разбиений множества {1,..., п}, индуцированного фиксированной перестановкой этого множества.

В наших обозначениях X = L_v. В соответствии с отмеченным выше направлением 2 в [9], поставим по отношению к тройке (L,ipL,L₉) следующий вопрос вложений: если ц>Ь вложена в L с сохранением только объединений или только пересечений и при этом L_v - подрешетка в то при каких условиях L_r будет подрешеткой в L? В данной работе решеткой L является конечная булевая решетка, а преобразованием цз - ее \/-эндоморфизм. Вопрос вложений для тройки (L, ipL, L_v) имеет в этом случае также и тот интерес, что всякая конечная решетка явля-

ется Y-эндоморфным образом булевой решетки. Еще один (приклад- _v ной) интерес представляет строение ретракта L_v для алгебры логики. ,Ь В приложениях алгебры логики (кибернетика, техника и т.д.) важную роль играют характеристические множества булевых функций. Последние состоят из двоичных наборов (... ,_л), на-которых булевы функции /(&,... ,„) принимают значение 1. Характеристические множества в указанных приложениях описываются поэлементно, в связи с чем возникает проблема ветвления, заключающаяся в экспоненциальной сложности перечисляющего алгоритма. Поэтому для данной булевой функции /(&, ...,„) целесообразно поставить следующий вопрос: не является ли ее характеристическое множество относительно естественной частичной упорядоченности V- или Д-подполурешетхой в булевой алгебре всех двоичных наборов (&,... ,f_n)? При положительном ответе вопрос перечисления всех элементов характеристического множества сводится к вопросу перечисления соответственно \j- или Д-неприводимых элементов соответствующей подполурешетки.

Естественно возникает и обратный вопрос: для всякой ли конечной решетки Р, вложенной в булеву алгебру L длины п как ч. у. множество с сохранением точных верхних или точных нижних граней, найдется булева функция / = /(&,..., „), характеристическое множество которой, рассматриваемое как подмножество алгебры L,' совпадает с Р? При положительном ответе в этом случае проблема перечисления характеристического множества функции / не возникает вовсе: оно однозначно определяется соответствующими неприводимыми элементами решетки Р. Отметим, что постановка вопроса описания характеристических множеств булевых функций в терминах частичного порядка нам в литературе не встречалась.

Переходя к частичному порядку на фактор-отношении, приведем вначале один его естественный пример.

Пусть а - естественно упорядоченная счетная цепь, состоящая из не-

У сократимых арифметических дробей -, где х, у Є N. Рассмотрим на а

обозначенную через ш< эквивалентность Риса, выделенный класс которой состоит из всех правильных дробей. Отождествим одноэлементные классы с образующими эти классы неправильными дробями и ослабим линейный порядок на их множестве, полагая, что непосредственно сравнимы лишь дроби с одинаковыми числителями или знаменателями. Дру-

у у у t гими словами, — < — и - < - => z < х и у < t. Отсюда по транзитив-

х z 2 z У t ности полагаем, что — < — <=* z < х < у для всех х, y,z,t N. При

X Z

этом класс правильных дробей будем считать наименьшим элементом ч. у. фактор-множества <т/и/<. Мы называем ч. у. Множество сг/ш< канонически упорядоченным множеством факторов Дедекинда естественно упорядоченного счетного ординала N по отношению {{х,у) : х,у Є N нод (х, у) = 1}. По определению фактор-порядка, как частичного порядка, определенного на классах эквивалентности ы< через частичный порядок, определен на представителях этих классов, частичный порядок на множестве является фактор-порядком ослабленного частичного порядка на множестве несократимых арифметических дробей.

Переходя к произвольному ч. у. множеству Р, формально отождествим одноэлементные классы {(я, у)}, где х < у для всех х, у Є Р, С неправильными арифметическу>ш дробями —, класс {(х,у) : х ^

-~ * X

у,х,у Є Р} - с классом правильных дробей, а также введем "ослабленный" частичный порядок на множестве всех классов как.в предыдущем случае арифметических дробей. В результате получим ч. у. множество, которое мы будем называть канонически упорядоченным множеством факторов Дедекинда ч. у. множества Р по универсальному отношению {(х, у) : х,у Є Р} (факторов Дедекинда ч. у. множества Р). Термин "фактор Дедекинда" непосредственно связан с термином "фактор ч.у.

множества", которым Дедекипд называл упорядоченную пару (х, у) элементов ч.у. множества, х < у, и которую он обозначал через у/х. Легко

видеть, что биекция > [х,у], {(х, у) : х у,х, у Є Р} -» 0 для всех

а:

х,у Р, является изоморфизмом ч. у. множества факторов Дедекинда ч. у. множества Р и ч. у. множества его интервалов (вместе с пустым интервалом) по включению. При этом возникает естественный вопрос: является ли понятие фактора {{х,у) : х у,х,у Є Р} содержательным с какой-либо точки зрения? В данной работе эта содержательность устанавливается в терминах насыщенных по эквивалентности w< частей множества Р х Р. Напомним, что по определению (см. Бурбаки [3]) таковыми являются произвольные объединения классов эквивалентности ш<. Наконец, общими в теории универсальных алгебр являются вопросы строения алгебр для конкретных классов алгебр и строения решеток их конгруэнции. В работе эти вопросы решаются для решеток факторов Дедекинда решеток. Заметим, что изоморфные объекты - решетки интервалов решеток с этих позиций не изучены.

Цель работы Изучить строение совокупностей неподвижных точек V-эндоморфизмов конечной булевой решетки во взаимосвязи с алгеброй логики и строение решеток факторов Дедекинда и решеток их конгруэнции для произвольных решеток.

Методика исследований. Результаты о строении совокупностей неподвижных точек V-эндоморфизмов булевой решетки получены методами линейной алгебры. Для этого булева решетка рассматривается как левый модуль над двухэлементной булевой алгеброй В с операцией сложения V и умножением элементов на скаляры из В, формально удовлетворяющим аксиомам классического унитарного модуля над кольцом [1, стр.261]. При этом на модуле определен согласованный с операциями частичный порядок <. \/"^энД^0М0РФ^измы решетки отождествляются с линейными операторами, сохраняющими порядок <, а их неподвижные

точки - с собственными векторами линейных операторов с собственным значением 1.

Результаты о строении решеток факторов Дедекинда получены методами формальной арифметики, оперирующей с факторами как с неправильными арифметическими дробями.

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. В ней развита структурная теория решеток класса решеток факторов Дедекинда и частично решены проблемы III.5 и III.7 в [4]: исследовать решетки, у которых решетка конгруэнции сто-унова, и развить структурную теорию для решеток, все конгруэнции которых стандартны. Результаты работы о строении решеток факторов могут найти применение в теории многообразий решеток при анализе локального строения решетки многообразий решеток. В приложениях алгебры логики может найти применение построенный в диссертации полиномиальный алгоритм решения систем булевых уравнений, рассма-. тривавшихся в [7].

Апробация работы. Результаты диссертации докладывались на XIX Всесоюзной алгебраической конференции (Львов, 1987), на международной конференции по алгебре, посвященной памяти А.А.Ширшова (Барнаул, 1991), на семинарах "АлггОра и логика⁵' (ИМ СО РАН), "Алгебраические системы" (УрГУ) и на алгебраическом семинаре института математики и механики УрО РАН.

Публикации. Результаты диссертации опубликованы в работах автора [11, 12, 13, 14, 15, 16, 17, 18].

Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы. Общий объем диссертации 95 страниц, список литературы содержит 29 наименований.