Частично упорядоченные множества и решётки
Определение 2.1 Бинарное отношение
на некотором множестве
называется отношением (нестрогого) частичного порядка, если для
:
(рефлексивность);
и
, то
(антисимметричность);
и
, то
(транзитивность).
Множество S с определённым на нем отношением частичного порядка
(частично упорядоченное множество) обозначается
. Если
, то говорят, что элемент
меньше, чем
или равен ему. Если для
не существует
, такого что
, то
называют максимальным элементом
(относительно
).
Если
и
, то пишут
и говорят, что
строго меньше, чем
.
Определение 2.2 Пусть
— частично упорядоченное множество. Элемент
называется соседом снизу элемента
, если
и
. В этом случае
называется соседом сверху
(обозначается
). Направленный граф отношения
называется графом покрытия.
Конечное частично упорядоченное множество
может быть графически представлено с помощью диаграммы Хассе (или просто диаграммы [1]). Элементы
изображаются в виде точек. Если
, то
размещается "над"
(вертикальная координата
больше вертикальной координаты
), и две точки соединяются линией.
Определение 2.3 Верхней гранью подмножества
в упорядоченном множестве
называется элемент
, такой что
для всех
. Точная верхняя грань множества
(называемая также наименьшей верхней гранью или супремумом) множества
(обозначается sup
) есть верхняя грань
такая, что
для любой верхней грани
подмножества
. Двойственным образом (с заменой
на
) определяется понятие точной (наибольшей) нижней грани или инфимума inf
.
Определение 2.4 Бинарная операция
называется полурешёточной, если для некоторого
и любых
:
(идемпотентность);
(коммутативность);
(ассоциативность);
.
Для
и
мы пишем
вместо
. Если
, то
.
Определение 2.5 Множество
с определённой на нем полурешёточной операцией
называется полурешёткой
.
Полурешёточная операция
задает два частичных порядка
и
на
(
):
Тогда множество с определённой на нем полурешёточной операцией
будем называть нижней полурешёткой (относительно частичного порядка
) и верхней полурешёткой (относительно частичного порядка
).
Определение 2.6 Пусть
— полурешётка. Множество
называется системой замыканий [33] или семейством Мура [1] (относительно
), если
.
Очевидно, что система замыканий (относительно
)
с определённой на ней операцией,
и
, образует полурешётку.
Определение 2.7 Упорядоченное множество
с определёнными на нем полурешёточными операциями
и
называется решёткой, если
и
являются, соответственно, нижней и верхней полурешётками (относительно
).
Операции
и
называют операциями взятия точной нижней и верхней грани в решётке, или инфимума и супремума соответственно.
Определение 2.8 Подрешёткой решётки
называется подмножество
такое, что если
,
, то
и
.
Полурешёточные операции
и
удовлетворяют в решётках следующему условию:
(поглощение).
Из любой конечной полурешётки можно получить решётку добавлением одного (максимального или минимального в зависимости от типа полурешетки) элемента.
Решётка называется полной, если у каждого подмножества его элементов есть супремум и инфимум (всякая конечная решётка является полной).
Определение 2.9 Интервал
состоит из всех элементов
. Порядковым фильтром (идеалом) решётки
называется подмножество
такое, что если
,
и
, то
(соответственно,
,
и
, то
).
Элемент
решётки называется инфимум-неразложимым или
-неразложимым (или неразложимым в пересечение), если для любых
и
, не выполняется
. Элемент
решётки называется супремум-неразложимым или
-неразложимым (или неразложимым в объединение), если для любых
и
не выполняется
.
Подмножество
полной решётки
называется инфимум-плотным, если
, и супремум-плотным, если
).
Определение 2.10 Пусть
и
— частично упорядоченные множества. Пара отображений
и
называется соответствием Галуа между частично упорядоченными множествами
и
, если для любых
и
:
;
;
и
.
Приведённые условия эквивалентны одному:
[1,33,28].
Назад Содержание Вперёд
