Группа

Моноиды, как базовые алгебраические структуры, представляют собой упорядоченные множества с одной ассоциативной операцией и нейтральным элементом. Они служат фундаментом для изучения более сложных структур, таких как группы, которые являются естественным продолжением и расширением моноидов. Группы добавляют к свойствам моноидов ключевое условие — существование обратного элемента для каждого элемента множества. Это позволяет группам обладать более богатым набором свойств и находить применение в широком спектре областей, от теории чисел и геометрии до физики и криптографии.

Что такое группа?

Группа — это алгебраическая структура, которая формализует понятие симметрии и операции, подчиняющейся определенным правилам. Формально, группа определяется как множество \(G\), на котором задана бинарная операция \(\cdot\) (называемая "умножением" или "групповой операцией"), удовлетворяющая четырем аксиомам:

• Замкнутость: Для любых двух элементов \(a, b \in G\) результат операции \(a \cdot b\) также принадлежит \(G\).
• Ассоциативность: Для любых \(a, b, c \in G\) выполняется \((a \cdot b) \cdot c = a \cdot (b \cdot c)\). Это свойство позволяет не учитывать порядок выполнения операций.
• Существование нейтрального элемента: В группе существует элемент \(e \in G\), называемый нейтральным, такой, что для любого \(a \in G\) выполняется \(a \cdot e = e \cdot a = a\).
• Существование обратного элемента: Для каждого элемента \(a \in G\) существует обратный элемент \(a^{-1} \in G\), такой, что \(a \cdot a^{-1} = a^{-1} \cdot a = e\).

Примеры групп

• Целые числа по сложению: Множество \(\mathbb{Z}\) с операцией сложения \(+\) является группой. Нейтральный элемент — 0, а обратный элемент к a — это -a.
• Неотрицательные рациональные числа по умножению: Множество \(\mathbb{Q}^+\) (положительных рациональных чисел) с операцией умножения \(\cdot\) является группой. Нейтральный элемент — 1, а обратный элемент к a — это \(\frac{1}{a}\).
• Группа симметрий фигуры: Множество всех преобразований (например, вращений и отражений), сохраняющих симметрию фигуры, образует группу относительно операции композиции преобразований.
• Натуральные числа не являются группой по сложению (данное число x в \(\mathbb{N}\), но -x не находится в \(\mathbb{N}\)).
• Ни целые числа, ни натуральные числа не являются группой по умножению, но множество ненулевых рациональных чисел (\(\frac{n}{d}\) для любого \(n, d \in N, n \neq 0, d \neq 0\)) является (абелевой) группой по умножению с единичным элементом 1.

Важные свойства групп

• Коммутативность (абелевость): Если для любых \(a, b \in G\) выполняется \(a \cdot b = b \cdot a\), то группа называется абелевой (или коммутативной). В противном случае группа называется неабелевой.
• Порядок группы: Порядок группы \(G\) — это количество элементов в ней. Если группа содержит конечное число элементов, она называется конечной группой. Если элементов бесконечно много, группа называется бесконечной группой.

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

Группа 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 = e\)

Код

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

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

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

Рациональные числа относительно умножения

В упрощенном варианте группа для рациональных чисел будет выглядеть так:

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)

Законы групп

• Замыкание следует из определения функции combine: тип результата этой функции совпадает с типом переменных, которые она принимает.
• Ассоциативность выражается следующим образом: g.combine(x, g.combine(y, z)) должно быть равно g.combine(g.combine(x, y), z).
  Это означает, что порядок объединения элементов не влияет на итоговый результат.
• Тождественность означает, что если вы объединяете любой элемент x с нейтральным элементом (g.empty), то результат всегда будет равен x. Другими словами, нейтральный элемент не меняет значение x при объединении. Это можно записать так:
  • g.combine(x, g.empty) == x
  • g.combine(g.empty, x) == x
• Обратимость означает, что для каждого элемента x существует обратный элемент x.inverse, при объединении с которым результат будет равен нейтральному элементу g.empty. Это можно записать так:
  • g.combine(x.inverse, x) == g.empty
  • g.combine(x, x.inverse) == g.empty

... // Законы моноида

def checkInverse[A](x: A)(using
    g: Group[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    g.combine(x.inverse, x) == g.empty &&
      g.combine(x, x.inverse) == g.empty,
    (),
    "Не соблюдается обратимость: x + (-x) = (-x) + x = e"
  ).toValidatedNel

Схема

classDiagram
    class Semigroup~A~{
        +combine(x: A, y: A) A
    }  
    class Monoid~A~{
        +empty() A
    }
    Semigroup <|-- Monoid
    class Group~A~{
      +inverse(x: A) A
    }  
    Monoid <|-- Group 

Реализация в библиотеках

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

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

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

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

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

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

Ссылки:

• Algebird
• Herding Cats
• Spire home page
• Wikipedia