Полукольцо

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

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

Определение и свойства полуколец[править | править исходный текст]

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

  1. \langle S, + \rangle — коммутативный моноид. То есть имеют место свойства:
  2. \langle S, \cdot \rangle — полугруппа. То есть имеет место свойство:
  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.

Примеры полуколец[править | править исходный текст]

  1. Полукольцо \langle \mathbb{N}_0, +, \cdot \rangle натуральных чисел с нулем.
  2. Тривиальное полукольцо: \langle \lbrace 0 \rbrace, +, \cdot \rangle
  3. Двухэлементные полукольца: \langle \mathbb Z_2, +, \cdot \rangle, \langle \mathbb B, \oplus, \vee \rangle, где \vee обозначает дизъюнкцию, а \oplus — логическую операцию «исключающее или» над множеством \mathbb B = \lbrace 0, 1 \rbrace
  4. Квадратные n×n матрицы с элементами из полукольца натуральных чисел с нулем \mathbb{N}_0 и операциями матричного сложения и умножения. Также полукольцо образуют квадратные матрицы с элементами из любого полукольца.
  5. Если A — коммутативный моноид, то множество End(A) эндоморфизмов A образует полукольцо, где сложение определено поточечно, а умножение — как композиция функций.
  6. N[x], многочлены с натуральными коэффициентами образуют коммутативное полукольцо. На самом деле, это свободное коммутативное полукольцо с единственным генератором {x}.
  7. Вероятностное полукольцо — неотрицательные действительные числа с обычными операциями сложения и умножения.[2]
  8. (max, +) и (min, +) — полукольца вещественных чисел, в которых сложение определено как взятие максимума (соотв. минимума), а умножение — как обычное сложение вещественных чисел.

Приложения[править | править исходный текст]

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

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

Полукольцо множеств[править | править исходный текст]

Полукольцо множеств[4] — система множеств 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. Любое кольцо множеств является полукольцом множеств. Прямое произведение полуколец множеств также является полукольцом множеств.

Примечания[править | править исходный текст]

  1. Berstel & Perrin (1985)
  2. 1 2 Lothaire (2005) p.211
  3. Sakarovitch (2009) pp.27-28
  4. Noel Vaillant, Caratheodory’s Extension, on probability.net.

См. также[править | править исходный текст]

Литература[править | править исходный текст]