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

Одинцов, Вадим Анатольевич

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

Одинцов, Вадим Анатольевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

1999 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Индуцированные порядки в булевых решетках и фактор-отношениях универсального отношения»

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК " ^^ УРАЛЬСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

ОДИНЦОВ Вадим Анатольевич

ИНДУЦИРОВАННЫЕ ПОРЯДКИ В БУЛЕВЫХ РЕШЕТКАХ И ФАКТОР-ОТНОШЕНИЯХ УНИВЕРСАЛЬНОГО ОТНОШЕНИЯ

Специальность 01.01.06 - математическая логика, алгебра и теория

чисел

Автореферат. диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург - 1999

Работа выполнена в Институте математики и механики Уральского Отделения Российской Академии Наук.

Научный руководитель — доктор физико-математических наук,

профессор А.И.Старостин Официальные оппоненты — доктор физико-математических наук,

профессор Ю.М.Важешш кандидат физико-математических наук, доцент Е.А.Перминов Ведущая организация — Саратовский государственный

технический университет

Защита диссертации состоится Имая 1999 года в 15 часов на заседании диссертационного совета Д 002.07.03 в Институте математики и механики УрО РАН по адресу:

(620219, г.Екатеринбург, ул. Софьи Ковалевской, 16)

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 10 апреля 1999 г.

Ученый. секретарь

диссертационного совета ' г~

кандидат физ.-мат. наук, доцент /// ¡СА-У^^-—В.В.Кабанов

Общая характеристика работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ется У-эндоморфным образом булевой решетки. Еще один (приклад- > ной) интерес представляет строение ретракта для алгебры логики. В приложениях алгебры логики (кибернетика, техника и т.д.) важную роль играют характеристические множества булевых функций. Последние состоят из двоичных наборов .,/;„), на-которых булевы функции /(&,... ,£„) принимают значение 1. Характеристические множества в указанных приложениях описываются поэлементно, в связи с чем возникает проблема ветвления, заключающаяся в экспоненциальной сложности перечисляющего алгоритма. Поэтому для данной булевой функции /(£1, целесообразно поставить следующий вопрос: не является ли ее характеристическое множество относительно естественной частичной упорядоченности V" яли Д-подполурешетхой в булевой алгебре всех двоичных наборов (&,.. - При положительном ответе вопрос перечисления всех элементов характеристического множества сводится к вопросу перечисления соответственно \/- или Д-неприводимых элементов соответствующей подполурешетки.

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

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

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

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

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

У У У I ^

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

ности полагаем, что — < — г < х < у < I для всех х, у, г, £ £ N. При х г

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

Переходя к произвольному ч. у. множеству Р, формально отождествим одноэлементные классы {(я, у)}, где х < у для всех х, у 6 Р,

С неправильными арифметическу>ш дробями —, класс {(ж, у) : х

^ * х

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

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

видеть, что биекция-->■ [а:, 2/1, {(х, у) : х £ у,х, у е Р} 0 для всех

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

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

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

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

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

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

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

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

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

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

Краткое содержание диссертации.

О; В § 1 главы 1 решаются следующие задачи:

а) изучается строение совокупности 2^,, состоящей из неподвижных точек данного \/-эндоморфизма <р конечной булевой решетки Ь;

б) изучается проблема вложения решетки в решетку Ь;

в) изучается строение решетки Ь^, в случае когда <р - произвольный решеточный эндоморфизм;

г) изучается проблема вложения данной дистрибутивной решетки й в булеву решетку Ь той же длины, что и 5, в качестве решетки неподвижных точек для некоторого \/-эндоморфизма <р решетки Ь.

Основными результатами этого параграфа являются теоремы 1-4.

Теорема 1. Реьиётка неподвижных точек любого У -эндоморфизма конечной булевой решётки дистрибутивна.

Для произвольного изотонного оператора ф решетки Ь назовем эле-

менты решетки Ьф ^-неподвижными точками и обозначим через ф изо-

