Группоиды, полугруппы, группы

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

 Группоидом называют любую алгебру g = (G, ⋅), сигнатура которой состоит из одной бинарной операции. В группоиде на бинарную операцию нет никаких ограничений.

Группоид (G, ⋅) называют полугруппой, если его операция ассоциативна, т.е. для любых элементов а, b, с носителя G выполняется равенство а ⋅ (b ⋅ с) = (а ⋅ b) ⋅ с.

 Пример 2.6. а. Множество V₃ свободных векторов вместе с операцией векторного умножения является группоидом, но не полугруппой, так как векторное умножение не ассоциативно.

 б. Множество натуральных чисел вместе с операцией возведения в степень также будет только группоидом, так как (a^bc ≠ a ^(bc) 

 в. Множество 2^А всех подмножеств множества А вместе с операцией \ (разность множеств) тоже только группоид, поскольку указанная операция не ассоциативна.

 г. Множество натуральных чисел N вместе с операцией сложения будет полугруппой. #

Группоид g = (G, ⋅) называют моноидом, если его операция ассоциативна и относительно операции существует нейтральный элемент. Его называют нейтральным элементом моноида g или единицей моноида и обозначают 1. Таким образом, моноид g = (G, ⋅) есть полугруппа, в которой для любого а имеют место равенства а ⋅ 1 = 1 ⋅ а = а, где 1 — нейтральный элемент (единица) моноида.

Поскольку нейтральный элемент относительно любой бинарной операции является единственным (см. 2.1), мы можем рассматривать моноид как алгебру (G, ⋅, 1), сигнатура которой состоит из двух операций: бинарной операции ⋅ (умножение) и нульарной операции 1 (нейтрального элемента). Введение 1 в сигнатуру моноида удобно тем, что зачастую при рассмотрении конкретных примеров моноидов целесообразно явно указать нейтральный элемент относительно его операции. Например, алгебра (2^A×A, ॰, id_A) есть моноид всех бинарных отношений на множестве А с операцией композиции бинарных отношений, в котором нейтральным элементом является диагональ множества А.

Среди полугрупп выделяют полугруппы с коммутативной операцией — коммутативные полугруппы.

 Пример 2.7. а. Множество всех бинарных отношений на произвольном множестве А с операцией композиции отношений будет моноидом, нейтральным элементом которого служит диагональ множества А, поскольку для любых бинарных отношений р, т и а на множестве А имеют место равенства (см. 1.4)

ρ॰(τ॰σ ) = (ρ॰τ)॰σ и id_A॰ρ = ρ॰id_A = ρ

б. Множество всех отображений некоторого множества А в себя по операции композиции отображений есть моноид.

Напомним, что композиция отображений снова есть отображение и операция композиции имеет нейтральный элемент: тождественное отображение А на себя. Поскольку любое отображение множества А в себя можно рассматривать как би- бинарное отношение на этом множестве, а композицию отображений — как частный случай композиции отношений, требуемые свойства операции композиции отображений выполняются (см. пример 2.7.а). При этом тождественному отображению соответствует диагональ id_A множества А. Этот моноид называют часто симметрическим моноидом или симметрической полугруппой множества А.

 в. Алгебра (N₀, +), где носитель — множество N₀ неотрицательных целых чисел, а сигнатура состоит из одной операции сложения, есть коммутативный моноид, в котором нейтральный элемент — это число 0. Действительно, сумма двух на- натуральных чисел есть натуральное число, операция сложения ассоциативна, коммутативна и для любого натурального числа п имеет место равенство n + 0 = n.

Обратим внимание на то, что свойства нейтральных элемен- элементов и нулей ассоциируются со свойствами чисел 1 и 0 относи- относительно операций умножения и сложения чисел.

 г. Алгебра (Z, ⋅), у которой носителем является множество целых чисел, а сигнатура состоит из одной операции умноже- умножения, есть коммутативный моноид. Нейтральным элементом этого моноида является число 1.

 д. Пусть А — конечное множество, а Аⁿ — множество кортежей длины n. На множестве всех кортежей определим операцию соединенил (конкатенации) кортежей следующим образом:

(a₁, ..., a_m)⋅(b₁, ..., b_k) = (a₁, ..., a_m, b₁, ..., b_k).

Можно видеть, что введенная операция ассоциативна, но не имеет нейтрального элемента. Таким образом, построена полугруппа, но не моноид.

Чтобы превратить эту полугруппу в моноид, расширим носитель полугруппы, введя понятие нулевой декартовой степени А⁰ произвольного множества А. Под А⁰ понимают одноэлементное множество {λ}, единственный элемент которого называют пустым кортежем. Такое определение множества А⁰ объясняется следующим: мощность положительной декартовой степени Аⁿ конечного множества равна |А|¹. При n = 0 должно быть |А⁰| = |А⁰| = 1, откуда заключаем, что А⁰ — одноэлементное множество.

Обозначив А* = A⁰ ∪ А⁺, по определению для любого х ∈ А* полагаем х ⋅ λ = λ ⋅ х = х. В результате получим алгебру (А*, ⋅), являющуюся моноидом, с нейтральным элементом λ. Его называют свободным моноидом, порожденным множеством А. #

Полугруппу, операция которой коммутативна и идемпотентна, называют полурешеткой.

 Пример 2.8. а. Алгебры (2^A, ∪), (2^A∩) (для произвольного фиксированного множества А) являются полурешетками, поскольку операции ∪ и ∩ ассоциативны, коммутативны и идемпотентны.

 б. Алгебра (N, НОК), где НОК — операция вычисления наименьшего общего кратного двух чисел, является полурешеткой. Покажем, что указанная операция ассоциативна. Рассмотрим произвольные натуральные числа m, n и l. Каждое из этих чисел можно разложить на произведение простых чисел и представить в виде

m = p^α₁1 ... p^α_kk, n = p^β₁1 ... p^β_kk, l = p^γ₁1 ... p^γ_kk

где набор простых чисел p₁, ..., p_k выбран одинаковым для всех трех чисел, а некоторые из показателей α_i, β_i, γ_i, i = 1, k, могут быть равными нулю. Тогда для чисел тип имеем

HOK(n,m) = p^{max(α₁,β₁)1} ... p^{max(α_k,β_k)k}

Таким образом, ассоциативность операции НОК сводится к ассоциативности операции max вычисления наибольшего из двух натуральных чисел. Ассоциативность последней вытекает из очевидного тождества max(a,max(b,c)) = max(max(a,b),c), верного для любых чисел а, b и с.

Поскольку HOK(n,m) = HOK(m,n), операция НОК коммутативна, а так как для любого натурального числа справедливо равенство НОК(n,n) = n, то операция идемпотентна.

 в. Алгебра (N, НОД), где НОД — операция вычисления наибольшего общего делителя двух целых чисел, также является полурешеткой. #

Группоид g = (G, ⋅) называют группой, если операция ассоциативна, существует нейтральный элемент (единица) 1 относительно умножения и для каждого х ∈ G существует такой элемент х' ∈ G, называемый обратным к x, что х⋅х' = х'⋅х = 1.

Таким образом, группа — это алгебра g = (G, ⋅), в которой для всех a, b, c ∈ G выполняется равенство а⋅ (b ⋅ с) = (а⋅ b) ⋅ с, существует единственный элемент 1 ∈ G, такой, что а ⋅ 1 = 1 ⋅ а = а для любого а ∈ G, и для каждого a ∈ G существует такой элемент а', что а ⋅ а' = а' ⋅ а = 1. Короче говоря, группа — это моноид, в котором для каждого элемента существует обратный элемент.

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

Во-первых, в сигнатуру может быть включена единственная бинарная операция. В этом случае пишут g = (G, ⋅), а все свойства операции описывают дополнительно.

Во-вторых, в сигнатуру может быть включена нульарная операция — нейтральный элемент группы. В этом случае пишут g = (G, ⋅, 1) и дополнительно указывают существование обратного элемента относительно бинарной операции для всех элементов носителя. 

Третий способ задания группы как алгебры вытекает из следующей теоремы.

 Теорема 2.1. В любой группе g = (G, ⋅) для каждого a ∈ G элемент, обратный к а, единственный.

◀ Пусть в группе (G, ⋅) с единицей 1 для некоторого а уществуют два элемента а' и а", обратных к а. Тогда а' = а' ⋅ 1 в силу свойства единицы. Так как 1 = а ⋅ а", то а' = а' ⋅(а ⋅ а"). Используя ассоциативность и учитывая, что а' — элемент, обратный к а, получим

а' ⋅ (a ⋅ а") = (а'⋅ а) ⋅ а" = 1 ⋅ а" = а". ▶

