К теории полудистрибутивных решеток

Семенова, Марина Владимировна

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

Семенова, Марина Владимировна АВТОР

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

Новосибирск МЕСТО ЗАЩИТЫ

2000 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

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

Автореферат диссертации на тему "К теории полудистрибутивных решеток"

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

УДК 512.56

РГ5 ОД

Семенова Марина Владимировна

К теории полудистрибутивных решеток

(01.01.06 — математическая логика, алгебра и теория чисел)

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

Новосибирск - 2000

Работа выполнена на кафедре алгебры и математической логики Новосибирского государственного университета

Научные руководители:

доктор физико-математических наук, профессор Горбунов В. А., академик РАН, доктор физико-математических наук, профессор Ершов Ю. Л.

Официальные оппоненты:

доктор физико-математических наук, профессор Пинус А. Г., кандидат физико-математических наук, доцент Больбот А. Д.

Ведущая организация:

Уральский государственный университет

Защита состоится 16 ноября 2000 г. в час. ЬО мин. на

заседании специализированного совета Д.002.23.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: 630090 Новосибирск, пр. акад. Коптюга, 4.

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

Автореферат разослан /3 октября 2000 г.

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

специализированного совета Д.002.23.01 кандидат физико-математических наук -

Ряскин А. Н.

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

Актуальность темы

Решетка Ь называется полудистрибутивной вверх, если для любых элементов х, у, г £ Ь

х V у = х V 2 влечет хУ у = хМ [у Г\г).

Теория полудистрибутивных решеток наряду с теорией модулярных решеток занимает особое положение в общей теории решеток. Понятие полудистрибутивной (вверх) решетки, как и понятие модулярной решетки, является одним из важных обобщений понятия дистрибутивной решетки. Причем свойства полудистрибутивных вверх решеток во многом противоположны свойствам модулярных решеток.

Определение полудистрибутивной решетки впервые появилось в работе Б. Йонссона [20] о подрешетках свободной решетки. Полудистрибутивные вверх решетки естественным образом возникают при изучении многих вопросов, как сформулированных в рамках теории решеток, так имеющих значение и для универсальной алгебры в целом, что отражено в монографии В. А. Горбунова [3]. Полудистрибутивные вверх решетки уже сыграли ведущую роль при изучении свободных решеток (см. монографию Р. Фриза, Я. Ежека и Дж. Б. Нейшна [18]), решеток подквазимногообразий квазимногообразий алгебраических систем [3], разложений в решетках и независимой аксиоматизируемости [2, 23]. Заметное место занимают полудистрибутивные вверх решетки и в теории многообразий решеток [19], теории ручных конгруэнций [5].

что в решетке замкнутых подмножеств произвольной проективной геометрии несократимые разложения обладают свойством замены. Антиподами комбинаторных геометрий являются выпуклые геометрии (то есть пространства замыкания со свойством антизамены). Причем, согласно теореме Р. П. Дилуорса [23], решетка замкнутых подмножеств любой конечной выпуклой геометрии полудистрибутивна вверх.

Для комбинаторных геометрий к настоящему времени была построена глубокая структурная теория, развитие которой было инициировано работами Г. Биркгофа [10], О. Фринка [17], Р. П. Дилуорса и М. Холла [16]. В то же время изучение выпуклых геометрий ограничивалось лишь конечным случаем (см. [21] и обзорную работу [23]). Определение бесконечной выпуклой геометрии было дано в работе К. В. Адаричевой, В. А. Горбунова и В. И. Туманова [8]. Там же были получены первые фундаментальные результаты о таких геометриях.

Одним из основных характеристческих свойств конечной выпуклой геометрии является существование ровно одного несократимого разложения для каждого элемента решетки ее замкнутых подмножеств. Проблема описания решеток, обладающих этим свойством была сформулирована в 40-х годах Р. П. Дилуорсом. Тогда же он показал [14], что конечная решетка обладает указанным свойством тогда и только тогда, когда она полудистрибутивна вверх и полумодулярна вниз. Полудистрибутивные вверх решетки оказались также полезными и при описании решеток с каноническими разложениями, которое было получено В. А. Горбуновым [2]. Отметим также связь теории разложений с вопросами базируемости для классов алгебраических систем. К примеру, вопрос о существовании независимого базиса тождеств (квази-теждеств) может быть переформулирован в терминах существования несократимых разложений в решетках многообразий (квазимногообразий) ^см. [3]).

Первым примером полудистрибутивных решеток оказались подре-шетки свободных решеток [20]. Впоследствии выяснилось, что полудистрибутивными вверх являются также решетки квазимногообразий [3] и решетки выпуклых подмножеств частично упорядоченных множеств [9].