тонный оператор, определяемый условием гр х = фх V х для всех х 6 Ь.

Теорема 2. Решётка Ь,Р для \/-эндоморфизма <р конечной булевой решётки Ь тогда и только тогда будет в ней подрешёткой, когда содержащееся в каждом главнол1 порядковом фильтре, порожденном \/-

неприводимой 'Р-неподвижной точкой, множество У-неприводимых у-неподвижных точек также является главнъш фильтром.

Теорема 2 дает необходимые и достаточные условия вложения решетки Ь^ в решетку Ь в качестве ее подрешетки.

Пусть у - эндоморфизм булевой решетки Ь с атомами е,-, » = 1,... га, п > 1. Назовем уз-циклом произвольную циклическую перестановку множества {г : г = 1,...,п; е^ А <р0 = 0}. <р-цчкл (ц... ц), I = 1,..., п назы-

вается стабильным циклом эндоморфизма <р, если для всех к = I,.. .,1 выполнено >

Теорема 3. Неподвижные точки любого эндоморфизма </> конечной булевой решётки образуют в ней булеву подрешётку, длина которой равна числу стабильных ^-циклов этого эндоморфизма.

Следствие 1. В дистрибутивной решетке Р любое подмножество множества J(P) ненулевых -неприводимых элементов V - порождает подрешетку в Р тогда и толь'^> тогда, когда каждый неприводимый У -элемент покрыт в ч. у. множестве J(P) не более нем' однтмм элементом.

Если е : решеточный мономорфизм для произвольных ре-

шеток 5, Ь и - изотонное преобразование решетки Ь, для которого г(5) = Ьр, то е называется ^-представлением решетки 5 неподвижными точками (<р-представлением решетки Б).

Теорема 4. Всякий мономорфизм дистрибутивной решетки в булеву решетку той же длины является <р-предстйвлением дистрибутивной решетки для подходящего \]-эндоморфизлш булевой решетки.

В § 2 главы 1 решаются следующие задачи:

а)для данной дистрибутивной решетки 5 длины п найти пропозициональную формулу ... ,Хп) брауэровой логики, характеристическое множество которой, рассматриваемое в естественной частичной упорядоченности, изоморфно ч.у. множеству 5;

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

Напомним [2, стр.365] , что брауэровой логикой называется пропозициональное исчисление, которое является решеткой с О и I такой, что

В1. Р -»д = / Р < Я \

В2. Р {<3 -»• й) = (Р V д) Л для всех Р, Л.

Пусть Л = ,..., Х„) - пропозициональная формула брауэровой логики в переменных Х1,...,Хп и Р - конечное ч. у. множество. Множество двоичных наборов .. •, на которых истинностная функция /(&,.. определяемая пропозициональной формулой >1(^1,..., Хп) в двузначной модели брауэровой логики, принимает значение 1, называется характеристическим множеством формулы Л■ Формула Л, для которой формула Л -» 0 не является тавтологией, называется выполнимой формулой. Характеристическое множество выполнимой формулы непусто, и оно определяет эту формулу с точностью до эквивалентности.

Напомним, что формула Л = В называется эквивалентностью формул Л и В, а сами формулы Л, В - эквивалентными формулами, если

{Л ВЩ8 -»■ >1).

Выполнимая формула Л называется интерпретацией ч.у. множества Р в брауэровой логике, а ч.у. множество Р называется интерпретируемым в этой логике посредством формулы Л, если характеристическое множество формулы Л в естественной частичной упорядоченности изоморфно ч. у. множеству Р.

Указанные выше задачи а) и б) решают соответственно теоремы 5 и

Теорема 5. Каждая дистрибутивная решетка длины п, как ч. у. множество, интерпретируема в брауэровой логике посредством фор-

мулы &с (<?,■ —>• для подходящих дизъюнкций С}х, г = 1,..., п, в пере-<=1

менных Х\,..., Хп ■

Теорема 6. Пусть в пропозициональной формуле Л = & V

>е/с{1,...,п}

