Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
Обобщенно булевы решетки
Выполнил:
студент 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. Транзитивность. Если и , то .
Если и , то говорят, что меньше или больше , и пишут или .
Примеры упорядоченных множеств:
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
является идеалом.
Глава 2
2.1. Конгруэнции
Отношение эквивалентности
(т.е. рефлексивное, симметричное и транзитивное бинарное отношение) на решётке L
называется конгруэнцией на L
, если и совместно влекут за собой и (свойство стабильности)
. Простейшими примерами являются ω, ι, определённые так:
(ω)
; (ι)
для всех .
Для обозначим через смежный класс
, содержащий элемент , т.е. |
Пусть L
– произвольная решётка и .
Наименьшую конгруэнцию
, такую, что для всех , обозначим через и назовём конгруэнцией, порождённой множеством
.
ЛЕММА 2.1.
Конгруэнция
существует для любого .
Доказательство.
Действительно, пусть Ф
= | для всех . Так как пересечение в решётке совпадает с теоретико-множественным пересечением, то для всех . Следовательно, Ф
=.
В двух случаях мы будем использовать специальные обозначения: если или и - идеал, то вместо мы пишем или соответственно. Конгруэнция вида называется главной; её значение объясняется следующей леммой:
ЛЕМ
=|.
Доказательство.
Пусть , тогда , отсюда . С другой стороны рассмотрим , но тогда . Поэтому и .
Заметим, что - наименьшая конгруэнция, относительно которой , тогда как - наименьшая конгруэнция, такая, чтосодержится в одном смежном классе. Для произвольных решёток о конгруэнции почти ничего не известно. Для дистрибутивных решёток важным является следующее описание конгруэнции :
ТЕОРЕМА 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.