Единственность для каждого элемента а обратного элемента а' группы g позволяет обозначать его как a^-1 и операцию ^-1: а → a^-1 вычисления (или взятия) обратного элемента ввести в сигнатуру группы. Таким образом, группу можно рассматривать и как алгебру g = (G, ⋅, ^-1, 1), сигнатура которой состоит из бинарной операции умножения, унарной операции взятия обратного элемента и нульарной операции — единицы группы (нейтрального элемента).

В дальнейшем в зависимости от контекста будем использовать все указанные варианты задания группы.

Среди групп также выделяют те, бинарная операция в которых коммутативна, — коммутативные (абелевы*) группы  *Н. Абель (1802-1829) — норвежский математик.  В коммутативных полугруппах и группах бинарную операцию часто обозначают знаком + и называют сложением.

Уместно здесь рассмотреть вопрос о двух формах записи бинарной операции группы. В аддитивной записи операции ее обозначают знаком +, нейтральный элемент — знаком 0, а элемент, обратный к а относительно операции +, записывают в виде -а, называя его при этом противоположным к а.

В мультипликативной записи операцию обозначают знаком ⋅, нейтральный элемент — знаком 1, а элемент, обратный к а, записывают в виде ^-1. В этом случае бинарную операцию группы часто называют умножением (также умножением группы или групповым умножением), а элемент а ⋅ b, как правило записываемый в виде аb, — произведением элементов а и b.