(О —> X;) = X,) & & = подформулы <5,- являются произ-

вольными (быть может пустыми) дизъюнкциями в переменных X},.. Хп для всех г = 1,..., п. Тогда характеристическое множество формулы Л в естественной частичной упорядоченности образует в булевой решетке Ь, состоящей из всех наборов (£ь • • ■, £п)> вместе с нулевым элементом решетки Ь плотную (т.е. с единственным атомом) подре-ше^пку длины не более, чем п — |/| + 1.

Система булевых уравнений V (о^Лфь) \Л/3* = определяемая фор-

к=1

мулой Л, из теоремы 6, связана с одним классом релейно-контактных схем (см. [7]). Для нее можно определить понятие системы фундаментальных решений. Она будет состоять из элементов множества ./(й), где ¿"-дистрибутивная решетка, образованнная всеми решениями. По теореме 6 5 совпадает с характеристическим множеством формулы Л.

В главе 2 развита структурная теория для решеток класса решеток факторов Дедекинда (факторов) и решеток их конгруэнций.

В §3 главы 2 решаются следующие задачи:

а)для ч. у. множества (£; <) изучить строение частично упорядоченного включением множества насыщенных по рисовской эквивалентности о;< частей множества £ х Ь\

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

Указанные задачи а) и б) решают соответственно предложение 1 и предложение 2.

Для подмножества £ ч. у. множества Ь/Ь факторов ч. у. множества (Ь,<) первой (второй) проекцией Р^ЦРггЕ) множества Е на множество Ь называется множество числителей (знаменателей) всех факторов

- 6 Е. Часть Ах В множества Ь X Ь называется насыщенной частью х

для эквивалентности ш<, есл'^4 х В является объединением некоторых классов эквивалентностиш< [3, стр.129].

Предложение 1. Множество Ах В насыщено для эквивалентности а/< тогда и только тогда, когда либо для всех а 6 А, Ь Е В выполнено {(а, 6)} = -, либо Ь \ {0} ХХ\{1}С.«4ХБС1/Х1/. Насыщенные части Ь\{0}хХ, ЬхЬ\{ 1}, £\{0}х£\{1} множества ЬхЬ включая его самого, а также фактор-множества Ео = Ь\ {0} х Е1 = Ь X Ь \ {1 }/ш<,

Ь\ {0} х!\{1}\и<, Ьх образуют по включению булеву решетку длины 2. При этом Рп£0 = Рг2Е0 = {0}, РгхЕ1 = Рг2Е1 = I \ {1} РпЕ0 П Ег = Рг2Е0 П Е1 = I \ {0,1}. □

Предложение 2. Частично упорядоченное множество факторов ч.у. множества Ь является решёткой.тогда и только тогда, когда ч.у. множество Ь является решёткой.

В §4 главы 2 решаются следующие задачи:

а)найти все подпрямо неразложимые решетки факторов;

б) найти все простые решетки факторов;

в)описать решетки конгруэнций решеток факторов;

г)найти все регулярные решетки факторов;

д)классифицировать конгруэнции непростых решеток факторов. Указанные задачи а)-д) решают соответственно, теоремы 7-11.

Теорема 7. Решётка факторов неодноэлементной решётки Ь подпрямо неразложима тогда и только тогда, когда \Ь\ ф 2.

Значение этого результата в теории многообразий решеток обусловлено той ролью, которую играют \Лнераз.ложимые элементы в решетке многообразий решеток (см. Ионссон [10]), в частности, для изучения

решетки подмногообразий данного многообразия. Естественно также поставить вопрос изучен^? интервалов типа \EquL, ЕциЬ/Ь], к примеру, для пятиугольника N5.

Теорема 8. Решётка факторов неодноэлементной решётки непроста тогда и только тогда, когда исходная решётка содержит неразложимый несобственный элемент.

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

Теорема 9. Плотная пятизлементная решётка длины 3 и все её собственные неодноэлементные подрешётки длины не более двух исчерпывают с точностью до изоморфизма все решётки конгруэнций решёток факторов решёток.

