Решетки

Решеткой называется частично упорядоченное множество \(L\), в котором для любых \(a,b \in L\) существуют \(\sup \{a,b,\}\) и \(\inf \{a,b,\}\).

Можно было бы сказать: для любого конечного подмножества.

Теорема. Если \(a \leq b\), то \(\sup \{a,b\} = b\) и \(\inf \{a,b\} = a\).

Следовательно, любая цепь будет решеткой.

На решетке рассматриваются алгебраические операции:

\(a \lor b = \sup \{a,b\}\) и \(a \land b = \inf \{a,b\}\)

Часто их обозначают через \(+\) и \(\cdot\). Называют их объединением и пересечением.

Теорема. На решетке \((L, \leq)\) выполняются свойства:

1. \(a \lor a = a\)
2. \(a \lor b = b \lor a\)
3. \((a \lor b) \lor c = a \lor (b \lor c)\)
4. \(a \land (a \lor b) = a\) (закон поглощения)

и все двойственные им.

Упражнение: показать, что идемпотентность следует из закона поглощения.

Решетку можно определить как алгебру \((L, \lor, \land)\), на которой выполняются указанные свойства.

Такие определения будут эквивалентны.