Федеральноеагентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Вятскийгосударственный гуманитарный университет
Математическийфакультет
Кафедра алгебры и геометрии
Выпускнаяквалификационная работа
Обобщенно булевы решетки
Выполнил:
студентV курса математического факультета
Онучин Андрей Владимирович
Научныйруководитель:
к.ф.-м.н.,доцент кафедры алгебры и геометрии ВятГГУ
Чермных Василий Владимирович
Рецензент:
д.ф.-м.н., профессор, зав. кафедрой алгебры игеометрии ВятГГУ
Вечтомов Евгений Михайлович
Работа допущена к защите вгосударственной аттестационной комиссии
«___» __________2005 г. Зав. кафедрой Е.М.Вечтомов
«___»__________2005 г. Деканфакультета В.И. Варанкина
Киров
2005
Содержание
Введение… 3
Глава 1… 4
1.1. Упорядоченные множества… 4
1.2. Решётки… 5
1.3. Дистрибутивные решётки… 7
1.4. Обобщённые булевы решётки, булевы решётки… 8
1.5. Идеалы… 9
Глава 2… 11
2.1. Конгруэнции… 11
2.2. Основная теорема… 16
Библиографический список… 22
Введение
Булева решёткапредставляет собой классический математический объект, который начал интенсивноизучаться в работах М. Стоуна 30-е годы 20-го века, расширением этого понятиядо обобщённо булевых решёток занимались Г. Гретцер и Е. Шмидт в своих трудахконца 50-х годов.
Цель данной работы: установлениевзаимно однозначного соответствия между конгруэнциями и идеалами в обобщённобулевых решётках. (Для булевых решёток это положение доказано в книге [2], крометого, сформулировано в книге [3] в качестве упражнений). А также – установлениесвязи между обобщённо булевыми решётками и булевыми кольцами.
Данная дипломная работасостоит из двух глав: в первой главе даны основные понятия, а так же содержатсябазовые сведения из теории решёток. Кроме того, в первой главе рассмотренонесколько простейших теорем.
Вторая глава представляетсобой основную часть данной дипломной работы. Опираясь на работы Гретцера Г.,но более подробно, рассмотрены свойства конгруэнций и связь конгруэнций иидеалов в обобщённо булевых решётках (Теоремы 2.1, 2.2, 2.3.). Кроме тогореализована основная цель данной дипломной работы: установлена связь междубулевыми кольцами и обобщённо булевыми решётками (Основная теорема).
Глава 11.1. Упорядоченные множества
Упорядоченныммножеством P называется непустое множество, накотором определено бинарное отношение />,удовлетворяющее для всех /> следующимусловиям:
1. Рефлексивность: />.
2. Антисимметричность. Если/> и />, то />.
3. Транзитивность. Если /> и />, то />.
Если /> и />, то говорят, что /> меньше />или /> больше />, и пишут /> или />.
Примеры упорядоченныхмножеств:
1. Множество целых положительных чисел, а /> означает,что /> делит />.
2. Множество всехдействительных функций /> на отрезке /> и /> означает, что /> для />.
Цепьюназывается упорядоченное множество, на котором длялюбых /> имеет место /> или />.
Используя отношениепорядка, можно получить графическое представление любого конечногоупорядоченного множества P.Изобразим каждый элемент множества P в виде небольшого кружка, располагая x выше y,если />. Соединим x и y отрезком. Полученная фигура называется диаграммойупорядоченного множества P./> />
Примеры диаграмм упорядоченногомножества: 1.2. Решётки
Верхней гранью подмножества Х вупорядоченном множестве Р называется элемент a из Р, больший или равный всех x из X.
Точная верхняя грань подмножества X упорядоченного множества P – это такая его верхняя грань,которая меньше любой другой его верхней грани. Обозначается символом sup Xи читается «супремум X».
Согласно аксиомеантисимметричности упорядоченного множества, если точная верхняя граньсуществует, то она единственна.
Понятия нижней грани иточной нижней грани (которая обозначается inf X и читается «инфинум») определяются двойственно. Также, согласноаксиоме антисимметричности упорядоченного множества, если точная нижняя грань X существует, то она единственна./> />
Решёткой /> называется упорядоченное множество L, в котором любые два элемента xи y имеют точную нижнюю грань, обозначаемую />, и точную верхнюю грань,обозначаемую />.
Примеры решёток:
Примечание. Любая цепьявляется решёткой, т.к. /> совпадаетс меньшим, а /> с большим из элементов />.
Наибольший элемент, то есть элемент,больший или равный каждого элемента упорядоченного множества, обозначают 1, анаименьший элемент, то есть меньший или равный каждого элемента упорядоченногомножества, обозначают 0.
На решётке можно рассматривать двебинарные операции:
/> - сложение и
/> - произведение
Эти операции обладают следующимисвойствами:
1. />, /> идемпотентность;
2. />, /> коммутативность;
3. />, /> ассоциативность;
4. />, /> законы поглощения.
ТЕОРЕМА 1.1. Пусть L — множество с двумя бинарными операциями />, обладающими свойствами(1) – (4). Тогда отношение /> (или />) является порядком на L, а возникающее упорядоченноемножество оказывается решёткой, причём: /> и />.
Доказательство. Рефлексивность отношения /> вытекает из свойства (1). Заметим,что оно является следствием свойства (4):
/>
/>
Если /> и />, то есть /> и />, то в силу свойства (2),получим />. Это означает, чтоотношение /> антисимметрично.
Если /> и />, то применяя свойство (3),получим: />, что доказываеттранзитивность отношения />.
Применяя свойства (3),(1), (2), получим:
/>,
/>.
Следовательно, /> и />.
Если /> и />, то используя свойства (1)– (3), имеем:
/>, т.е. />.
По определению точнейверхней грани убедимся, что />.
Из свойств (2), (4)вытекает, что /> и />.
Если /> и />, то по свойствам (3), (4)получим:
/>.
Отсюда по свойствам (2) и(4) следует, что
/>.
Таким образом, />.
Пусть Lрешётка, тогда её наибольший элемент1 характеризуется одним из свойств:
1./> />.
2./> />.
Аналогичнохарактеризуется наименьший элемент />:
1./> />
2./> />.
1.3. Дистрибутивные решётки
Решётка L называется дистрибутивной,если для любых /> выполняется:
D1. />.
D2. />.
В любой решётке тождестваD1 и D2 равносильны. Доказательство этого факта содержится в книге[2], стр. 24.
Примерыдистрибутивных решёток:
1. Множествоцелых положительных чисел, /> означает,что /> делит />. Это решётка с операциямиНОД и НОК.
2. Любаяцепь является дистрибутивной решёткой./> />
ТЕОРЕМА 1.2. Решётка Lс 0 и 1 является дистрибутивнойтогда и только тогда, когда она не содержит подрешёток вида
Доказательство этойтеоремы можно найти в книге [1].1.4. Обобщённобулевы решётки, булевы решётки
Всюду далеепод словом «решётка» понимается произвольная дистрибутивная решётка с 0.
Решётка Lназывается обобщённой булевой, если для любых элементов /> и d из L, таких что/> существует относительноедополнениена интервале />, т.е.такой элемент /> из L, что /> и />.
(Для />, />, интервал />|/>; для/>, />можно так же определить полуоткрытыйинтервал/>|/>).
ТЕОРЕМА1.3. (Оединственности относительного дополнения в обобщённо булевой решётке). Каждыйэлемент обобщённо булевой решётки L имеет только одно относительное дополнение напромежутке.
Доказательство. Пусть для элемента /> существует дваотносительных дополнения /> и /> на интервале />. Покажем, что />. Так как /> относительное дополнениеэлемента /> на промежутке />, то /> и />, так же /> относительное дополнениеэлемента /> на промежутке />, то /> и />.
Отсюда
/>/>,
таким образом />, т.е. любой элементобобщённой булевой решётки имеет на промежутке только одно относительноедополнение.
Решётка L называетсябулевой, если для любого элемента /> изL существует дополнение,т.е. такой элемент /> из L, что /> и />
ТЕОРЕМА1.4. (Оединственности дополнения в булевой решётке). Каждый элемент булевой решётки L имеет только однодополнение.
Доказательство аналогично доказательству теоремы 1.3.
ТЕОРЕМА 1.5. (О связи обобщённобулевых и булевых решёток).
Любая булева решёткаявляется обобщённо булевой, обратное утверждение не верно.
Доказательство. Действительно, рассмотримпроизвольную булеву решётку L. Возьмём элементы a и d из L, такие что />. Заметим, чтоотносительным дополнением элемента a до элемента dявляется элемент />, где a’ – дополнение элемента a в булевой решётке L. Действительно, />, кроме того />. Отсюда следует, чторешётка L является обобщённо булевой.
1.5.Идеалы
Подрешётка Iрешётки L называется идеалом,если для любых элементов /> и /> элемент /> лежит в I. Идеал I называется собственным,если />. Собственный идеал решёткиL называется простым,если из того, что /> и /> следует /> или />.
Так какнепустое пересечение любого числа идеалов снова будет идеалом, то мы можемопределить идеал, порождённый множеством Hв решётке L, предполагая, что H не совпадает с пустыммножеством. Идеал, порождённый множеством H будет обозначаться через(H]. Если />, то вместо /> будем писать /> и называть /> главным идеалом.
ТЕОРЕМА1.5.Пусть L – решётка, а H и I– непустые подмножества вL, тогда Iявляется идеалом тогда итолько тогда, когда если />, то />, и если />, то />.
Доказательство.Пусть I – идеал, тогда /> влечёт за собой />, так как I– подрешётка. Если />, то /> и условия теоремыпроверены.
Обратно,пусть I удовлетворяет этим условиям и />. Тогда /> и так как />, то />, следовательно, I – подрешётка. Наконец,если /> и />, то />, значит, /> и I является идеалом.
Глава 22.1. Конгруэнции
Отношениеэквивалентности(т.е. рефлексивное, симметричное и транзитивное бинарное отношение) /> на решётке L называется конгруэнцией на L, если /> и/> совместно влекут за собой /> и /> (свойство стабильности).Простейшими примерами являются ω, ι, определённые так:
/>(ω)/>/>; />(ι)для всех />.
Для /> обозначим через /> смежный класс,содержащий элемент />, т.е. />|/>
Пусть L – произвольная решётка и />. Наименьшую конгруэнцию,такую, что /> для всех />, обозначим через /> и назовём конгруэнцией,порождённой множеством/>.
ЛЕММА 2.1. Конгруэнция />существует для любого />.
Доказательство. Действительно, пусть Ф = />|/> для всех />/>. Так как пересечение врешётке /> совпадает стеоретико-множественным пересечением, то /> длявсех />. Следовательно, Ф=/>.
В двух случаях мы будемиспользовать специальные обозначения: если /> или/> и /> — идеал, то вместо />мы пишем /> или /> соответственно.Конгруэнция вида /> называетсяглавной; её значение объясняется следующей леммой:
ЛЕММА 2.2. />=/>|/>.
Доказательство. Пусть />, тогда />, отсюда />. С другой сторонырассмотрим />, но тогда />. Поэтому /> и />.
Заметим, что /> - наименьшая конгруэнция,относительно которой />, тогда как /> - наименьшая конгруэнция,такая, что/>содержится в одном смежном классе. Для произвольныхрешёток о конгруэнции />почти ничего неизвестно. Для дистрибутивных решёток важным является следующее описаниеконгруэнции />:
ТЕОРЕМА 2.1. Пусть />-дистрибутивная решётка, /> и />. Тогда /> и />.
Доказательство. Обозначим через Ф бинарноеотношение, определённое следующим образом: /> и/>.
Покажем, что Ф –отношение эквивалентности:
1) Ф – отношениерефлексивности: x·a= x·a; x+b= x+b;
2) Ф – отношениесимметричности:
/>/> x·a = y·a иx+b = y+b /> y·a = x·a иy+b = x+b />/>;
3) Ф – отношениетранзитивности.
Пусть />/> x·a= y·aи x+b= y+b и пусть />/> y·с = z·с и y+d = z+d. Умножим обе части x·a= y·a на элемент с, получим x·a·c= y·a·c. А обе части y·с = z·с умножим на элемент a, получим y·c·a= z·c·a. В силу симметричности x·a·c= y·a·c= z·a·c. Аналогично получаем x+b+d= y+b+d= z+b+d. Таким образом />.
Из всего вышеобозначенного следует, что Ф – отношение эквивалентности.
Покажем, что Фсохраняет операции. Если /> и z/>L, то (x+z) ·a= (x·a) + (z·a) = (y·a) + (z·a) = (y+z) ·a и (x+z)+b= z+(x+b) = z+(y+b); следовательно, />.Аналогично доказывается, что /> и,таким образом, Ф – конгруэнция.
Наконец, пусть /> - произвольнаяконгруэнция, такая, что />, и пусть />.Тогда x·a= y·a, x+b= y+b, />и />. Поэтому вычисляя по модулю />, получим
/>/>/>, т.е. />, и таким образом, />.
СЛЕДСТВИЕ ИЗ ТЕОРЕМЫ2.1. Пусть I – произвольный идеал дистрибутивнойрешётки L. Тогда /> втом и только том случае, когда /> длянекоторого />. В частности, идеал I является смежным классом по модулю />.
Доказательство. Если />, то />и элементы x·y·i, iпринадлежат идеалу I.
Действительно />.
Покажем, что />.
Воспользуемся тем, что /> (*), заметим, что /> и />, поэтому мы можемприбавить к тождеству (*) /> или />, и тождество при этомбудет выполняться.
/> Прибавим />:/>, получим />.
/> Прибавим />:/>, получим />.
Отсюда />. Таким образом,/>.
Обратно согласно лемме 2,/>|/>
Однако /> и поэтому />|/>
Если />, то /> откуда
/>.
Действительно, /> (**).
Рассмотрим правую частьэтого тождества:
Объединим первое и второеслагаемые –
/>.
Объединим первое и третьеслагаемые –
/>,
таким образом /> (***)
Заметим, что />, поэтому прибавим к обеимчастям выражения (***) y:
/>
/>
Но />, отсюда />.
Следовательно, условиеследствия из теоремы 2.1. выполнено для элемента />.Наконец, если /> и />, то />, откуда /> и />, т.е. /> является смежным классом.
ТЕОРЕМА 2.2. Пусть L – булева решётка. Тогда отображение />/> /> является взаимнооднозначным соответствием между конгруэнциями и идеалами решётки L. (Под />/> понимаем класс нуля поконгруэнции />, под /> понимаем решёткуконгруэнций.)
/>Доказательство. В силу следствия из теоремы 2.1. этоотображение на множество идеалов; таким образом мы должны только доказать, чтооно взаимно однозначно, т.е. что смежный класс /> определяетконгруэнцию />. Это утверждение, однако,очевидно. Действительно /> тогда итолько тогда, когда /> (*), последнеесравнение в свою очередь равносильно сравнению />,где с – относительное дополнение элемента /> винтервале />.
Действительно, помножим выражение(*) на с:
/>, но/>,а />, отсюда />.
Таким образом, /> в том и только том случае,когда />.
Примечание. Приведённоедоказательство не полностью использует условие, что L– дистрибутивная решётка с дополнениями. Фактически,мы пользовались только тем, что L имеет нуль и является решёткой с относительными дополнениями. Такаярешётка называется обобщённой булевой решёткой.
ТЕОРЕМА 2.3 (Хасимото [1952]). Пусть L – произвольная решётка. Для того,чтобы существовало взаимно однозначное соответствие между идеалами иконгруэнциями решётки L,при котором идеал, соответствующий конгруэнции />,являлся бы смежным классом по />,необходимо и достаточно, чтобы решётка L была обобщённой булевой.
/>Доказательство. Достаточность следует издоказательства теоремы 2.2. Перейдём к доказательству необходимости.
Идеалом, соответствующимконгруэнции />, должен быть (0]; следовательно,L имеет нуль 0.
/> Если L содержит диамант />, то идеал (a] не может быть смежным классом, потому что из /> следует /> и />. Но />, значит, любой смежныйкласс, содержащий />, содержит и />, и />.
Аналогично, если L содержит пентагон /> и смежный класс содержитидеал />, то /> и />, откуда />. Следовательно, этотсмежный класс должен содержать /> и />.
Итак, решётка L не содержит подрешёток, изоморфных нидиаманту, ни пентагону. Поэтому, по теореме 1.2., она дистрибутивна.
Пусть /> и />. Согласно следствию изтеоремы 2.1., для конгруэнции /> идеал /> так же является смежнымклассом, следовательно, />,откуда />. Опять применяя следствиеиз теоремы 2.1. получим, /> длянекоторого />. Так как />, то /> и />. Следовательно, />ополу орого ледствие 4 получим, цииодержать, соответствующим конгруэнции образом мы должны только доказать, ______________ и />, т.е. элемент /> является относительнымдополнением элемента /> в интервале />.
2.2. Основная теорема
(1) />Пусть /> -обобщённая булева решётка. Определим бинарные операции /> на B, полагая /> иобозначая через /> относительноедополнение элемента /> в интервале />. Тогда /> - булево кольцо, т.е.(ассоциативное) кольцо, удовлетворяющее тождеству /> (аследовательно и тождествам />, />).
(2) Пусть /> - булево кольцо. Определимбинарные операции /> и /> на />, полагая, что /> и />. Тогда /> - обобщённая булеварешётка.
Доказательство.
(1) Покажем, что /> - кольцо.
Напомним определение. Кольцо /> - этонепустое множество /> с заданными нанём двумя бинарными операциями />,которые удовлетворяют следующим аксиомам:
1. Коммутативность сложения:/> выполняется />;
2. Ассоциативность сложения:/> выполняется />;
3. Существование нуля, т.е. />, />;
4. Существованиепротивоположного элемента, т.е. />, />, />;
5. Ассоциативностьумножения: />, />;
6. Закон дистрибутивности.
Проверим, выполняются лиаксиомы кольца:
1. Относительнымдополнением до /> элемента /> будет элемент />, а относительнымдополнением /> элемент />/>.В силу того, что />, а так жеединственности дополнения имеем />.
2. Покажем, что />.
/>Рассмотрим все возможныегруппы вариантов:
1) Пусть />, тогда /> (Далее везде под элементомx будем понимать сумму />).
Аналогично получаем /> в случаях />, />, />, /> и />. Заметим, что когда одиниз элементов равен нулю (например, c),то получаем тривиальные варианты (a+b=a+b).
2) Пусть />, а элемент c не сравним с ними. Возможныследующие варианты:
/>/>/>
Нетрудно заметить, что вовсех этих случаях />, кроме того:
если c=a+b, то (a+b)+c=0=a+(b+c);
если c=0, то получаем тривиальныйвариант.
Вариант,когда c равен наибольшему элементу решётки d, мы уже рассматривали.
Если c=b, то (a+b)+c=(a+b)+b=aи a+(b+c)=a+(b+b)=a.
Если c=a, то (a+b)+c=(a+b)+a=bи a+(b+c)=a+(b+a)=b.
/>Аналогичнодля случаев />, />, />, /> и />.
3) Под элементами нижнегоуровня будем понимать элементы />, />, />, />, />, />, />, />, т.е. те элементы 4-хмерного куба, которые образуют нижний трёхмерный куб.
Под элементами верхнегоуровня будем понимать элементы />, />, />, />, />, />, />, />, т.е. те элементы 4-хмерного куба, которые образуют верхний трёхмерный куб.
Под фразой «элементверхнего уровня, полученный из элемента /> нижнегоуровня сдвигом по соответствующему ребру» будем понимать элемент /> верхнего уровня.
Пусть a, b, c несравнимы. Рассмотрим следующие варианты: /> и />.
/>Пусть />.Заметим, что это возможно только в случаях, когда /> принадлежатнижнему уровню, причём лежат на позициях элементов /> (рис.1). Либо a, b остаются на своих позициях, элемент c сдвигается на верхний уровень посоответствующему ребру (рис. 2). Либо элемент a остаётся на своей позиции, элементы b, c сдвигаются на верхний уровень по соответствующемуребру (рис 3).
/>Нетруднозаметить, что во всех этих случаях />.
Пусть />, здесь так же />.
Таким образом мырассмотрели все основные группы вариантов расположения элементов a, b, cи во всех этих случаях ассоциативность сложениявыполняется.
3. Рассмотрим в решёткеэлемент />, к нему существуетотносительное дополнение /> доэлемента />, т.е. /> и />. Учитывая, что в решётке /> и />, имеем следующее: /> и />. Отсюда />.
4. Рассмотримотносительное дополнение элемента /> до />, это элемент />. Таким образом: /> и />. Учитывая, что в решёткевыполняются тождества /> и /> имеем следующее: /> и />. Отсюда />.
5. Так как в решёткевыполняется ассоциативность />, а также имея />, то />.
6. Докажемдистрибутивность /> или что то жесамое
/> (*).
Докажем, что дополнениялевой и правой частей выражения (*) до верхней грани /> совпадают.
Нетрудно заметить, чтодополнением правой части выражения (*) до элемента /> будетявляться элемент />.
Покажем это:
/>, по определению относительногодополнения элемента />(/>), где за /> приняли элемент />, а элемент /> за />.
/>, по определению относительногодополнения элемента /> (/>), где за /> приняли элемент />, а элемент /> за />.
Покажем, что и для левойчасти (*) элемент /> будет являтьсяотносительным дополнением до верхней грани />:
/>, т.к. />.
/>
Мы показали, чтодополнения элементов /> и /> до верхней грани /> совпадают, следовательно,в силу единственности дополнения />. Азначит и />, т.е. дистрибутивностьдоказана.
Таким образом, для /> все аксиомы кольцавыполняются.
Заметим, что /> выполняется в силу того,что />, а в решётке />.
Также выполняется />, потому что />.
Таким образом, /> - булево кольцо.
Доказательство (2). Частичнуюупорядоченность /> имеем исходя изтого, что исходное булево кольцо /> -частично упорядоченное множество. Кроме того /> -решётка, т.к. /> существуют sup(x,y) и inf(x,y), заданные соответствующими правилами: /> и />.
Покажем, что решёткадистрибутивна, т.е. что выполняется тождество /> (*)
Рассмотрим левую частьвыражения (*):
/>.
Рассмотрим правую частьвыражения (*):
/>,
т.о. тождество /> верно, т.е. решётка /> является дистрибутивной.
Покажем, что у каждогоэлемента /> в дистрибутивной решётке /> есть относительноедополнение. Для этого рассмотрим произвольные элементы />, но они так же должныявляться элементами решётки />,следовательно, в ней должны лежать и />,которым в кольце соответствуют />.
Рассмотрим элемент булевакольца /> (в решётке лежитсоответствующий ему элемент), заметим, что
/>
и /> .
Поэтому элемент /> будет являться вдистрибутивной решётке /> относительнымдополнением /> до верхней грани />.
Таким образом, /> будет являтьсядистрибутивной решёткой с относительными дополнениями (обобщённой булевой).
Библиографическийсписок
1. Гретцер, Г. Общая теориярешёток [Текст] / Г. Гретцер. – М.: Мир, 1982.
2. Биркгоф, Г. Теориярешёток [Текст] / Г. Биркгоф. – М.: Наука, 1984.
3. Скорняков, Л.А. Элементыалгебры [Текст] / Л.А. Скорняков. – М.: Наука, 1989.