Группа

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

Группа G — это моноид с обратным \(g^{-1}\) для каждого элемента g.

Множество \(G\) с заданной на нём бинарной операцией +: \(G \times G \to G\) называется группой \((G, +)\), если выполнены следующие аксиомы:

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

Первые три закона наследуются от моноида.

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

trait Group[A] extends Monoid[A]:
  extension (a: A) 
    def inverse: A

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

trait GroupLaw extends MonoidLaw:
  def checkGroupLaw[A: Group](x: A, y: A, z: A): ValidatedNel[String, Unit] =
    checkMonoidLaw(x, y, z) combine
      check(
        Group[A].combine(x, Group[A].inverse(x)) == Group[A].empty,
        "inverse law 1: x + (-x) = 0"
      ) combine
      check(
        Group[A].combine(Group[A].inverse(x), x) == Group[A].empty,
        "inverse law 2: (-x) + x = 0"
      )

Примеры

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

given Group[Int] with
  val empty                           = 0
  def combine(x: Int, y: Int): Int    = x + y
  extension (a: Int) def inverse: Int = -a

Натуральные числа не являются группой по сложению (данное число x в N, но -x не находится в N).
Ни целые числа, ни натуральные числа не являются группой по умножению, но множество ненулевых рациональных чисел (n/d для любого n, d ∈ N, n ≠ 0, d ≠ 0) является (абелевой) группой по умножению с единичным элементом 1.

В примере ниже числитель и знаменатель надо сокращать на НОД и "нормализовывать" знак с проверкой на n ≠ 0, d ≠ 0, но в упрощенном варианте группа для рациональных чисел будет выглядеть так:

final case class Rational(n: Int, d: Int):
  def *(that: Rational): Rational =
    Rational(n * that.n, d * that.d)

given Group[Rational] with
  val empty: Rational                             = Rational(1, 1)
  def combine(x: Rational, y: Rational): Rational = x * y
  extension (a: Rational) def inverse: Rational   = Rational(a.d, a.n)

Реализация

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

import cats.*, cats.syntax.all.*

1.inverse() // -1

assert((1 |+| 1.inverse()) === Monoid[Int].empty)

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

import spire.algebra.Group
import spire.syntax.group.*

1.inverse       // -1
1 |+| 1.inverse // 0

Ссылки:

scalabook