В алгебраической литературе сложилась такая традиция, что аддитивная запись используется преимущественно для коммутативных групп. Поскольку одним из самых простых, распространенных и вместе с тем важных примеров коммутативной группы служит аддитивная группа целых чисел, то обозначения и термины для произвольной аддитивно записываемой коммутативной группы „скопированы" с терминов для группы (Z, +, 0). Аналогично мультипликативная запись произвольной группы „позаимствована" у мультипликативных групп рациональных и вещественных чисел.

 Пример 2.9. а. Алгебра (Z, +) — коммутативная группа, поскольку на множестве целых чисел операция сложения ассоциативна и коммутативна, число 0 есть нейтральный элемент, и для каждого целого числа п существует обратный по сложению элемент, а именно число - n, противоположное n. Рассматриваемую группу называют аддитивной группой целых чисел.

б. Множество всех биекций некоторого множества А на себя с операцией композиции отображений есть группа.

Это следует из того, что композиция двух биекций есть биекция, операция композиции ассоциативна, ее нейтральный элемент — тождественное отображение id_A — есть биекция, для всякой биекций f: A → А отображение f^-1, обратное биекций f, определено, является биекцией и выполнены равенства f॰f^-1 = f^-1॰f = id_A.

Эту группу называют симметрической группой множества А, а в том случае, когда множество А конечно, — группой подстановок множества А. Если множество А состоит из n элементов, группу подстановок этого множества называют также симметрической группой степени n или группой подстановок n-й степени и обозначают S_n (см. пример 2.10).

 в. Алгебры (g\{0}, ⋅) и (R\{0}, ⋅) есть коммутативные группы. Их называют мультипликативной группой рациональных чисел и мультипликативной группой действительных чисел соответственно. В каждой из них число 1 есть нейтральный элемент (единица) группы, а обратный к числу х по операции умножения элемент х^-1 есть число х^-1 = 1/х. г.