Еще один важный подкласс в классе полудистрибутивных вверх решеток образуют ограниченные снизу решетки. Начало исследованию ограниченых снизу решеток было положено в работе Р. Маккензи [22]. (Наиболее полно теория ограниченных снизу решеток изложена в монографии [18], см. также [6, 7, 13].)

Цель работы

Данная работа посвящена изучению полудистрибутивных вверх решеток. В частности, изучается класс решеток подпорядков частично упорядоченных множеств, которые играют большую роль при изучении ограниченных снизу решеток. Кроме того, большое внимание уделено изучению разложений в полных решетках. Получены результаты о существовании различных типов разложений в таких решетках.

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

В работе получены следующие основные результаты:

1) Найдено описание ограниченых снизу решеток подпорядков.

2) Доказано, что любая решетка, удовлетворяющая условию минимальности Фриза — Нейшна и не содержщая бесконечных £>-циклов вложима в полудистрибутивную вверх решетку подпорядков, что обобщает теорему Сивака.

3) Определено понятие минимального разложения и показано, что все известные классы решеток с единственными несократимыми разложениями являются, в действительности, классами решеток с минимальными разложениями. Кроме того, получена характе-ризация решеток с минимальными разложениями.

4) Описано несколько новых классов решеток с единственными несократимыми разложениями.

Основные методы

В работе используются теоретико-решеточные методы, в частности, методы теории разложений, развитые в работах В. А. Горбунова [2, 3], Р. П. Дилуорса и П. Кроули [14, 15, 12].

Теоретическая и практическая ценность

Работа носит теоретический характер. Ее результаты могут быть использованы специалистами в области теории решеток, универсальной алгебры и дискретной математики для чтения спецкурсов в Новосибирском, Уральском, Саратовском и других государственных университетах.

Научная новизна работы

Все результаты диссертационной работы являются новыми, получены автором самостоятельно и снабжены подробными доказательствами.

Апробация результатов работы

Результаты работы были представлены на Международной конференции "Мальцевские чтения" (Новосибирск, 1997-1998 гг.), Международной конференции, посвященной 60-летию акад. Ю. Л. Ершова (Новосибирск, 2000) и IV Международной алгебраической конференции, посвященной 60-летию проф. Ю. И. Мерзлякова (Новосибирск, 2000), а также на семинарах ""Универсальная хорнова логика" и "Алгебра и логика" Новосибирского государственного университета.

Публикации

Все основные результаты диссертации опубликованы в [27]—[30]. Структура и объем работы

Диссертация состоит из введения, двух глав, разбитых на параграфы, и списка литературы. Утверждения нумеруются тремя цифрами: первая обозначает номер главы, вторая — номер параграфа в этой главе, а третья — номер утверждения в параграфе. Нумерация выносных формул сквозная. Список литературы содержит 44 наименования. Объем диссертации составляет 67 страниц.

Содержание работы

Перейдем к изложению содержания диссертации.

Глава 1 посвящена изучению решеток подпорядков частично упорядоченных множеств. Д. А. Бредихин и Б. М. Шайн [11] показали что решетки подпорядков универсальны, то есть любая решетка вло-жима в решетку подпорядков подходящего частичного порядка. Кроме того, если (X, Я) — частично упорядоченное множество, то, сопоставляя каждому подмножеству <Э в Л его транзитивное замыкание, можно определить оператор замыкания <р на который удовлетворяет свойству антизамены. Причем решетка подпорядков 0(Х,Н) изоморфна решетке замкнутых относительно <р подмножеств в Я.

В параграфе 1.1 устанавливаются некоторые основные свойства решеток подпорядков. На множестве .7(Ь) всех неразложимых элементов решетки Ь определим отношение зависимости О (см. [18]), полагая для всех а,Ь Е J{L)

аОЬ тогда и только тогда, когда а ^ Ь V р для некоторого р£Ьша<£.Ь\\/р для всех 61 < Ь.

Последовательность а,-, г < п, неразложимых в Ь элементов называется О-последователъностъю, если а,-1)а1+1 для всех г < п — 1. £>-последовательность ао,... ,ап_ь где п ^ 2, называется О-циклом, если ап-1 = ао- .О-цикл называется полным, если все его элементы вполне неразложимы.

Следующая теорема описывает полудистрибутивные вверх решетки подпорядков.

Теорема 1.1.3. Для частично упорядоченного множества (X, Я) следующие условия равносильны:

1) 0(Х, Я) — полудистрибутивная вверх решетка;

