Дипломная работа: Обобщённо булевы решетки

Федеральное агентство по образованию

Государственное образовательное учреждение
высшего профессионального образования
Вятский государственный гуманитарный университет

Математический факультет

Кафедра алгебры и геометрии

Выпускная квалификационная работа

Обобщенно булевы решетки

Выполнил:

студент 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.). Кроме того реализована основная цель данной дипломной работы: установлена связь между булевыми кольцами и обобщённо булевыми решётками (Основная теорема).

1.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 существует, то она единственна.

Примеры решёток:

Примечание. Любая цепь является решёткой, т.к.  совпадает с меньшим, а  с большим из элементов .

Наибольший элемент, то есть элемент, больший или равный каждого элемента упорядоченного множества, обозначают 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].

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 является идеалом.

2.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. Таким образом .

Из всего выше обозначенного следует, что Ф – отношение эквивалентности.

Покажем, что Ф сохраняет операции. Если  и zL, то (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.