г. Для произвольно фиксированного множества А рассмотрим алгебру (2^A, Δ), где Δ — операция вычисления симметрической разности множеств. Операция Δ ассоциативна и коммутативна (см. 1.1). Для любого X ⊆ А имеем X Δ ∅ = X. Кроме того, X = Y тогда и только тогда, когда X Δ У = ∅. Поэтому алгебра (2^A, Δ) является абелевой группой, в которой каждый элемент обратен сам себе, а нейтральный элемент — пустое множество.

 д. Рассмотрим алгебру Z^+k = ({0,1,..., к — 1}, ⊕_k), в которой операция ⊕_k (сложения по модулю к) определяется так: для любых двух m и n число m⊕_kn, называемое суммой чисел m и n по модулю к, равно остатку от деления арифметической суммы m + n на k. Можно проверить, что эта алгебра является коммутативной группой. Бе называют аддитивной группой вычетов по модулю k. Нейтральным элементом служит число 0, а обратным к числу n будет k - n, поскольку n ⊕_k (k - n) = 0.

 е. Множество всех невырожденных (т.е. имеющих ненулевой определитель) числовых квадратных матриц порядка п с операцией умножения матриц является группой. Действительно, произведение двух невырожденных матриц снова есть невырожденная матрица [III]; единичная матрица порядка n невырожденная, и матрица, обратная к невырожденной, также является невырожденной. Эту группу будем обозначать М_n. #

Из рассмотренных четырех видов алгебр — группоида, полугруппы, моноида и группы — последняя обладает наиболее интересными свойствами. Изучим более подробно операцию вычисления обратного элемента.

Теорема 2.2. Пусть g = (G, ⋅) — группа. Для любых элементов а, b ∈ G верны тождества

(a⋅b)^-1 = b^-1 ⋅ a^-1, (a^-1)^-1 = a.

◀В силу ассоциативности умножения группы имеем

(a⋅b)⋅(b^-1 ⋅ a^-1) = ((a ⋅ b) ⋅b^-1)⋅a^-1.

Используя еще раз ассоциативность, определение элемента, обратного к данному, и свойства единицы, получим

((a ⋅ b) ⋅ b^-1) ⋅ a^-1 = a ⋅ (b ⋅ b^-1) ⋅ a^-1 = a ⋅ a^-1 = 1

Итак, (a ⋅ b) ⋅ ( b^-1 ⋅ a^-1) = 1. Точно так же доказывается, что ( b^-1 ⋅ a^-1)(а ⋅ b) = 1. Поэтому элемент b^-1a^-1 является обратным к элементу а ⋅ b. Согласно теореме 2.1, обратный элемент единственный, и поэтому (а ⋅ b)^-1 = b^-1 ⋅ а^-1. Второе из доказываемых равенств следует непосредственно из определения элемента, обратного к данному. Действительно, определение элемента а^-1, обратного к а, равенством а^-1 ⋅ а = а ⋅ а^-1 = 1 можно рассматривать как определение (а^-1)^-1 - обратного элемента к а^-1, которым является, согласно этим равенствам, элемент а. В силу теоремы 2.1 он единственный, т.е. а = (а^-1)^-1. ▶

Таким образом, мы установили, что элемент, обратный к произведению а ⋅ b, равен b^-1 ⋅ а^-1, а элемент, обратный к элементу, обратному к а, равен а.

Теорема 2.3. В любой группе g = (G, ⋅, 1) справедливы левый и правый законы сокращения: если а ⋅ х = a ⋅ у, то х = у, и если х ⋅ а = у ⋅ а, то х = у.

◀ Пусть а ⋅ х = а ⋅ у. Умножая обе части этого равенства слева на элемент а^-1, получаем

а^-1 ⋅ (а ⋅ х) = а^-1 ⋅ (а ⋅ у).

В силу ассоциативности групповой операции последнее равенство можно записать так:

(а^-1 ⋅ а) ⋅ х) = (а^-1 ⋅ а) ⋅ у.

Поскольку а^-1 ⋅ а = 1, то 1 ⋅ х = 1 ⋅ у, откуда х = у. Тем самым доказан левый закон сокращения. Аналогично доказывается и правый закон. ▶

Пусть g = (G, ⋅, 1) — группа, а, b — фиксированные элементы G. Рассмотрим задачу решения уравнений

а ⋅ х = b,       (2.1)