2) Я) не содержит бесконечных Б-последовательностей;

3) любая подрешетка в 0(Х, Я) не содержит полных О-циклов;

4) (X, Я) не содержит частично упорядоченных подмножеств, изоморфных из + 1 и {ы + 1)а.

Решеточный гомоморфизм Л : К —> Ь называется ограниченным снизу, если для любого а 6 £ множество {х £ К : 1г(х) > а} либо пусто, либо имеет наименьший элемент. Мы говорим также, что решетка Ь ограничена снизу, если любой гомоморфизм Л : К —> £, где К — конечно порожденная решетка, является ограниченным снизу.

Согласно теореме Б. Сивака [25] конечная решетка ограничена снизу тогда и только тогда, когда она вложим а в решетку подпорядков некоторого конечного частичного порядка. Существуют и другие свойства, эквивалентные в классе конечных решеток ограниченности снизу. В общем случае эти свойства не равносильны и образуют иерерхию, которая была детально изучена в работе К. В. Адаричевой и В. А. Горбунова [7]. В параграфе 1.1 дается также характеризация решеток подпорядков, удовлетворяющих некоторым из этих свойств.

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

Теорема 1.2.4. Для ч. у. множества (Х,Н) следующие условия равнослъны:

1) решетка 0(Х, Я) обладает полным свойством Йонссона;

2) решетка 0(Х, Я) ограничена снизу;

3) ч. у. лтожество (X, Щ имеет конечную высоту.

Заметим, что при доказательстве этой теоремы использовался т^т факт, что решетка, обладающая полным свойством Йонссона, ограничена снизу. Доказательство этого утверждения аналогично доказательству соответствующего результата для свойства Йонссона, приведенному в [18].

Параграф 1.3 посвящен доказательству еще одного основного результата диссертационной работы, следствием которого является упоминавшаяся выше теорема Б. Сивака.

Теорема 1.3.2. Пусть Ь — решетка, удовлетворяющая условию минимальности Фриза — Нейшна. Если Ь не содержит, бесконечных Б-последовательностей, то Ь вложима в полудистрибутивную

вверх решетку 0(Х, Я) подпорядков некоторого частичного порядка Я на множестве X.

Пусть О обозначает класс решеток, изоморфных решеткам квазимногообразий. Следуя [1, 3], функцию Н на полной решетке Ь мы называем оператором эквационального замыкания или, кратко, оператором эквазамыкания, если Л обладает свойствами (/г1)-(/гб).

(Л1) Л является оператором замыкания на Ь, т. е. а < /г(а); а < Ь влечет Л(а) < /1(6); /г(Л(а)) = Л(а) для всех а,Ь £ Ь.

(Л2) Л(0) = 0, где 0 — нуль решетки Ь.

(ЛЗ) Л(а) = к(Ь) влечет Л(а) = Л(а Л Ь) для всех а,Ь € Ь.

(/г4) Д(а) Л (Ь V с) = (/»(а) Л Ь) V (к(а) Л с) для всех а, Ь, с £ I.

(Л5) Для всех атомов а, Ь, с, <1 решетки Ь если интервал [0, а V</] содержит два атома, <1 Л(а), й < к(с) и к (с) = /г(аУб), то Л(с) = /г(Ь\/(/).

(/16) Существуют кокомпактный элемент а (он называется псевдонулем оператора Л), алгебраическая решетка А и изоморфизм д : [О,а] Бр(А) такие, что Л(а) = а и д(к(х)) = [/\д(х), 1л] для всех х < а.

Заметим, что, согласно [1], любая решетка квазимногообразий допускает оператор эквазамыкания.

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

Теорема 1.4.3. Для частично упорядоченного множества (Х,Я) следующие условия равносильны:

1) 0(Х, Я) в 0;

2) (X, Я) — конечное или счетное множество, имеющее высоту не более чем 2 и не содержащее ч. у. подмножеств вида 22, Р\ и Р? (см. рис. 1).

Р» 22

Рис. 1. Ч. у. множества Р\, Р®, 22

Глава 2 посвящена изучению различных типов разложений в полных решетках. Основы теории разложений были заложены в работах Р. П. Дилуорса и П. Кроули [15, 12]. Представление элемента а полной решетки Ь в виде а = \/ В называется разложением, если элементы множества В вполне неразложимы, то есть Ь = \/ X, X С ¿, влечет Ь € X для всех Ь 6 В. Это разложение несократимо, если а ф \/{В — Ь) для всех Ь £ В.

