Полурешётка

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

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

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

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

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

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

• $x\vee <!--\; \vee \; -->(x\wedge <!--\; \wedge \; -->y)=x$$x\vee (x\wedge y)=x$ ,
• $x\wedge <!--\; \wedge \; -->(x\vee <!--\; \vee \; -->y)=x$$x\wedge (x\vee y)=x$ ,

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

Частичный порядокПравить

Частичный порядок в алгебраически определённой полурешётке $(V,\wedge <!--\; \wedge \; -->)$$(V,\wedge )$  может быть введён следующим образом: $x⊑<!--\; ⊑\; -->y$$x\sqsubseteq y$  тогда и только тогда, когда $x\wedge <!--\; \wedge \; -->y=x$$x\wedge y=x$ . Поскольку бинарная операция в полурешётке идемпотентна, коммутативна и ассоциативна, то определённый таким образом порядок является рефлексивным ($x⊑<!--\; ⊑\; -->x$$x\sqsubseteq x$ ), антисимметричным ($(x⊑<!--\; ⊑\; -->y)\mathrm{\&<!--\; \&\; -->}(y⊑<!--\; ⊑\; -->x)\Rightarrow <!--\; \Rightarrow \; -->(x=y)$$(x\sqsubseteq y)\And (y\sqsubseteq x)\Rightarrow (x=y)$  и транзитивным ($(x⊑<!--\; ⊑\; -->y)\mathrm{\&<!--\; \&\; -->}(y⊑<!--\; ⊑\; -->z)\Rightarrow <!--\; \Rightarrow \; -->(x⊑<!--\; ⊑\; -->z)$$(x\sqsubseteq y)\And (y\sqsubseteq z)\Rightarrow (x\sqsubseteq z)$ ).

ЛитератураПравить

• Салий В. Н., Скорняков Л. А. . Глава V. Решётки // Общая алгебра / Под общ. ред. Л. А. Скорнякова. — М.: Наука, 1991. — Т. 2. — С. 192—294. — 480 с. — (Справочная математическая библиотека). — 25 000 экз. — ISBN 5-9221-0400-4.
• Davey, B. A.; Priestley, H. A. Introduction to Lattices and Order (англ.). — second. — Cambridge University Press, 2002. — ISBN 0-521-78451-4.
• Vickers, Steven^[en]. Topology via Logic (англ.). — Cambridge University Press, 1989. — ISBN 0-521-36062-5.

СсылкиПравить

• Jipsen’s algebra structures page: Semilattices.