х ⋅ а = b      (2.2)

в группе g, т.е. поиска всех таких элементов х ∈ G, для которых уравнение (2.1) (или 2.2)) превращается в тождество.

Теорема 2.4. В любой группе g уравнения вида (2.1) и (2.2) имеют решения, и притом единственные.

◀Покажем, что x =а^-1 ⋅ b есть решение (2.1). Действительно, а ⋅ (а^-1 ⋅ b) = (а ⋅ а^-1 ⋅ b) = b.

Докажем единственность решения. Пусть для фиксированных а и b и некоторого х выполнено равенство а ⋅ х = b. В группе для любого а существует и однозначно определен элемент а^-1, обратный к а. Умножив на него обе части равенства, получим а^-1 ⋅ (a ⋅ x) = а^-1 ⋅ b. В силу ассоциативности преобразуем последнее равенство к виду (а^-1 ⋅ а) ⋅ х = а^-1 ⋅ b. Поскольку а^-1⋅ а = 1, то 1 ⋅ х = а^-1 ⋅ b, откуда х = а^-1 ⋅ b. Это решение единственное в силу единственности обратного элемента.

Аналогично из х ⋅ a = b получаем х = b ⋅ а^-1, и это решение также единственное. ▶

 Замечание. При использовании аддитивной записи операции для коммутативной группы g = (G, +, 0) оба написанных выше уравнения сводятся к одному: а + х = b, а его решение есть х = b + (-а). Правую часть этого равенства в коммутативной группе называют разностью элементов b и а и обзначают b - а. Саму же операцию, сопоставляющую упорядоченной паре (а,b) разность b-a, называют операцией вычитания. С учетом введенных обозначений решение уравнения в коммутативной группе можно записать так: х = b - а.

В случае коммутативной группы при употреблении для бинарной операции мультипликативной записи решения обоих уравнений имеют вид х = b ⋅ а^-1. Выражение b ⋅ а^-1в коммутативной группе называют частным от деления b на а и обозначают b/а, а саму операцию называют операцией деления. Решение уравнения в этом случае записывают в виде х = b/а).

 Пример 2.10. Рассмотрим группу подстановок n-й степени Sn всех биекций n-элементного множества {1,2, ...,п}. Произвольную биекцию а из S_n обычно записывают в виде

обозначая тем самым, что образ 1 (при отображении σ) есть a₁, образ 2 есть a₂, ..., образ n есть a_n. Биекцию множества {1, ...,n} на себя называют подстановкой этого множества. Подстановку, которая отображает a₁ в a₂, a₂ в a₃, ..., a_k-1в a_k, а a_k в a₁, где 1≤a₁, a₂, ..., a_k≤ n и все а_j попарно различны, а все элементы, отличные от a₁, ..., a_k, отображаются сами в себя, называют циклом длины k и записывают ее в виде (a₁ a₂ ... a_k). Например, подстановку из группы S₄

можно записать в виде 1 3 4).

Цикл длины 2 называют транспозицией. Транспозиция представляет такое отображение множества {1, ...,n} в себя, при котором два элемента меняются местами, а остальные остаются на своих местах. Так, полная запись транспозиции (3 4) в S₄ будет иметь вид

Подстановка, обратная подстановке

есть подстановка, которая отображает a₁ в 1, a₂ в 2, ... a_т в n. Отметим, что при записи обратной подстановки элементы первой строки тем не менее записываются в обычном порядке: 1, ..., n.

В группе S₃ решим следующее уравнение:

Умножив обе части уравнения слева на

получим

Далее, умножив полученное уравнение справа на

окончательно получим

В полугруппе в общем случае законы сокращения и разрешимость уравнений типа (2.1) и (2.2) могут не иметь места. Например, в полугруппе квадратных матриц фиксированного порядка с операцией умножения матриц из матричного равенства АХ = АУ, вообще говоря, не следует, что X = У. Это можно утверждать лишь при дополнительном предположении, что detA ≠ 0. Можно доказать, что в свободном моноиде, порожденном некоторым конечным множеством, оба закона сокращения справедливы, но никаких обратных элементов не существует.