Известно, что в дистрибутивной решетке каждый элемент имеет не более одного несократимого разложения. В каких решетках любой ненулевой элемент имеет единственное несократимое разложение? Далее такие решетки будем называть решетками с единственными несократимыми разложениями. Для конечных решеток ответ на этот вопрос был найден в 1940 году Р. П. Дилуорсом [14]. Он доказал, что конечная решетка Ь является решеткой с единственными несократимыми разложениями тогда и только тогда, когда Ь локально дистрибутивна. Известно также (см. [21, 23]), что класс конечных решеток с единственными несократимыми разложениями совпадает с классом конечных выпуклых геометрий. В 1960 году Р. П. Дилуорс и П. Кроули [15] охарактеризовали класс коалгебраических сильно коатомных решеток с единственными несократимыми разложениями. Наконец, в 1978 году В. А. Горбунов [2] дал описание класса дистрибутивных решеток с (единственными) несократимыми разложениями. Близкие вопросы рассматривались также в работах других авторов (см [24, 26]).

Сразу отметим, что в основном в диссертационной работе изучаются разложения в следующих классах решеток:

в классе непрерывных вверх вполне полудистрибутивных вверх решеток;

в классе непрерывных вверх и вниз решеток;

в классе полумодулярных вверх вполне полудистрибутивных вверх решеток;

в классе полумодулярных вверх непрерывных вниз решеток.

В параграфе 2.1 найдены необходимые и достаточные условия существования разложений в двух из перечисленных выше классов и пре-ведены некоторые вспомогательные результаты. Будем говорить, что несократимые разложения в решетке Ь обладают свойством замены, если каждый элемент а € Ь имеет по крайней мере одно несократимое разложение и если а = \/ Я = \/ <3 — два несократимых разложения, то для любого г € Л найдется q 6 <3, такой что а = \/(Я \ {г}) V д и это разложение несократимо. Параграф 2.2 посвящен описанию в упомянутых выше классах решеток, в которых несократимые разложения обладают свойством замены. Заметим, что решетки, в которых несократимые разложения обладают свойством замены, были описаны Р. П. Дилуорсом и П. Кроули [12, 15] в классе полумодулярных вниз коалгебраических сильно коатомных решеток.

Разложение а = V В называется лшнимальным, если для любого разложения а = \/ С имеет место включение В С С. Это определение является основным определением параграфа 2.3. Кроме того, в этом параграфе получено следующее описание решеток, в которых каждый элемент имеет минимальное разложение:

Следствие 2.3.2. Решетка Ь является решеткой с минимальными разложениями тогда и только тогда, когда Ь вполне полудистрибутивна вверх, полумодулярна вниз и сильно коатомна.

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

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

этих результатов существенно опирается на характеризацию решеток с минимальными разложениями, полученную в параграфе 2.3. Более того, используя эту характеризацию, нетрудно установить, что во всех известных классах единственные несократимые разложения являются, в действительности, минимальными разложениями.

Следующее условие рассматривалось в работе [26].

для любого а £ Ь и любых ж, у € CJ(L) ^

а V х = а V у и. х а влечет х = у.

Справедливы следующие теоремы.

Теорема 2.4.4. Для непрерывной вверг вполне полудистрибутивной вверх решетки Ь следующие условия равносильны:

1) Ь имеет минимальные разложения;

2) Ь имеет единственные несократимые разложения;

3) Ь сильно коатомна и удовлетворяет условию (4);

4) Ь сильно коатомна и полумодулярна вниз;

5) Ь сильно коатомна и изоморфна решетке С1(Х,ф) замкнутых подмножеств некоторой выпуклой геометрии (Х,ф).

Теорема 2.4.5. Для непрерывной вверх и вниз решетки Ь следующие условия равносильны:

1) Ь имеет минимальные разложения;

2) Ь имеет единственные несократимые разложения;

3) Ь сильно коатомна и удовлетворяет условию (4);

4) Ь сильно коатомна, полудистрибутивна вверх и полумодулярна вниз;

5) Ь сильно коатомна и локально дистрибутивна;

6) Ь сильно коатомна и изоморфна решетке С1(Х,ф) замкнутых подмножеств некоторой выпуклой геометрии (X, ф).

Теорема 2.4.6. Для полумодулярной вверх вполне полудистрибутивной вверх (либо полумодулярной вверх и непрерывной вниз) решетки Ь следующие условия равносильны:

1) Ь имеет минимальные разложения;

2) Ь имеет единственные несократимые разложения;

3) Ь сильно коатомна и удовлетворяет условию (4);

4) Ь сильно коатомна и полумодулярна вниз (и полудистрибутивна вверх);

