Полурешётка

Полурешётка (англ. semilattice, до 1960-х годов также использовался термин полуструктура) в общей алгебре — полугруппа, бинарная операция в которой коммутативна и идемпотентна.

С точки зрения теоретико-множественного подхода, полурёшетка определяется как частично упорядоченное множество, для каждой пары элементов которого определена точная верхняя грань (верхняя полурешётка) или точная нижняя грань (нижняя полурешётка). Множество, являющееся одновременно верхней и нижней полурешёткой является решёткой.

Алгебраические определения

Полурешётка аксиоматизируется как алгебра, снабжённая бинарной операцией $\langle V, \star \rangle$ следующими тождествами:

1. $x \star x = x$ (идемпотентность);
2. $(x \star y) \star z = x \star (y \star z)$ (ассоциативность);
3. $x \star y = y \star x$ (коммутативность).

Если алгебры $\langle V, \vee \rangle$ и $\langle V, \wedge \rangle$ — полурешётки и их операции связаны соотношениями (называемым законами поглощения):

• $x \vee (x \wedge y) = x$,
• $x \wedge (x \vee y) = x$,

то алгебра $\langle V, \vee, \wedge \rangle$ является решёткой. В таком контексте $\langle V, \vee \rangle$ называют верхней полурешёткой, а $\langle V, \wedge \rangle$ — нижней. В верхних полурешётках вводится верхний элемент $\top \in V$ такой, что $\top \vee x = x$ для всех элементов $x \in V$, в нижних — нижний элемент $\bot \in V$ такой, что $\bot \wedge x = \bot$, полурешётки, в которых существуют такие элементы, называют ограниченными.

Частичный порядок в полурешётке

Для $x$ и $y$ из $V$ в полурешётке можно определить частичный порядок таким образом: $x \le y$ тогда и только тогда, когда $x \wedge y = x$. Поскольку бинарная операция в полурешётке идемпотентна, коммутативна и ассоциативна, то определённый таким образом порядок является рефлексивным ($x \le x$), антисимметричным ($(x \le y) \And (y \le x) \Rightarrow (x=y)$ и транзитивным ($(x \le y) \And (y \le z) \Rightarrow (x \le z)$).

Литература

• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — Издательский дом "Вильямс", 2008. — ISBN 0-321-48681-1
• Introduction to Lattices and Order. — second. — Cambridge University Press, 2002. — ISBN 0-521-78451-4
• Vickers Steven Topology via Logic. — Cambridge University Press, 1989. — ISBN 0-521-36062-5
• Аратмонов В. А.; Салий В. Н.; Скорняков Л. А.; Шеврин Л. Н.; Шульгейфер Е. Г. Решётки // Общая алгебра / под общей редакцией Скорнякова Л. А.. — М.: Наука, 1991. — Т. 2. — С. 192—294. — 480 с. — (Справочная математическая библиотека). — 25 500 экз. — ISBN 5-02-014427-4

Ссылки

• Jipsen’s algebra structures page: Semilattices.