Частично упорядоченные множества и решётки
Определение 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].
Назад Содержание Вперёд