2. Теорема 1 (Кэли). Любая полугруппа изоморфно вложма в симметрическую полугруппу t (X) для подходящего множества X. Доказательство

сохраняя операцию в S и полагая 1a = a1 = a для любого a ∈ S¹.

Очевидно, S¹ — полугруппа относительно этой операции.

Для произвольного элемента a ∈ S на множестве S¹ определим преобразование λ_a, полагая

λ_a(x) = ax (x ∈ S¹).

Преобразование λ_aназывают левым сдвигом, соответствующим элементу a.

Пусть a, b ∈ S и x ∈ S¹. Тогда λ_ab(x) = (ab)x = a(bx) =

a(λ_b(x)) = λ_a(λ_b(x)) = (λ_a◦ λ_b)(x). Следовательно,

λ_ab= λ_a◦ λ_b,

где ◦ — операция суперпозиции преобразований в T (S¹). Отсюда, в частности, вытекает, что T = {λ_a: a ∈ S} — подполугруппа в T (S¹).

Зададим теперь отображение ϕ из S в T (S¹), полагая ϕ(a) = λ_a(a ∈ S). Для любых a, b ∈ S выполняется ϕ(ab) = λ_ab= λ_a◦ λ_b= ϕ(a) ◦ ϕ(b), т. е. ϕ — гомоморфизм. Если ϕ(a) = ϕ(b), то a = a1 = λ_a(1) = ϕ(a)(1) = ϕ(b)(1) = λ_b(1) = b1 = b, т. е. ϕ инъективно.

Итак, ϕ — изоморфизм полугруппы S на подполугруппу T

полугруппы T (S¹). Q

Будем говорить, что полугруппа S₂ является гомоморфным об- разом полугруппы S₁, если существует гомоморфизм из S₁ на S₂.

Лемма 1.1. Любое отображение ϕ непустого множества X в полугруппу S можно продолжить до гомоморфизма ψ свободной полугруппы F(X) в S.

Доказательство. Определим отображение ψ из F(X) в S,

полагая

ψ(x₁ . . . x_n) = ϕ(x₁) . . . ϕ(x_n) (x₁, . . . , x_n∈ X).

Тривиально проверяется, что ψ — гомоморфизм, продолжаю- щий ϕ.

3.

Бинарной операцией на непустом множестве A называется отображение декартова квадрата A × A в множество A. Бинарные операции будем обозначать символами +, ·, ∗, ◦ и т. п. Результат применения операции ∗ к элементам a, b ∈ A будем обозначать через a ∗ b. Часто символ операции опускают и пишут просто ab. Такую форму записи называют мультипликативной.

Группоидом называют непустое множество вместе с некоторой бинарной операцией на нем.

Группоид A будем называть полугруппой, если в нем выпол- няется тождество ассоциативности, т. е. для любых a, b, c ∈ A справедливо равенство (ab)c = a(bc). Нетрудно установить, что в полугруппе результат многократного применения операции к по- следовательности ее элементов a₁, a₂, . . . , a_nне зависит от расста- новки скобок и поэтому обычно записывается в виде a₁a₂ . . . a_n. Отметим, однако, что это произведение, вообще говоря, зависит от порядка сомножителей. Для любого элемента a полугруппы и лю- бого натурального числа n можно ввести n-ю степень элемента, полагая ее равной произведению n экземпляров элемента a и обо- значая через aⁿ. Конечно, выполняется обычное правило действия со степенями aⁿa^m= aⁿ⁺^mдля любых натуральных чисел n и m.

Примеры. 1) Пусть T (X) — множество всех преобразова- ний непустого множества X. Определим на T (X) бинарную опе- рацию ◦ суперпозиции преобразований, полагая α ◦ β(x) = α(β(x)) для любых α, β ∈ T (X) и x ∈ X. Легко проверить ассоциатив- ность этой операции. Полученную полугруппу называют симмет- рической полугруппой на множестве X.

2) Пусть X — непустое множество и F(X) — множество всех непустых слов в алфавите X. Определим на F(X) бинарную опе- рацию ∗ конкатенации слов, полагая

(y₁ . . . y_n) ∗ (z₁ . . . z_m) = y₁ . . . y_nz₁ . . . z_m

для любых y₁, . . . , y_n, z₁, . . . , z_m∈ X. Очевидно, F(X) — полу- группа относительно этой операции. Такую полугруппу называют свободной полугруппой в алфавите X.

Пусть S — полугруппа. Подмножество T ⊆ S называется под- полугруппой, если оно замкнуто относительно операции из S, т. е. ab ∈ T для любых a, b ∈ T. Далее в число подполугрупп произ- вольной полугруппы будем включать пустую подполугруппу ∅. Если T — подполугруппа полугруппы S, то будем писать T ≤ S. Пусть S₁ и S₂ — полугруппы. Отображение ϕ из S₁ в S₂ называ- ется гомоморфизмом, если ϕ(ab) = ϕ(a)ϕ(b) для любых a, b ∈ S₁. Если ϕ является биекцией, то этот гомоморфизм называют изо- морфизмом.

Будем говорить, что полугруппа S₁ изоморфно вложима в по- лугруппу S₂, если S₁ изоморфна некоторой подполугруппе из S₂.

Теорема 1.1 (Кэли). Любая полугруппа изоморфно вложи- ма в симметрическую полугруппу T (X) для подходящего множе- ства X.

