Полукольцо (Hklrtkl,ek)

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

Определения

Множество $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}$ являются элементами $S$ и подмножествами элемента $A$, то их можно дополнить непересекающимися элементами $A_{n+1},\dots ,A_{m}$ до $A$;

Доказательство

Проведем доказательство индукцией по $n$. При $n=1$ утверждение содержится в определении полукольца. Пусть для $n-1$ множества утверждение доказано. Рассмотрим $n$ множеств. Тогда для некоторых $B_{j}\in S$ имеет место разложение $A=\textstyle {\bigsqcup _{k}^{n-1}A_{k}\sqcup \bigsqcup _{j}B_{j}}$, причём $\textstyle {A_{n}\subset \bigsqcup _{j}B_{j}.}$ При каждом $j$ в силу определения полукольца найдётся такие $\{C_{i,j}\}_{i}$ из $S$, что $\textstyle {B_{j}=(A_{n}\cap B_{j})\sqcup \bigsqcup _{i}C_{i,j}.}$ Поскольку $\textstyle {A_{n}=\bigsqcup _{j}(A_{n}\cap B_{j})}$, ⁣то

$A=\bigsqcup _{k}^{n}A_{k}\sqcup \bigsqcup _{j}\bigsqcup _{i}C_{i,j}.$

• если $A_{1},A_{2},\ldots ,A_{n}\in S$, тогда найдутся такие попарно непересекающиеся $B_{1},B_{2},\ldots ,B_{m}\in S$, что каждое из $A_{k}$ представимо в виде объединения некоторых из $B_{j}$;

Доказательство

Проведем индукцию по $n$. При $n=1$ доказывать нечего. Пусть для $n-1$ множества утверждение уже доказано. Рассмотрим $n$ множеств, и пусть $B_{1},\ldots ,B_{m}\in S$ соответствуют первым $n-1$ множеству. Для каждого $j=1,\ldots ,m$ проведем следующее действие: если $A_{n}\cap B_{j}$ непусто, то обозначим его за $C_{1,j}$ и построим, опираясь на определение полукольца, разложение $B_{j}=\textstyle {\bigsqcup _{i}C_{i,j}}$; в противном случае положим $C_{i,j}=B_{j}$. Теперь каждое из $n-1$ первых множеств $A_{k}$ представимо в виде дизъюнктного объединения некоторых $C_{i,j}$ и

$A_{n}\supseteq \bigsqcup _{j}^{n-1}C_{1,j}$,

причем остальные $C_{i,j}$ не пересекаются с $A_{n}$. Если здесь выполнено равенство, то набор ${C_{i,j}}$ годится и для $n$ множеств, иначе применим предыдущее свойство и добавим к набору множества $\{D_{k}\}.$

• для любого элемента $A$ полукольца система множеств $S\ |_{A}=\{B\in S\ |\ B\subseteq A\}$ — полукольцо;

Доказательство

Ясно, что если два множества вложены в $A$, то их пересечение вложено в $A$. Если же $B_{1}\subset B\subseteq A$, где $B,B_{1}\in S$, то множества, дополняющие $B_{1}$ до $B$, тоже будут вложены в $A$.

• прямое произведение полуколец $S_{1}\times S_{2}\times \dots \times S_{n}$ является полукольцом.

Доказательство

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

Декартово произведение пустых множеств есть пустое множество. Пересечение декартовых произведений равно декартову произведению пересечений.

Пусть $A_{k}\in S_{k}$ и $A_{k,1}\in S_{k}$, причём $A_{1,1}\times A_{2,1}\times \dots \times A_{n,1}\subseteq A_{1}\times A_{2}\times \dots \times A_{n}$, где множество слева непусто. Тогда при каждом $k$ $A_{k,1}\subseteq A_{k}$, и так как $S_{k}$ — полукольца, то найдутся такие $A_{k,j}$, что при каждом $k$ выполнено равенство $A_{k}=\textstyle {\bigsqcup _{j}}\ A_{k,j}.$ Нетрудно видеть, что

$A_{1}\times A_{2}\times \dots \times A_{n}=\bigsqcup _{j_{1}}\cdots \bigsqcup _{j_{n}}^{}A_{1,j_{1}}\times A_{2,j_{2}}\times \dots \times A_{n,j_{n}}.$

Все члены в правой части равенства принадлежат прямому произведению полуколец, и один из них есть наше заданное множество $A_{1,1}\times A_{2,1}\times \dots \times A_{n,1}.$ Таким образом, все свойства полукольца выполнены, и свойство доказано.

Литература

• 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.