Полукольцо

Формальное определение

В то время как группа, моноид и полугруппа определяются множеством и одной операцией, полукольцо определяется множеством и двумя операциями. Учитывая множество R

и операции + и *, мы говорим, что (R, +, *) - это полукольцо, если оно удовлетворяет следующим свойствам:

(R, +) является коммутативным моноидом
(R, *) является полугруппой

Для полугруппы должны соблюдаться законы коммутативного моноида по сложению:

Замыкание (closure): для \(\forall x, y \in S\) выполняется \(x + y \in S\).
Ассоциативность (associativity): для \(\forall x, y, z \in S\) выполняется \((x + y) + z = x + (y + z)\).
Тождественность или существования нейтрального элемента (identity): существует \(\exists e \in S\) такой, что для \(\forall x \in S\) выполняется \(e + x = x + e = x\)
Коммутативность (commutative): для \(\forall x, y \in S\) выполняется \(x + y = y + x\).

и законы полугруппы по умножению:

Замыкание (closure): для \(\forall x, y \in S\) выполняется \(x * y \in S\).
Ассоциативность (associativity): для \(\forall x, y, z \in S\) выполняется \((x * y) * z = x * (y * z)\).

, а также дистрибутивность и мультипликативное свойство нуля:

Дистрибутивность (distributivus, распределительный закон): для \(\forall x, y, z \in S\) выполняется \(x * (y + z) = x * y + x * z\) и \((x + y) * z = x * z + y * z\).
Мультипликативное свойство нуля: \(a * 0 = 0 * a = 0\)

Связь с кольцом

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

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

Определение в виде кода на Scala

trait MultiplicativeSemigroup[A]:
  def times(x: A, y: A): A

trait Semiring[A] extends CMonoid[A], MultiplicativeSemigroup[A]

Законы в виде кода на Scala

trait MultiplicativeSemigroupLaw extends Laws:
  def checkMultiplicativeSemigroupLaw[A: MultiplicativeSemigroup](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    check(
      MultiplicativeSemigroup[A]
        .times(MultiplicativeSemigroup[A].times(x, y), z) ==
        MultiplicativeSemigroup[A]
          .times(x, MultiplicativeSemigroup[A].times(y, z)),
      "associative: (x * y) * z == x * (y * z)"
    )
    
trait SemiringLaw extends CMonoidLaw, MultiplicativeSemigroupLaw:
  def checkSemiringLaw[A: Semiring](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    checkCMonoidLaw(x, y, z) combine
      checkMultiplicativeSemigroupLaw(x, y, z) combine
      check(
        Semiring[A].times(x, Semiring[A].combine(y, z)) ==
          Semiring[A].combine(Semiring[A].times(x, y), Semiring[A].times(x, z)),
        "left distributivus: x * (y + z) = x * y + x * z"
      ) combine
      check(
        Semiring[A].times(Semiring[A].combine(x, y), z) ==
          Semiring[A].combine(Semiring[A].times(x, z), Semiring[A].times(y, z)),
        "right distributivus: (x + y) * z = x * z + y * z"
      ) combine
      check(
        Semiring[A].times(x, Semiring[A].empty) == Semiring[A].empty,
        "left zero multiplicative: a * 0 = 0"
      ) combine
      check(
        Semiring[A].times(Semiring[A].empty, x) == Semiring[A].empty,
        "right zero multiplicative: 0 * a = 0"
      )

Примеры

Числа относительно сложения с 0 и умножения

(Z, +, *)

given Semiring[Int] with
  val empty                        = 0
  def combine(x: Int, y: Int): Int = x + y
  def times(x: Int, y: Int): Int   = x * y

Реализация

Реализация в Spire

import spire.algebra.Semiring
import spire.math.Rational

Semiring.plus(Rational(1, 2), Rational(1, 3))
// val res0: spire.math.Rational = 5/6
Semiring.times(Rational(1, 2), Rational(1, 3))
// val res1: spire.math.Rational = 1/6
Semiring.pow(Rational(1, 2), 3)
// val res2: spire.math.Rational = 1/8

Ссылки:

scalabook