5) Ь сильно коатолта и изолюрфна решетке С1(Х,ф) замкнутых подмножеств некоторой выпуклой геометрии (X, ф).

В случае, когда решетка Ь непрерывна вниз и полумодулярна вверх, эти условия равносильны также следующему:

6) Ь сильно коатомна и локально дистрибутивна.

Как отмечалось выше, В. А. Горбунов в работе [2] дал описание дистрибутивных решеток с (единственными) несократимыми разложениями. Там же он поставил вопрос о поиске необходимых и достаточных условий для существования несократимого разложения для произвольного элемента дистрибутивной решетки. Следующее предложение дает ответ на этот вопрос.

Теорема 2.4.7. Пусть Ь — дистрибутивная решетка и х 6 Ь, тогда следующие условия равносильны:

1) х имеет минимальное разложение;

2) х имеет каноническое разложение;

3) х имеет несократимое разложение;

4) х вполне полудистрибутивен вверх, а решетка [0, х] коатомна.

Автор глубоко признателен В. А. Горбунову за постановку вопросов, постоянное внимание к работе и всемерную поддержку.

Автор благодарит Ю. Л. Ершова за внимание к работе и ряд полезных замечаний, высказанных при ее обсуждении.

Литература

[1] К. В. Адаринева, В. А. Горбунов, Оператор эквазамыкания и запрещенные полудистрибутивные решетки, Сиб. Матем. ж., 30 (1989), No 6, 7-25.

[2] В. А. Горбунов, Канонические разложения в полных решетках, Алгебра и логика, 17 (1978), No 5, 495-511.

[3] В. А. Горбунов, Алгебраическая теория квазимногообразий, Новосибирск, Научная книга, 1999.

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

[5] Д. Хобби, Р. Маккензи, Строение конечных алгебр, М.: Мир, 1993.

[6] К. V. Adaricheva, Two embedding theorems for lower bounded lattices, Algebra Univers., 36 (1996), No 4, 425-430.

[7] К. V. Adaricheva, V. A. Gorbunov, On lower bounded lattices, Algebra Univers., to appear.

[8] К. V. Adaricheva, V. A. Gorbunov and V. I. Tumanov, Join semidistributive lattices and convex geometries, to appear.

[9] M. K. Bennett, G. Birkhoff, The convexity lattice of a poset, Order, 2 (1985), No 2, 223-242.

[10] G. Birkhoff, Abstract linear dependence and lattices, Amer. J. Math., 57 (1935), 800-804.

[11] D. Bredikhin, B. Schein, Representation of ordered semigroups and lattices by binary relations, Colloq. Math., 39 (1978), 1-12.

[12] P. Crawley, R. P. Dilworth, Algebraic theory of lattices, Englewood Cliffs, NJ, Prentice-Hall, 1973.

[13] A. Day, Characterization of finite lattices that are bounded-homo-morphic images or sublattices of free lattices, Can. J. Math., 31 (1979), No 1, 69-78.

[14] R. P. Dilworth, Lattices with unique irreducible decompositions, Ann. Math., 41 (1940), No 4, 771-776.

[15] R. P. Dilworth, P. Crawley, Decomposition theory for lattices without chain conditions, Trans. Amer. Math. Soc., 96 (1960), No 1, 1-22.

[16] R. P. Dilworth, M. Hall, The embedding problem for modular lattices, Ann. Math., 45 (1944), 450-456.

[17] 0. Frink, Complemented modular lattices and projective spaces of infinite dimension, Trans. Amer. Math. Soc., 60 (1946), 452-467.

[18] R. Freeze, J. Jezek, and J. B. Nation, Free Lattices, AMS, Providence, Rhode Island, 1995.

[19] P. Jipsen, H. Rose, Varieties of Lattices, Lect. Notes in Math., 1533, Springer Verlag, Berlin, 1992.

[20] B. Jonsson, Sublattices of a free lattice, Can. J. Math., 13 (1961), 256-264.

[21] B. Korte, L. Lovdsz and R. Schräder, Greedoids, Springer Verlag, Berlin, 1991.

[22] R. McKenzie, Equational bases and nonmodular lattice varieties, Trans. Amer. Math. Soc., 174 (1972), No 1, 1-43.

[23] B. Monjardet, The consequences of Dibvorth's work on lattices with unique irreducible decompositions, In: The Dilworth theorems: selected papers of R. P. Dilworth (ed. by K. P. Bogart, R. Freese, J. P. S. Kung), Birkhaser, Boston — Basel — Berlin, 1990.