Отметим, что по теореме 9 решетки факторов и их прямые произведения являются решетками со стоуновыми решетками конгруэнций, проблема изучения которых постелена Гретцером.

Подмножество X алгебры А называется регулярным, если оно является классом точно одной конгруэнции на А. Конгруэнция на алгебре называется регулярной, если все её классы регулярны. Алгебра называется регулярной, если все конгруэнции на ней регулярны.

Теорема 10. Решётка факторов решётки регулярна тогда и только тогда, когда исходная решётка содержит не более одного неразложимого несобственного элемента или когда она двухэлементна.

Конгруэнция в[1], где I - идеал, называется стандартной, если х = у(0[1]) {х Ау)\/ г —XV у для некоторого г 6 I (см. [4]).

Теорема 11. Все конгруэнции на решётках факторов стандартны.

В §5 главы 2 решаются следующие задачи:

а)изучить строение идеалов и коидеалов, в том числе ядерных идеалов конгр^-энциН решеток факторов;

б)найти связь между упорядоченными включением ядерными идеалами собственных конгруэнций решетки факторов решетки Ь и упорядоченными включением насыщенными по эквивалентности о>< частями множества Ьх Ь;

в)пзучить локальное строение решетки многообразий решеток вблизи многообразия Еди(Ы,¡) для пятиугольника N5.

Указанные задачи а)-в) решены соответственно в теореме 12, следствии 1, предложении 3, теореме 13.

Теорема 12. В решётке факторов любой собственный коидеал разложим в прямое произведение своей первой проекции на решётку, двойственную его второй проекции, и всякий собственный идеал разложим в прямое произведение тогда и только тогда, когда он - главный идеал, порождаемый субатомом.

Следствие 1. Ядерные идеалы всех собственных конгруэнций решёток факторов подпрямо неразложшт за исключением решёток факторов трёх и четырёхэлельентной цепей.

Из теоремы 12 непосредственно вытекает следующий факт, установленный в [5] на языке решеток интервалов: всякое самодвойственное тождество на решетке Ь является тождеством на любой подрешетке в ¿/¿, не содержащей элемента Оц^.

Идеал I решетки факторов называется вполне насыщенным, если I является фактор-множеством по отношению о;< некоторой насыщенной по эквивалентности ы< части множества Ьх Ь.

Предложение 3. Идеал I вполне насыщен тогда и только тогда, когда I-ядерный идеал некоторой конгруэнции решетки Ь(Ь.

Предложение 3 совместно с предложением 2 устанавливают сохраняющее порядок взаимно однозначное соответствие мтасду ненаименьшими конгруэндиями решетки факторов решетки Ь и насыщенными по эквивалентности си< частями множества ЬхЬ, упорядоченными включением, и показывают, что формальное соответствие между 0-фактором, т.е. классом {{х,у) : х у, х,у £ £,}, и пустым интервалом при изоморфизме решетки факторов решетки Ь и решетки ее интервалов по включению не уравновешивает указанные понятия с содержательной точки зрения.

Назовем локальным строением решетки многообразий решеток вблизи элемента конечной высоты строение ч. у. множества 1([Еди(Ь), Еди(Ь/¿)]). Локальное строение решетки многообразий вблизи элемента -ЕдгфУб) характеризует следующая теорема.

Теорема 13. Все неприводимые элементы решетки многообразий решеток, заключенные в интервале [Еди(Ы,¡), Еди(Ы$/./У5)], приведены на рис. 1-9, а ч. у. множество, образованное ими по включению - на рис. 10.

Рис. 7. 22/22

1 s

<jj

Рис. 8. Мъ

Рис. 9. Li

Equ{ 22/22)

Equ{L3)

