Обобщённо булевы решетки
3
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
Обобщенно булевы решетки
Выполнил:
студент 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. Таким образом .Из всего выше обозначенного следует, что
Ф - отношение эквивалентности.Покажем, что
Ф сохраняет операции. Если и
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.