В полугруппе можно умножать любой элемент а сам на себя, причем в силу ассоциативности операции полугруппы элемент определен однозначно. Этот элемент называют n-й степенью элемента а и обозначают аⁿ. При этом а¹ = а, аn = а⋅а^n-1, n = 2, 3, ...

В моноиде вводят также нулевую степень элемента, полагая а⁰ = 1.

Если (А, ⋅, 1) — группа, то можно ввести и отрицательные степени элемента согласно равенству а^-n = (a^-1) ⁿ, n = 1, 2, ...

Без доказательства сформулируем утверждения о свойствах степеней.

Теорема 2.5. Для любой полугруппы ^-n ⋅ аⁿ = a^m+n, (a^m)ⁿ = a^mn (m, n ∈ ℕ).

Теорема 2.6. Для любой группы а^-n = (аⁿ)^-1 (n ∈ ℕ), a^m ⋅ aⁿ = a^m+n, (a^m)ⁿ = a^mn (m, n ∈ ℤ)

Определение 2.4. Полугруппу (в частности, группу) (A,⋅) называют циклической, если существует такой элемент а, что любой элемент х полугруппы является некоторой (целой) степенью элемента а. Элемент а называют образующим элементом полугруппы (группы).

Пример 2.11. а. Полугруппа (ℕ₀, +, 0) циклическая, с образующим элементом 1. При аддитивной записи бинарной операции возведение элемента а в положительную степень n есть сумма n этих элементов, и это записывают n ⋅ а (или nа, без знака умножения).

б. Группа (ℤ, +, 0) также циклическая. Для нее образующими элементами могут быть 1 и -1. Рассмотрим элемент 1.

Если в качестве образующего взять элемент - 1, то 0 ⋅ (-1) = = 0, отрицательные целые числа получаются как положительные „степени" -1, а положительные — как отрицательные „степени" -1. Например, (-2) ⋅ (-1) = 2, 4 ⋅ (-1) = -4.

в. Группа (Z₃, ⊕₃, 0) вычетов по модулю 3 циклическая, причем любой ее ненулевой элемент является образующим.

Действительно, для 1 имеем 1 ⊕₃ 1 = 2, 1 ⊕₃ 1 ⊕₃ 1 = 0, а для 2 получим 2² = 2 ⊕₃ 2 = 1, 2 ⊕₃ 2 ⊕₃ 2 = 0. #

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

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

Так, например, аддитивная группа вычетов по модулю k имеет порядок k. Симметрическая группа степени n, т.е. группа подстановок S_n, имеет порядок n!. Мультипликативная группа вычетов по модулю р, где р — простое число, имеет порядок р - 1.

 Порядок элемента а циклической группы — это наименьшее положительное n, такое, что аⁿ = 1.

 Теорема 2.7. Порядок образующего элемента конечной циклической группы равен порядку самой группы.

◀Пусть g = (G, ⋅, 1) — конечная циклическая группа с образующим элементом а и n > 0 — порядок этого элемента.

Тогда все степени а⁰ = 1, а¹ = а, ..., а^n-1 попарно различны. Действительно, если а^k = а^l, 0 < 1 < k < n, то а^k-l = а^k+(-l)= = а^ka^-l = а^1l а^-l = a^l-l= 1. Поскольку к - l < n, получено противоречие с выбором n как порядка элемента а (ибо найдена степень, меньшая n, при возведении в которую элемента а получится единица).

Осталось доказать, что любая степень элемента а принадлежит множеству {1, а, ..., а^n-1}. Для любого целого m существуют также целые n, k, такие, что m = kn + g, где g — целое и 0 ≤ g < n. Тогда а^m = а^kn+g = (aⁿ)^k) ⋅ ^g = 1 ⋅ ^g = a^g ∈ {1, а, ..., а^n-1}. Поскольку каждый элемент группы g есть некоторая степень элемента а, то G = {1,а, ... a^n-1} и порядок группы равен n. ▶

Из доказанной теоремы следует, что в бесконечной циклической группе не существует такого n > 0, что для образующего элемента а группы выполняется равенство aⁿ = 1.