Открыть главное меню

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

Содержание

ОпределенияПравить

Формально определяется как множество  , снабжённое бинарными операциями   и  , в котором для любых элементов   выполняются следующие аксиомы:[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.

ЛитератураПравить