. Примеры решёток:
Примечание. Любая цепь является решёткой, т.к.
совпадает с меньшим, а
с большим из элементов
.
Наибольший элемент, то есть элемент, больший или равный каждого элемента упорядоченного множества, обозначают 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.
.
Решётка L
называется дистрибутивной
, если для любых
выполняется:
D1.
.
D2.
.
В любой решётке тождества D1 и D2 равносильны. Доказательство этого факта содержится в книге [2], стр. 24.
Примеры дистрибутивных решёток:
1. Множество целых положительных чисел,
означает, что
делит
. Это решётка с операциями НОД и НОК.
2. Любая цепь является дистрибутивной решёткой.
ТЕОРЕМА 1.2.
Решётка L
с 0 и 1 является дистрибутивной тогда и только тогда, когда она не содержит подрешёток вида Доказательство этой теоремы можно найти в книге [1].
Всюду далее под словом «решётка» понимается произвольная дистрибутивная решётка с 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
является обобщённо булевой.
Подрешётка I
решётки L
называется идеалом
,
если для любых элементов
и
элемент
лежит в I
. Идеал I
называется собственным,
если
. Собственный идеал решётки L называется простым
, если из того, что
и
следует
или .
Так как непустое пересечение любого числа идеалов снова будет идеалом, то мы можем определить идеал, порождённый множеством H
в решётке L
, предполагая, что H
не совпадает с пустым множеством. Идеал, порождённый множеством H
будет обозначаться через (
H
]
. Если
, то вместо
будем писать
и называть
главным идеалом
.
ТЕОРЕМА 1.5.
Пусть L
– решётка, а H
и I
– непустые подмножества в L
, тогда I
является идеалом тогда и только тогда, когда если
, то
, и если
, то .
Доказательство.
Пусть I
– идеал, тогда
влечёт за собой
, так как I
– подрешётка. Если
, то
и условия теоремы проверены.
Обратно, пусть I
удовлетворяет этим условиям и
. Тогда
и так как
, то
, следовательно, I
– подрешётка. Наконец, если
и
, то
, значит,
и I
является идеалом.
Отношение эквивалентности
(т.е. рефлексивное, симметричное и транзитивное бинарное отношение)
на решётке 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 получим, цииодержать , соответствующим конгруэнции образом мы должны только доказать, ______________ и
, т.е. элемент
является относительным дополнением элемента
в интервале .
(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.