[24] G. Richter, The Kuros - Ore theorem, finite and infinite decompositions, Stud. Sei. Math. Hung., 17 (1982), No 1-3, 243-250.

[25] B. Sivak, Representation of finite lattices by orders on finite sets, Math. Slovaca, 28 (1978), No 2, 203-215.

[26] A. Walendziak, Join decompositions in lower continuous lattices, Stud. Sei. Math. Hung., 28 (1993), No 1-2, 131-134.

Работы автора по теме диссертации

[27] М. В. Семенова, Решетки подпорядков, Сиб. Матем. ж., 40 (1999), No. 3, 673-682.

[28] М. В. Семенова, Решетки с единственными несократимыми разложениями, Алгебра и логика, 39 (2000), N0 1, 93-103.

[29] М. В. Семенова, Единственные несократимые разложения в полных решетках, Логика и приложения, издательство ИДМИ, 2000, стр. 140.

[30] М. В. Семенова, Разложения в полных решетках, препринт N0 53, издательство ИДМИ, 2000, 23 стр.

Подписано в печать 05.10.2000 Формат 60x84/16 Заказ № 504 Усл.-п.л. 1,0 Тираж 80

Отпечатано на полиграфическом участке РИЦ НГУ 630090, Новосибирск-90, Пирогова, 2

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Семенова, Марина Владимировна

Введение.

Глава 1. Решетки подпорядков и ограниченные снизу решетки.

1. Свойства, близкие к ограниченности снизу.

2. Ограниченные снизу решетки подпорядков.

3. Теорема о вложении в решетки подпорядков.

4. Решетки подпорядков, представимые в виде решеток квазимногообразий.

Глава 2. Разложения в решетках.

1. Существование разложений.

2. Несократимые разложения со свойством замены.

3. Минимальные разложения.

4. Единственные несократимые разложения.

Введение диссертация по математике, на тему "К теории полудистрибутивных решеток"

Решетка Ь называется полудистрибутивной вверх, если для любых элементов х,у,г £ Ь х V у = х V -г влечет х V у = х V (у А г).

Двойственным образом определяются полудистрибутивные вниз решетки. Теория полудистрибутивных решеток наряду с теорией модулярных решеток занимает особое положение в общей теории решеток. Понятие полудистрибутивной (вверх) рештеки, как и понятие модулярной решетки, является одним из важных обобщений понятия дистрибутивной решетки. Причем свойства полудистрибутивных вверх решеток во многом противоположны свойствам модулярных решеток.

Определение полудистрибутивной решетки впервые появилось в работе Б. Йонссона [31] о подрешетках свободной решетки. Полудистрибутивные вверх решетки естественным образом возникают при изучении многих вопросов, как сформулированных в рамках теории решеток, так имеющих значение и для универсальной алгебры в целом, что отражено в монографии В. А. Горбунова [6]. Полудистрибутивные вверх решетки уже сыграли ведущую роль при изучении свободных решеток (см. монографию Р. Фриза, Я. Ежека и Дж. Б. Ней-шна [29]), решеток подквазимногообразий квазимногообразий алгебраических систем [6], разложений в решетках и независимой аксиоматизируемости [5, 35]. Заметное место занимают полудистрибутивные вверх решетки и в теории многообразий решеток [30], теории ручных конгруэндий [9].

Следует упомянуть еще об одном естественном комбинаторном приложении теории полудистрибутивных вверх решеток, которое наиболее отчетливо высвечивает как тесную связь упомянутого классса решеток с классом модулярных решеток, так и некоторую оппозиционность этих двух классов по отношению друг к другу. Известно (см. книгу Г. Гретцера [8]), что любую модулярную решетку с дополнениями можно вложить в модулярную геометрическую решетку. С другой стороны, класс модулярных геометрических решеток совпадает с классом так называемых проективных геометрий. Таким образом, любая модулярная решетка с дополнениями вложима в решетку замкнутых подмножеств некоторого пространства замыкания со свойством замены Штейница-Маклейна (или комбинаторной геометрии). Следует также отметить, что в решетке замкнутых подмножеств произвольной проективной геометрии несократимые разложения обладают свойством замены. Антиподами комбинаторных геометрий являются выпуклые геометрии (то есть пространства замыкания со свойством антизамены). Причем, согласно теореме Р. П. Дилуорса [35], решетка замкнутых подмножеств любой конечной выпуклой геометрии полудистрибутивна вверх.

