Обобщённо булевы решетки
Федеральное агентство по образованию
Государственное
образовательное учреждение
высшего
профессионального образования
Вятский
государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
Обобщенно
булевы решетки
Выполнил:
студент 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.1. Упорядоченные множества
Упорядоченным множеством
P
называется непустое множество, на
котором определено бинарное отношение
,
удовлетворяющее для всех
следующим условиям:
1. Рефлексивность:
.
2. Антисимметричность. Если
и
,
то
.
3. Транзитивность. Если
и
,
то
.
Если
и
,
то говорят, что
меньше
или
больше
,
и пишут
или
.
Примеры упорядоченных множеств:
Множество целых положительных
чисел, а
означает, что
делит
.
Множество всех действительных
функций
на отрезке
и
означает, что
для
.
Цепью называется
упорядоченное множество, на котором
для любых
имеет место
или
.
Используя отношение порядка,
можно получить графическое представление
любого конечного упорядоченного
множества 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. Решётка
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
является идеалом.
Глава 2
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.
Таким образом
.
Из всего выше обозначенного следует, что Ф – отношение эквивалентности.
Покажем, что Ф
сохраняет операции. Если
и 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. Основная теорема
П
усть
- обобщённая булева решётка. Определим
бинарные операции
на B,
полагая
и обозначая через
относительное дополнение элемента
в интервале
.
Тогда
- булево кольцо, т.е. (ассоциативное)
кольцо, удовлетворяющее тождеству
(а следовательно и тождествам
,
).
Пусть
- булево кольцо. Определим бинарные
операции
и
на
,
полагая, что
и
.
Тогда
- обобщённая булева решётка.
Доказательство.
Покажем, что
- кольцо.
Напомним определение. Кольцо
- это непустое множество
с заданными на нём двумя бинарными
операциями
,
которые удовлетворяют следующим
аксиомам:
Коммутативность
сложения:
выполняется
;
Ассоциативность
сложения:
выполняется
;
Существование нуля,
т.е.
,
;
Существование
противоположного элемента, т.е.
,
,
;
Ассоциативность
умножения:
,
;
Закон дистрибутивности.
Проверим, выполняются ли аксиомы кольца:
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),
заданные соответствующими правилами:
и
.
Покажем, что решётка дистрибутивна,
т.е. что выполняется тождество
(*)
Рассмотрим левую часть выражения (*):
.
Рассмотрим правую часть выражения (*):
,
т.о. тождество
верно, т.е. решётка
является дистрибутивной.
Покажем, что у каждого элемента
в дистрибутивной решётке
есть относительное дополнение. Для
этого рассмотрим произвольные элементы
,
но они так же должны являться элементами
решётки
,
следовательно, в ней должны лежать и
,
которым в кольце соответствуют
.
Рассмотрим элемент булева кольца
(в решётке лежит соответствующий ему
элемент), заметим, что
и
.
Поэтому элемент
будет являться в дистрибутивной решётке
относительным дополнением
до верхней грани
.
Таким образом,
будет являться дистрибутивной решёткой
с относительными дополнениями (обобщённой
булевой).
Библиографический список
Гретцер, Г. Общая теория решёток [Текст] / Г. Гретцер. – М.: Мир, 1982.
Биркгоф, Г. Теория решёток [Текст] / Г. Биркгоф. – М.: Наука, 1984.
Скорняков, Л.А. Элементы алгебры [Текст] / Л.А. Скорняков. – М.: Наука, 1989.