Полукольцо

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

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

Определения[править | править код]

Формально определяется как множество , снабжённое бинарными операциями и , в котором для любых элементов выполняются следующие аксиомы:[1][2][3]

  1.  — коммутативный моноид. То есть имеют место свойства:
  2.  — полугруппа. То есть имеет место свойство:
  3. Умножение дистрибутивно относительно сложения:
    • Левая дистрибутивность:
    • Правая дистрибутивность:
  4. Мультипликативное свойство нуля:

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

Полукольцо называется коммутативным, если операция умножения в нём коммутативна: .

Полукольцо называется полукольцом с единицей, если в нём существует нейтральный элемент по умножению (называемый единицей): .

Полукольцо называется мультипликативно (или аддитивно) сократимым, если из равенства (или, соответственно, ) следует, что .

Полукольцо называется идемпотентным, если для любого выполняется равенство

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

  • Полукольцо натуральных чисел с нулем.
  • Тривиальное полукольцо:
  • Двухэлементные полукольца: , , где обозначает дизъюнкцию, а  — логическую операцию «исключающее или» на множестве
  • Квадратные матрицы с элементами из полукольца натуральных чисел с нулем и операциями матричного сложения и умножения. Также полукольцо образуют квадратные матрицы с элементами из любого полукольца.
  • Если  — коммутативный моноид, то множество эндоморфизмов образует полукольцо, где сложение определено поточечно, а умножение — как композиция функций.
  •  — многочлены с натуральными коэффициентами — образуют коммутативное полукольцо; это свободное коммутативное полукольцо с единственным генератором .
  • Вероятностное полукольцо — неотрицательные действительные числа с обычными операциями сложения и умножения[2].
  • и  — полукольца вещественных чисел, в которых сложение определено как взятие максимума (соответственно минимума), а умножение — как обычное сложение вещественных чисел.

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

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

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

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

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

  • ;
  • ;
  • .

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

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

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

  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.

Литература[править | править код]