Для комбинаторных геометрий к настоящему времени была построена глубокая структурная теория, развитие которой было инициировано работами Г. Виркгофа [16], О. Фринка [26], Р. П. Дилуорса и М. Холла [25]. Однако изучение выпуклых геометрий ограничивалось лишь конечным случаем (см. [33] и обзорную работу [35]). Определение бесконечной выпуклой геометрии было дано в работе К. В. Адаричевой, В. А. Горбунова и В. И. Туманова [14]. Там же были получены первые фундаментальные результаты о таких геометриях.

Одним из основных характеристческих свойств конечной выпуклой геометрии является существование ровно одного несократимого разложения для каждого элемента решетки ее замкнутых подмножеств. Проблема описания решеток, обладающих этим свойством была сформулирована в 40-х годах Р. П. Ди-луорсом. Тогда же он показал [23], что конечная решетка обладает указанным свойством тогда и только тогда, когда она полудистрибутивна вверх и полу-модулярна вниз. Полудистрибутивные вверх решетки оказались также полезными и при описании решеток с каноническими разложениями, которое было получено В. А. Горбуновым [5]. Отметим также связь теории разложений с вопросами базируемости для классов алгебраических систем. К примеру, вопрос о существовании независимого базиса тождеств (квазитеждеств) может быть переформулирован в терминах существования несократимых разложений в решетках многообразий (квазимногообразий) (см. [6]).

Первым примером полудистрибутивных решеток оказались подрешетки свободных решеток [31]. Впоследствии выяснилось, что полудистрибутивными вверх являются также решетки квазимногообразий [6] и решетки выпуклых подмножеств частично упорядоченных множеств [15].

Еще один важный подкласс в классе полудистрибутивных вверх решеток образуют ограниченные снизу решетки. Начало исследованию ограниченых снизу решеток было положено в работе Р. Маккензи [34]. (Наиболее полно теория ограниченных снизу решеток изложена в монографии [29], см. также [11, 13, 21].)

В работе получены следующие основные результаты:

1) Найдено описание ограниченых снизу решеток подпорядков.

2) Доказано, что любая решетка, удовлетворяющая условию минимальности Фриза — Нейшна и не содержщая бесконечных ^-циклов вложима в полудистрибутивную вверх решетку подпорядков, что обобщает теорему Сивака.

3) Определено понятие минимального разложения и показано, что все известные классы решеток с единственными несократимыми разложениями являются, в действительности, классами решеток с минимальными разложениями. Кроме того, получена характеризация решеток с минимальными разложениями.

4) Описано несколько новых классов решеток с единственными несократимыми разложениями.

В работе используются теоретико-решеточные методы, в частности, методы теории разложений, развитые в работах В. А. Горбунова [5, 6], Р. П. Дилуорса и П. Кроули [23, 24, 20].

Результаты работы были представлены на Международной конференции "Мальцевские чтения" (Новосибирск, 1997-1998 гг.), Международной конференции, посвященной 60-летию акад. Ю. Л. Ершова (Новосибирск, 2000) и IV Международной алгебраической конференции, посвященной 60-летию проф. Ю. И. Мерзлякова (Новосибирск, 2000), а также на семинарах "Универсальная хорнова логика" и "Алгебра и логика" Новосибирского государственного университета.

Все основные результаты диссертации опубликованы в [41]—[44].

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Семенова, Марина Владимировна, Новосибирск

1. К. В. Адаричева, Строение конечных решеток подполурешеток, Алгебра и логика, 30 (1991), No 4, 385-404.

2. К. В. Адаричева, В. А. Горбунов, Оператор эквазамыкания и запрещенные полудистрибутивные решетки, Сиб. Матем. ж., 30 (1989), No б, 7-25.

3. К. В. Адаричева, В. А. Горбунов, В. Дзёбяк, Алгебраические точечные решетки квазимногообразий, Алгебра и логика, 36 (1997), No 4, 363-386.

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

5. В. А. Горбунов, Канонические разложения в полных решетках, Алгебра и логика, 17 (1978), No 5, 495-511.

6. В. А. Горбунов, Алгебраическая теория квазимногообразий, Новосибирск, Научная книга, 1999.

7. В. А. Горбунов, В. И. Туманов, Об одном классе решеток квазимногообразий, Алгебра и логика, 19 (1980), No 1, 59-80.

8. Г. Гретцер, Общая теория решеток, М.: Мир, 1982.

9. Д. Хобби, Р. Маккензи, Строение конечных алгебр, М.: Мир, 1993.

