Полурешётка

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

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

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

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

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

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

• ${\displaystyle x\vee (x\wedge y)=x}$,
• ${\displaystyle x\wedge (x\vee y)=x}$,

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

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

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

Примечания

Литература

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

Ссылки

• Jipsen’s algebra structures page: Semilattices.