Полукольцо

Полукольцо — общеалгебраическая структура, похожая на кольцо, но без требования существования противоположного по сложению элемента.

Определения

Множество $S$, с заданными на нем бинарными операциями $+$ и $\cdot$, называется полукольцом, если для любых элементов $a,b,c$ выполняются следующие условия:

1. $\langle S,+\rangle$ — коммутативный моноид. То есть имеют место свойства:
   • Коммутативности: $a+b=b+a$
   • Ассоциативности: $(a+b)+c=a+(b+c)$
   • Существования нейтрального элемента (нуля): $a+0=0+a=a$
2. $\langle S,\cdot \rangle$ — полугруппа. То есть, дополнительно, имеет место свойство:
   • Ассоциативности: $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
3. Умножение дистрибутивно относительно сложения:
   • Левая дистрибутивность: $a\cdot (b+c)=a\cdot b+a\cdot c$
   • Правая дистрибутивность: $(a+b)\cdot c=a\cdot c+b\cdot c$
4. Мультипликативное свойство нуля:
   • $a\cdot 0=0\cdot a=0$

Для кольца последнее соотношение не требуется, поскольку оно следует из других, для полукольца оно необходимо. Отличие полукольца от кольца состоит только в том, что по сложению полукольцо образует не коммутативную группу, а только коммутативный моноид.

Полукольцо называется коммутативным, если операция умножения в нём коммутативна: $a\cdot b=b\cdot a\;\forall a,b\in S$.

Полукольцо называется полукольцом с единицей, если в нём существует нейтральный элемент по умножению (называемый единицей): $a\cdot 1=1\cdot a=a\;\forall a\in S$.

Полукольцо называется мультипликативно (или аддитивно) сократимым, если $\;\forall a,b,c\in S$ из равенства $a\cdot c=b\cdot c$ (или, соответственно, $a+c=b+c$) следует, что $a=b$.

Полукольцо называется идемпотентным, если для любого $a\in S$ выполняется равенство $a+a=a.$

Примеры полуколец

• Полукольцо $\langle \mathbb {N} _{0},+,\cdot \rangle$ натуральных чисел с нулем.
• Тривиальное полукольцо: $\langle \lbrace 0\rbrace ,+,\cdot \rangle$
• Двухэлементные полукольца: $\langle \mathbb {Z} _{2},+,\cdot \rangle$, $\langle \mathbb {B} ,\oplus ,\vee \rangle$, где $\vee$ обозначает дизъюнкцию, а $\oplus$ — логическую операцию «исключающее или» на множестве $\mathbb {B} =\lbrace 0,1\rbrace$
• Квадратные $n\times n$ матрицы с элементами из полукольца натуральных чисел с нулем $\mathbb {N} _{0}$ и операциями матричного сложения и умножения. Также полукольцо образуют квадратные матрицы с элементами из любого полукольца.
• Если $A$ — коммутативный моноид, то множество $\operatorname {End} (A)$ эндоморфизмов $A$ образует полукольцо, где сложение определено поточечно, а умножение — как композиция функций.
• $\mathbb {N} [x]$ — многочлены с натуральными коэффициентами — образуют коммутативное полукольцо; это свободное коммутативное полукольцо с единственным генератором $\{x\}$.
• Вероятностное полукольцо — неотрицательные действительные числа с обычными операциями сложения и умножения.
• $(\max ,+)$ и $(\min ,+)$ — полукольца вещественных чисел, в которых сложение определено как взятие максимума (соответственно минимума), а умножение — как обычное сложение вещественных чисел. Для первого случая подмножество должно быть четко ограничено снизу, для второго - сверху.

Приложения

Идемпотентные кольца, особенно $(\max ,+)$ и $(\min ,+)$, часто используются в методах оценки персонала. Вещественные числа здесь обозначают «время прибытия» или «затраты», операция $\max$ обозначает необходимость ожидать выполнения всех предпосылок для совершения действия (соответственно, $\min$ обозначает способность выбрать наименее затратный вариант) и + обозначает сложение времени (затрат) при прохождении одного и того же пути.

Алгоритм Флойда — Уоршелла поиска кратчайших путей может быть переформулирован для вычислений над $(\min ,+)$-алгеброй. Также и алгоритм Витерби поиска наиболее вероятной последовательности состояний в скрытой марковской модели может быть переформулирован для вычислений над $(\max ,\times )$-алгеброй вероятностей. Эти алгоритмы динамического программирования используют дистрибутивность соответствующих полуколец для расчета свойств при использовании большого (возможно, экспоненциально большого) числа переменных более эффективно, чем перечисляя каждую из них.

Полукольцо множеств

Полукольцо множеств — система множеств $S$, для которой выполнены следующие условия:

• $\varnothing \in S$;
• $\forall A,B\in S\quad A\cap B\in S$;
• $\forall A\in S,A_{1}\in S\quad A_{1}\subset A\Rightarrow \exists A_{2},\dots ,A_{n}\subset A:A_{1}\sqcup \dots \sqcup A_{n}=A$.

Таким образом, полукольцо множеств содержит в себе пустое множество, замкнуто относительно пересечения и любая разность множеств из полукольца множеств представима в виде конечного объединения дизъюнктных (попарно не пересекающихся) множеств, принадлежащих этому полукольцу множеств. Такие полукольца часто используются в теории меры.

Полукольцом множеств с единицей называют полукольцо множеств с таким элементом $E$, что его пересечение с любым элементом $A$ полукольца множеств равно $A$. Применяя метод математической индукции, можно расширить последний пункт определения: если множества $A_{1},\dots ,A_{n}$ являются элементами полукольца множеств и подмножествами элемента $A$, то их можно дополнить непересекающимися элементами $A_{n+1},\dots ,A_{m}$ до $A$. Любое кольцо множеств является полукольцом множеств. Прямое произведение полуколец множеств также является полукольцом множеств.

Литература

• François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (online version), Wiley, 1992, ISBN 0-471-93609-X
• Golan, Jonathan S., Semirings and their applications. Updated and expanded version of The theory of semirings, with applications to mathematics and theoretical computer science (Longman Sci. Tech., Harlow, 1992, MR: 1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR: 1746739
• Berstel, Jean; Perrin, Dominique. Theory of codes (неопр.). — Academic Press, 1985. — Т. 117. — (Pure and applied mathematics). — ISBN 978-0-12-093420-1.
• Lothaire, M. Applied combinatorics on words (неопр.). — Cambridge: Cambridge University Press, 2005. — Т. 105. — (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-84802-4.