Решётки

2. Решётки

Определение: Верхней гранью подмножества  в упорядоченном множестве  называется элемент  из  , больший или равный всех  из .

Определение: Точная верхняя грань подмножества  упорядоченного множества  – это такая его верхняя грань, которая меньше любой другой его верхней грани. Обозначается символом  и читается «супремум X».

Согласно аксиоме антисимметричности упорядоченного множества, если точная верхняя грань существует, то она единственна.

Понятия нижней грани и точной нижней грани (которая обозначается  и читается «инфинум») определяются двойственно. Также, согласно аксиоме антисимметричности упорядоченного множества, если точная нижняя грань существует, то она единственна.

Определение: Решёткой  называется упорядоченное множество , в котором любые два элемента  и  имеют точную нижнюю грань, обозначаемую , и точную верхнюю грань, обозначаемую .

Примеры решёток:

1. Любая цепь является решёткой, т.к.  совпадает с меньшим, а  с большим из элементов .

2.

Наибольший элемент, то есть элемент, больший или равный каждого элемента упорядоченного множества, обозначают , а наименьший элемент, то есть меньший или равный каждого элемента упорядоченного множества, обозначают .

На решётке можно рассматривать две бинарные операции:

 - сложение и

 - произведение

Эти операции обладают следующими свойствами:

1. ,  идемпотентность

2. , коммутативность

3. ,

 ассоциативность

4. ,

 законы поглощения

Теорема. Пусть  - множество с двумя бинарными операциями , обладающими свойствами (1) – (4). Тогда отношение  (или ) является порядком на , а возникающее упорядоченное множество оказывается решёткой, причём:

Доказательство.

Рефлексивность отношения  вытекает из свойства (1). Заметим, что оно является следствием свойства (4):

Если  и , то есть  и , то в силу свойства (2), получим . Это означает, что отношение  антисимметрично.

Если  и , то применяя свойство (3), получим: , что доказывает транзитивность отношения .

Применяя свойства (3), (1), (2), получим:

,

.

Следовательно,  и

Если  и , то используя свойства (1) – (3), имеем:

, т.е.

По определению точней верхней грани убедимся, что

Из свойств (2), (4) вытекает, что  и

Если  и , то по свойствам (3), (4) получим:

Отсюда по свойствам (2) и (4) следует, что

, т.е.

Таким образом, . ■

Пусть решётка, тогда её наибольший элемент  характеризуется одним из свойств:

1.

2..

Аналогично характеризуется наименьший элемент :

1.

2..