10. М. Е. Adams, Ж Dziobiak, (^-universal quasivarieties of algebras, Proc. Amer. Math. Soc., 120 (1994), No 4, 1053-1059.

11. К. V. Adaricheva, Two embedding theorems for lower bounded lattices, Algebra Univers., 36 (1996), No 4, 425-430.

12. К. V. Adaricheva, Dziobiak and V. A. Gorbunov, Finite atomistic lattices that can be represented as lattices of quasivarieties, Fund. Math., 142 (1993), 19-43.

13. K. V. Adaricheva, V. A. Gorbunov, On lower bounded lattices, Algebra Univers., to appear.

14. K. V. Adaricheva, V. A. Gorbunov and V. I. Tumanov, Join semidistributive lattices and convex geometries, to appear.

15. M. K. Bennett, G. Birkhoff, The convexity lattice of a poset, Order, 2 (1985), No 2, 223-242.

16. G. Birkhoff, Abstract linear dependence and lattices, Amer. J. Math., 57 (1935), 800-804.

17. G. Birkhoff, Rings of sets, Duke Math. J., 3 (1937), No 2, 442-454.

18. D. Bredikhin, B. Schein, Representation of ordered semigroups and lattices by binary relations, Colloq. Math., 39 (1978), 1-12.

19. P. Crawley, Decomposition theory for nonsemimodular lattices, Trans. Amer. Math. Soc., 99 (1961), No 1, 246-254.

20. P. Crawley, R. P. Dilworth, Algebraic theory of lattices, Englewood Cliffs, NJ, Prentice-Hall, 1973.

21. A. Day, Characterization of finite lattices that are bounded-homomorphic images or sublattices of free lattices, Can. J. Math., 31 (1979), No 1, 69-78.

22. V. Duquenne, On the core of finite lattices, Discrete Math., 88 (1991), No 2-3, 133-147.

23. R. P. Dilworth, Lattices with unique irreducible decompositions, Ann. Math., 41 (1940), No 4, 771-776.

24. R. P. Dilworth, P. Crawley, Decomposition theory for lattices without chain conditions, Trans. Amer. Math. Soc., 96 (1960), No 1, 1-22.

25. R. P. Dilworth, M. Hall, The embedding problem for modular lattices, Ann. Math., 45 (1944), 450-456.26. 0. Frink, Complemented modular lattices and projective spaces of infinite dimension, Trans. Amer. Math. Soc., 60 (1946), 452-467.

26. P. H. Edelman, R. E. Jamison, The theory of convex geometries, Geom. Ded-icata, 19 (1985), No 2, 247-270.

27. M. Erne, On the existence of decompositions in lattices, Algebra Univers., 16 (1983), No 3, 338-343.

28. R. Freeze, J. Jezek, and J. B. Nation, Free Lattices, AMS, Providence, Rhode Island, 1995.

29. P. Jipsen, H. Rose, Varieties of Lattices, Lect. Notes in Math., 1533, Springer Verlag, Berlin, 1992.

30. B. Jonsson, Sublattices of a free lattice, Can. J. Math., 13 (1961), 256-264.

31. B. Jonsson, J. B. Nation, A report on sublattices of a free lattice, Contrib. Universal Algebra (Szeged, 1975), Colloq. Math. Soc. J. Bolyai, 17 (1977), 233-257.

32. B. Körte, L. Loväszaiid R. Schräder, Greedoids, Springer Verlag, Berlin, 1991.

33. R. McKenzie, Equational bases and nonmodular lattice varieties, Trans. Amer. Math. Soc., 174 (1972), No 1, 1-43.

34. G. Richter, The Kuros Ore theorem, finite and infinite decompositions, Stud. Sci. Math. Hung., 17 (1982), No 1-3, 243-250.

35. B. Sivak, Representation of finite lattices by orders on finite sets, Math. Slovaca, 28 (1978), No 2, 203-215.

36. A. Walendziak, Meet decompositions in complete lattices, Period. Math. Hung., 21 (1990), No 3, 219-222.

37. A. Walendziak, Join decompositions in lower continuous lattices, Stud. Sci. Math. Hung., 28 (1993), No 1-2, 131-134.

38. A. Walendziak, Unique irredundant decompositions in upper continuous lattices, Czech. Math. J., 45 (1995), No 2, 193-199.Работы автора по теме диссертации

39. М. В. Семенова, Решетки подпорядков, Сиб. Матем. ж., 40 (1999), No. 3, 673-682.

40. М. В. Семенова, Решетки с единственными несократимыми разложениями, Алгебра и логика, 39 (2000), No 1, 93-103.

41. М. В. Семенова, Единственные несократимые разложения в полных решетках, Логика и приложения, издательство ИДМИ, 2000, стр. 140.

42. М. В. Семенова, Разложения в полных решетках, препринт No 53, издательство ИДМИ, 2000, 23 стр.