1   2   3
Ім'я файлу: Новий Документ Microsoft Word.docx
Розширення: docx
Розмір: 141кб.
Дата: 20.07.2021


2.

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

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



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

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

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

λa(x) = ax (x S1).

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

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

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

λab= λaλb,

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

Зададим теперь отображение ϕ из S в T (S1), полагая ϕ(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 (S1). Q

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

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

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

полагая

ψ(x1 . . . xn) = ϕ(x1) . . . ϕ(xn) (x1, . . . , xnX).

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

3.

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

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

Группоид A будем называть полугруппой, если в нем выпол- няется тождество ассоциативности, т. е. для любых a, b, c A справедливо равенство (ab)c = a(bc). Нетрудно установить, что в полугруппе результат многократного применения операции к по- следовательности ее элементов a1, a2, . . . , anне зависит от расста- новки скобок и поэтому обычно записывается в виде a1a2 . . . an. Отметим, однако, что это произведение, вообще говоря, зависит от порядка сомножителей. Для любого элемента a полугруппы и лю- бого натурального числа n можно ввести nстепень элемента, полагая ее равной произведению n экземпляров элемента a и обо- значая через an. Конечно, выполняется обычное правило действия со степенями anam= an+mдля любых натуральных чисел n и m.

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

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

(y1 . . . yn) ∗ (z1 . . . zm) = y1 . . . ynz1 . . . zm

для любых y1, . . . , yn, z1, . . . , zmX. Очевидно, F(X) — полу- группа относительно этой операции. Такую полугруппу называют свободной полугруппой в алфавите X.

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

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

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

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



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

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

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

λa(x) = ax (x S1).

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

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

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

λab= λaλb,

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

Зададим теперь отображение ϕ из S в T (S1), полагая ϕ(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 (S1). Q

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

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

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

полагая

ψ(x1 . . . xn) = ϕ(x1) . . . ϕ(xn) (x1, . . . , xnX).

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

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

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

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

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

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

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

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

M ⟩ = {m1 . . . mk: m1, . . . , mkM, k ∈ N}.

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

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

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

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

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

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

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

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

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

bai1 b2ai2 b2 . . . b2ainb,

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

{x1, x2, . . .}, на полугруппу A, для которого ψ(xi) = ai(i ∈ N).

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

ψ(xi1 . . . xin ) = ϕ(xi1 ) . . . ϕ(xin ) = ai1 . . . ain,

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

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

ψ(xj1 . . . xjm ). Тогда ai1 · . . . · ain = aj1 · . . . · ajm, т.е.

bai1 b2ai2 b2 . . . b2ainb = baj1 b2aj2 b2 . . . b2ajmb

в полугруппе F({a, b}), откуда следует n = m и i1 = j1, . . . , in=

jm, т. е. xi1 . . . xin = xj1 . . . xjm.

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

ψ(xi) = ai(i ∈ N). Q

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

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

4.

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

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

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

  1   2   3

скачати

© Усі права захищені
написати до нас