Equ(L\) ^^ Equ(jL2\L^ Equ(N5)

Equ(M3)

Рис. 10. J[[Equ{22),Equ{Nb/N5)])

- <*<'

Литература

1. Артамонов В.А., Салий В.Н., Скорняков Л.А., Шеврин Л.Н., Шуль-гейфер Е.Г. Общая алгебра, т.2. - М.:Ыаука, 1991. - 480с.

2. Биркгоф Г. Теория решеток. - М.:Наука, 1984. - 5G8c.

3. Бурбаки Н. Теория множеств. М.:Мир, 1965. - 456с.

4. Гретцер Г. Общая теория решеток. М.:Мир, 1982. - 456с.

5. Игошин В.И. Решетки интервалов и решетки выпуклых подрешеток решеток// Упорядоченные множества и решетки. Межвуз. сб. науч. тр. Саратовгизд. СГУ, 1980, выл.6, с.69-76.

6. Когаловский С.Р., Туманова Т. А. Замечания о неподвижных точках изотонных преобразований// Иванов, ун-т, Ивановский текстильн. ин-т. Иваново, 1981, Деп. в ВИНИТИ 9.02.1981 N622-81 - Юс.

7. Чистов В.П. О системах логических уравнений// ИММ УНЦ АН СССР. Свердловск, 1985, Деп.;в ВИНИТИ N2114-85

8. Dilworth R.P. The role of order in lattice theory // "Ordered Sets. Proc. NATO Adv. Study Inst., Banff, Aug.28-Sept.12, 1981". Dordrecht e.a., 1982. - P.333-353.

9. Hanlon Ph. The fixed-point partition lattices // Pacif.J.Math. - 1981. -Vol.96. - P.319-341.

10. Jonsson B. Algebras whose congruence lattices are distributive// Math. Scand. - 1967. - Vol.21. - P.110-121. - 1984. - Vol.18. - P.95-105.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

11. Одинцов В.А. О конгруэнциях решеток интервалов.// Тез. сообщ. 19 Всесоюз. алгебр, конф., Львов, сент. 1987 г. - Львов, 1987. - 4.2 -

12. Одинцов В.А. Конгруэнции на решетках интервалов // Алгебраические системы и их многообразия: Сб. науч. тр. Свердловск: УрГУ,

с.206.

1988. - с.104-113.

13. Одинцов В.А. О неподвижных точках верхних эндоморфизмов конечной булевой решетки // Подгрупповая структура групп. Свердловск: УрО 'АН СССР, 1988. - с. 135-148.

14. Одинцов В. А. О ретрактах конечной булевой решетки // Тез. докл. по логике и универсальным алгебрам, прикладной алгебре. Межд. конф. по алгебре, Барнаул, авг. 1991 г. - Новосибирск, 1991. - с.99.

15. Одинцов В.А. Эндоморфизмы булевых решеток // Тез. сообщ. межд. конф. по алгебре. - С. - П. май 1997 г. - С. - П., 1997. - с.252

16. Одинцов В.А. Об эквациональных свойствах класса решеток интервалов решеток // Тез. докл. научно-практ. конф. вузов Урал, зоны, Челябинск, апрель 1998 г. - Челябинск, 1998. - с.30

17. Одинцов В.А. Главные идеалы и главные коидеалы решеток интервалов решеток // Исследования алгебраических систем по свойствам их подсистем: Сб. науч. тр. Урал. гос. пед. ун-т. Екатеринбург, 1998 г. - с.79-81.

18. Одинцов В.А. Представление решеток в двухзначной логике // Исследования алгебраических систем по свойствам их подсистем: Сб. науч. тр. Урал. гос. пед. ун-т. Екатеринбург, 1998 г. - с.82-85.

Екатеринбург, ротапринт, подписано к печати 5.04.99г. Тираж 100 экз. Заказ 2326 .

Ротапринт ИММ УрО РАН 620219, г.Екатеринбург, ул.С.Ковалевской 16

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

ОДИНЦОВ Вадим Анатольевич

ИНДУЦИРОВАННЫЕ ПОРЯДКИ В БУЛЕВЫХ РЕШЕТКАХ И ФАКТОР-ОТНОШЕНИЯХ УНИВЕРСАЛЬНОГО ОТНОШЕНИЯ

Специальность 01.01.06 - математическая логика, алгебра и теория

чисел

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор А.И.СТАРОСТИН

Екатеринбург - 1999

Оглавление

Введение 4

1. Объект и направление исследования..........................4

2. Постановка задачи................................................5

3. Методика исследования..........................................9

4. Основные результаты............................................9

1 Вложение частично упорядоченных множеств в булевы

решетки 19

1. Неподвижные точки \/-эндоморфизмов конечной булевой решетки в индуцированной частичной упорядоченности . . 19

1.1. Неподвижные точки изотонных преобразований решеток ......................................................20

1.2. Левые модули над двухэлементной булевой алгеброй 24

1.3. Полулинейные преобразования свободного Б-модуля 27

1.4. Неподвижные точки эндоморфизмов свободного В-модуля ................................31

1.5. Неподвижные точки эндоморфизмов булевой решетки 41

1.6. Неподвижные точки полуэндоморфизмов свободного В-модуля..................................48

1.7. Представление дистрибутивных решёток решетками неподвижных точек..................................50

2. Интерпретация неподвижных точек в логике Брауэра ... 58

2 Частичный порядок на фактор-отношениях универсаль-

ного отношения 62

3. Факторы Дедекинда частично упорядоченных множеств . 62

4. Решётки факторов Дедекинда и их конгруэнции............71

4.1. Подпрямая неразложимость решёток факторов ... 71

4.2. Решётки конгруэнций решёток факторов..............78

4.3. Алгебраические свойства конгруэнций................81

5. Идеалы и коидеалы решёток факторов Дедекинда..........84

5.1. Строение идеалов и коидеалов..........................84

5.2. О локальном строении решетки многообразий решеток ..........................................................90

Литература 93

Введение

В диссертации изучаются частичные порядки, индуцированные некоторыми данными частичными порядками, и частичные порядки, являющиеся их ослаблениями. Последние порядки также можно называть индуцированными, если в определении индуцирования исходить из бинарного отношения. Действительно, пусть рСРхРир- порядок с диагональю {(ж, ж) : же?}, Пусть 8 С р и 6 - порядок с диагональю {(ж, х) : х £ Q1 Q С Р}. Будем называть 8 частичным порядком на Q: индуцированным частичным порядком р.

1. Объект и направление исследования

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

пополнения для решения теоретико-решеточных проблем.

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

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

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

2. Постановка задачи

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

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

1. X - множество всех неподвижных точек некоторого изотонного пре-

образования решетки

2. X - ретракт решетки Ь, т.е. существует изотонное отображение решетки Ь на ч.у. множество X, тождественное на X;

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

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

В наших обозначениях X = Ь<р. В соответствии с отмеченным выше направлением 2 в [15], поставим по отношению к тройке (Ь,(рЬ, Ь^) следующий вопрос вложений: если <рЬ вложена в Ь с сохранением только объединений или только пересечений и при этом Ь^ - подрешетка в </?£, то при каких условиях Ь^ будет подрешеткой в Ш В данной работе решеткой Ь является конечная булевая решетка, а преобразованием ср - ее \/-эндоморфизм. Вопрос вложений для тройки (I/, <рЬ, Ь^) имеет в этом случае также и тот интерес, что всякая конечная решетка является \/-эндоморфным образом булевой решетки. Еще один (прикладной) интерес представляет строение ретракта Ь^ для алгебры логики. В приложениях алгебры логики (кибернетика, техника и т.д.) важную роль играют характеристические множества булевых функций. Последние состоят из двоичных наборов (£х,..., на которых булевы функции /(£х, • • •, £п) принимают значение 1. Характеристические множества в указанных приложениях описываются поэлементно, в связи с чем возникает проблема ветвления, заключающаяся в экспоненциальной сложности перечисляющего алгоритма. Поэтому для данной булевой функции ..., £п) целесообразно поставить следующий вопрос: не является ли ее характеристическое множество относительно естественной ча-

стичной упорядоченности \/_ или Д-подполурешеткой в булевой алгебре всех двоичных наборов (£1,..., £п)? При положительном ответе вопрос перечисления всех элементов характеристического множества сводится к вопросу перечисления соответственно \/- или Д-неприводимых элементов соответствующей подполу решетки.

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

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

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

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

гими словами, — < - и - < - •<=>■ г <х ж у < Отсюда по транзитив-х х г г У *

ности полагаем, что — < - г < х < у <t для всех х, у. х, £ £ N. При

х г

этом класс правильных дробей будем считать наименьшим элементом

ч. у. фактор-множества сг/и><. Мы называем ч. у. множество сг/ш< канонически упорядоченным множеством факторов Дедекинда естественно

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

Переходя к произвольному ч. у. множеству Р, формально отождествим одноэлементные классы {(ж, у)}, где х < у для всех ж, у 6 Р,

с неправильными арифметическими дробями —, класс {(х,у) : х ^

у, ж, у Е Р} - с классом правильных дробей, а также введем "ослабленный" частичный порядок на множестве всех классов как в предыдущем случае арифметических дробей. В результате получим ч. у. множество, которое мы будем называть канонически упорядоченным множеством факторов Дедекинда ч. у. множества Р по универсальному отношению {(ж, у) : х, у Е Р} (факторов Дедекинда ч. у. множества Р). Термин "фактор Дедекинда" непосредственно связан с термином "фактор ч.у. множества", которым Дедекинд называл упорядоченную пару (ж, у) элементов ч.у. множества, х < у, и которую он обозначал через у/х. Легко видеть, что биекция--> [х, у], {(х,у) : х ^ у, х, у Е Р} —>• 0 для всех

ОС

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

и<. Наконец, общими в теории универсальных алгебр являются вопросы строения алгебр для конкретных классов алгебр и строения решеток их конгруэнций. В работе эти вопросы решаются для решеток факторов Дедекинда решеток. Заметим, что изоморфные объекты - решетки интервалов решеток с этих позиций не изучены.

3. Методика исследования

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

4. Основные результаты

В § 1 главы 1 решаются следующие задачи:

а) изучается строение совокупности состоящей из неподвижных точек данного \/-эндоморфизма (р конечной булевой решетки Ь;

б) изучается проблема вложения решетки Ь^ в решетку Ь;

в) изучается строение решетки Ь^, в случае когда <р - произвольный решеточный эндоморфизм;

