Полурешётка

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Полурешётка (англ. 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 = \top для всех элементов 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))[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.
  • 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.

Ссылки[править | править вики-текст]