WikiSort.ru - Не сортированное

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

Определения

Формально определяется как множество ${\displaystyle S}$ , снабжённое бинарными операциями ${\displaystyle +}$ и ${\displaystyle \cdot }$ , в котором для любых элементов ${\displaystyle a,b,c}$ выполняются следующие аксиомы:^[1][2][3]

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

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

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

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

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

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

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

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

Приложения

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

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

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

Полукольцо множеств^[4] — система множеств ${\displaystyle S}$ , для которой выполнены следующие условия:

• ${\displaystyle \varnothing \in S}$ ;
• ${\displaystyle \forall A,B\in S\quad A\cap B\in S}$ ;
• ${\displaystyle \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}$ .

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

Полукольцом множеств с единицей называют полукольцо множеств с таким элементом ${\displaystyle E}$ , что его пересечение с любым элементом ${\displaystyle A}$ полукольца множеств равно ${\displaystyle A}$ . Применяя метод математической индукции, можно расширить последний пункт определения: если множества ${\displaystyle A_{1},\dots ,A_{n}}$ являются элементами полукольца множеств и подмножествами элемента ${\displaystyle A}$ , то их можно дополнить непересекающимися элементами ${\displaystyle A_{n+1},\dots ,A_{m}}$ до ${\displaystyle 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. Theory of codes / Jean Berstel, Perrin. — Academic Press, 1985. — Vol. 117. — ISBN 978-0-12-093420-1.
• Lothaire, M. Applied combinatorics on words. — Cambridge : Cambridge University Press, 2005. — Vol. 105. — ISBN 0-521-84802-4.