Полукольцо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • ;
  • ;
  • .

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

Полукольцом множеств с единицей называют полукольцо множеств с таким элементом E, что его пересечение с любым элементом A полукольца множеств равно A. Применяя метод математической индукции, можно расширить последний пункт определения: если множества являются элементами полукольца множеств и подмножествами элемента A, то их можно дополнить непересекающимися элементами до 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.

См. также[править | править вики-текст]

Литература[править | править вики-текст]