Доказательство. Пусть S — произвольная полугруппа. Ес- ли S имеет единицу 1, т. е. элемент, для которого выполняются равенства a1 = 1a = a (a ∈ S), то положим S¹ = S. Пусть S не имеет единицы. Будем считать, что 1 — это элемент, не лежащий в S. На множестве S¹ = S ∪ {1} определим бинарную операцию,

Теорема 1.2. Любая полугруппа является гомоморфным об- разом свободной полугруппы F(X) для подходящего алфавита X.

Доказательство. Пусть S — произвольная полугруппа. За- фиксируем множество X такое, что |X| ≥ |S|. Очевидно, суще- ствует отображение ϕ из X на S. В силу леммы 1.1 существует гомоморфизм из F(X) на S. Q

Лемма 1.2. Пересечение любого семейства подполугрупп по- лугруппы является подполугруппой.

Доказательство. Пусть T_i(i ∈ I) — семейство подполугрупп полугруппы S. Если a, b ∈ ∩_iT_i, то последовательно получаем a, b ∈ T_i(i ∈ I), ab ∈ T_i(i ∈ I), ab ∈ ∩_iT_i. Q

Заметим, что пересечение пустого семейства подполугрупп по- лугруппы S по определению считается равным S.

Пусть M ⊆ S. Через ⟨M ⟩ обозначим пересечение всех подпо- лугрупп полугруппы S, содержащих M. В силу леммы 1.2 под- множество ⟨M ⟩ является подполугруппой. Это наименьшая под- полугруппа из S, содержащая M. Говорят, что множество M по- рождает подполугруппу ⟨M ⟩. Если S = ⟨M ⟩, то M называют порождающим множеством полугруппы S.

Теорема 1.3. Пусть M — произвольное подмножество полу- группы S. Тогда

⟨M ⟩ = {m₁ . . . m_k: m₁, . . . , m_k∈ M, k ∈ N}.

Доказательство. Включение ⊇ очевидно. В правой части доказываемого равенства указана подполугруппа из S, содержа- щая M. Теперь ясно, что это равенство имеет место, поскольку

⟨M ⟩ — наименьшая подполугруппа из S, содержащая M. Q

Пример. Если y₁ . . . y_n∈ F(X), где y₁, . . . , y_n∈ X, то n назы- вают длиной слова y₁ . . . y_n. Слова длины 1 будем отождествлять

с соответствующими буквами из X. Ясно, что X — порождающее множество свободной полугруппы F(X). Его называют множе- ством свободных образующих полугруппы F(X).

Пусть ψ — изоморфизм F(X) на полугруппу S. Тогда S также будем называть свободной полугруппой, а множество ψ(X) — ее множеством свободных образующих.

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

Построим пример полугруппового кода счетной мощности в свободной полугруппе F({a, b}), где a и b — два различных сим- вола. В полугруппе F({a, b}) положим a_i= baⁱb (i ∈ N).

Теорема 1.4. Множество {a_i: i ∈ N} — счетный полугруп- повой код в свободной полугруппе F({a, b}).

Доказательство. Через A обозначим подполугруппу, порож- денную множеством {a_i: i ∈ N}. Ясно, что элементы из A и только они представимы в виде слов вида a_i1 · . . . · a_in, т.е. вида

baⁱ1 b²aⁱ2 b² . . . b²aⁱnb,

где i₁, i₂, . . . , i_n∈ N. Для доказательства теоремы нам достаточно построить изоморфизм ψ свободной полугруппы F(X), где X =

{x₁, x₂, . . .}, на полугруппу A, для которого ψ(x_i) = a_i(i ∈ N).

Определим отображение ϕ из X в A, полагая ϕ(x_i) = a_i(i ∈ N). По лемме 1.1 отображение ϕ можно продолжить до гомо- морфизма ψ из F(X) в A. Поскольку

ψ(x_i1 . . . x_in ) = ϕ(x_i1 ) . . . ϕ(x_in ) = a_i1 . . . a_in,

ясно, что ψ является гомоморфизмом на все A.

Проверим теперь инъективность ψ. Пусть ψ(x_i1 . . . x_in ) =

ψ(x_j1 . . . x_jm ). Тогда a_i1 · . . . · a_in = a_j1 · . . . · a_jm, т.е.

baⁱ1 b²aⁱ2 b² . . . b²aⁱnb = ba^j1 b²a^j2 b² . . . b²a^jmb

в полугруппе F({a, b}), откуда следует n = m и i₁ = j₁, . . . , i_n=

j_m, т. е. x_i1 . . . x_in = x_j1 . . . x_jm.

Итак, ψ — изоморфизм полугруппы F(X) на A такой, что

ψ(x_i) = a_i(i ∈ N). Q

Из доказанной теоремы вытекает

Следствие. Свободная полугруппа со счетным множеством свободных образующих изоморфно вложима в свободную полугруппу с двумя свободными образующими.

4.

Теорема 2.2. Любая группа является гомоморфным образом свободной группы FG(X) для подходящего алфавита X.

Доказательство. Пусть G — произвольная группа. Зафик- сируем множество X такое, что |X| ≥ |G|. Тогда существует отоб- ражение ϕ из X на G. Теперь в силу леммы 2.4 группа G есть гомоморфный образ группы FG(X). Q

Слово в алфавите X ∪ X⁻¹ называется редуцированным, если оно не содержит подслов вида a^εa⁻^ε, где a ∈ X и ε ∈ {1, −1}. Очевидно, любое слово эквивалентно некоторому редуцированно- му слову. Более того, справедлива