г) изучается проблема вложения данной дистрибутивной решетки Я в булеву решетку Ь той же длины, что и 5, в качестве решетки неподвижных точек для некоторого \/-энД°моРФизма Ф решетки Ь.

Основными результатами этого параграфа являются теоремы 1-4.

Теорема 1. Решётка неподвижных точек любого У -эндоморфизма конечной булевой решётки дистрибутивна.

Теорема 1 доказана в [24] (см. Предложение 3).

Для произвольного изотонного оператора ф решетки Ь назовем эле-

менты решетки Ьф ^-неподвижными точками и обозначим через ф изо-

тонный оператор, определяемый условием ф х — фх V х для всех х (Е Ь.

Теорема 2. Решётка Ь^ для \/-эндоморфизма ср конечной булевой решётки Ь тогда и только тогда будет в ней подрешёткой, когда содержащееся в каждом главном порядковом фильтре, порожденном \/_

неприводимой <Р-неподвижной точкой, множество \/-неприводимых ср-неподвижных точек также является главным фильтром.

Теорема 2 дает необходимые и достаточные условия вложения решетки Ьу в решетку Ь в качестве ее подрешетки. Теорема 2 доказана в [24] (см. Теорема 1).

Пусть ср - эндоморфизм булевой решетки Ь с атомами е;, г = 1,... п, п > 1. Назовем ^-циклом произвольную циклическую перестановку множества {г : г = 1,..., п; ег- А <¿>0 = 0}. (^-цикл (г\.. .ц). I = 1,..., п называется стабильным циклом эндоморфизма ср, если для всех к = 1,..., I выполнено срегк > е^.

Теорема 3. Неподвижные точки любого эндоморфизма ср конечной булевой решётки образуют в ней булеву подрешётку, длина которой равна числу стабильных ср-циклов этого эндоморфизма.

Теорема 3 является следствием теоремы 2 и предложения 1.4, которое доказано в [24] (см. Следствие 2).

Следствие 11. В дистрибутивной решетке Р любое подмножество множества J(P) ненулевых У-неприводимых элементов У - порождает подрешетку в Р тогда и только тогда, когда каждый неприводимый \/-элемент покрыт в ч. у. множестве J(P) не более чем одним элементом.

Если е : 5 —Ь - решеточный мономорфизм для произвольных решеток Я, Ь и р - изотонное преобразование решетки Ь, для которого е(5) = Ьф, то е называется ^»-представлением решетки $ неподвижными точками ((^-представлением решетки 5).

Теорема 4. Всякий мономорфизм дистрибутивной решетки в булеву решетку той же длины является <р-представлением дистрибутивной решетки для подходящего У -эндоморфизма <р булевой решетки.

Теорема 4 доказана по частям. (См. Теорема 2 в [24], Предложение 1 в [29]).

В § 2 главы 1 решаются следующие задачи:

а)для данной дистрибутивной решетки 5 длины п найти пропозициональную формулу А(Х1,...,Хп) брауэровой логики, характеристическое множество которой, рассматриваемое в естественной частичной упорядоченности, изоморфно ч.у. множеству 5;

Напомним [2, стр.365] , что брауэровой логикой называется пропозициональное исчисление, которое является решеткой с О и / такой, что

В1. =

В2. Р ->> (ф Л) = (Р V (3) Я для всех Р, С}, К

Пусть А = Л(Х1,...,Хп) - пропозициональная формула брауэро-вой логики в переменных ... ,Хп и Р - конечное ч. у. множество. Множество Ад двоичных наборов (£ь...,£п)> на которых истинностная функция /(£1,..., £п)? определяемая пропозициональной формулой А(Х\,..., Хп) в двузначной модели брауэровой логики, принимает значение 1, называется характеристическим множеством формулы А. Формула А, для которой формула А —»■ 0 не является тавтологией, называется выполнимой формулой. Характеристическое множество выполнимой формулы непусто, и оно определяет эту формулу с точностью до эквивалентности.

Напомним, что формула А = В называется эквивалентностью формул Л и Б, а сами формулы А, В - эквивалентными формулами, если (А В)к{В А).

Выполнимая формула А называется интерпретацией ч.у. множества Р в брауэровой логике, а ч.у. множество Р называется интерпретируемым в этой логике посредством формулы А, если характеристическое множество формулы А в естественной частичной упорядоченности изоморфно ч. у. множеству Р.

Указанные выше задачи а) и б) решают соответственно теоремы 5 и

мулы & (Qi Х{) для подходящих дизъюнкций % — 1,..., п, в пере-%=1

менных Х\,..., Хп.

Теорема 5 доказана в [29] (см. Теорема 2).

Теорема 6. Пусть в пропозициональной формуле А = &

г£/С{1,...,п}

(О —Хг) = Хг) &; & (Ц] = Xподформулы (¿г являются произвольными (быть может пустыми) дизъюнкциями в переменных Х\,.. Хп для всех % — 1,... ,п. Тогда характеристическое множество формулы Л в естественной частичной упорядоченности образует в булевой решетке Ь, состоящей из всех наборов (£1, вместе с нулевым

элементом решетки Ь плотную (т.е. с единственным атомом) подре-шетку длины не более, чем п — |/| + 1.

Система булевых уравнений \/ (ск^ У ^ = определяемая фор-

к=1

мулой Л, из теоремы 6, связана с одним классом релейно-контактных схем (см. [7]). Для нее