Дискретно-непрерывная математика (стр. 53 )

7. Z обозначает множество целых чисел {0, ± 1, ± 2, ... }. (Z, + ) есть группа целых чисел с обычной операцией сложения. Z+ обозначает множество неотрицательных целых чисел. (Z+, + ) — подполугруппа группы (Z, + ). Обозначим через (п) конгруэнтность на группе (Z, + ), для которой z1(n)z2 [обычно это записывается z1 ≡ z1 (mod п)] тогда и только тогда, когда z1 — z2 = kn для некоторого k Z. Zn = Z/(п) называется циклической группой порядка п или аддитивной группой целых чисел по модулю п.

8. Пусть S — произвольная полугруппа.

1) Определим полугруппу S1. Если S — моноид, то по определению S1=S; в противном случае S1=S {1}, где символ 1S. Распространим операцию умножения, заданную в S, на множество S {1}, полагая

11 = 1 и 1s = s1 = s для любого s S.

2) Определим полугруппу S0. Если S содержит нуль и |S|>1, то S0=S. В противном случае S0=S {0}, где символ 0S. Распространим операцию умножения, заданную в S на множество S {0}, полагая

00 = 0s = s0 = 0 для любого элемента s S.

3) Определим полугруппу SІ =S {І}, где ІS. Распространим операцию умножения, заданную в S, на множество S {І}, полагая ІІ =І, Is = sІ = s для любого элемента s S.

Будем отождествлять единицу полугруппы (∑А)1 с пустым множеством. В некоторых разделах настоящей работы свободный моноид (∑А)1 обозначается как А*.

9. Пусть А и В— непустые множества. Тогда F (А, В) обозначает множество всевозможных отображений из А в В. Запишем множество F (А, А) в виде F (А). Обозначим через FL(А) полугруппу [F(А), • ], для которой умножение определяется соотношением (fg)(а)=f[g(a)], где элемент аА. Обозначим через FR(A) полугруппу [F(A), °], для которой умножение определяется соотношением (f°g)(а)=g[f(а)], аА. Иногда, имея дело с полугруппой Fr(A), вместо f (а) будем писать а(f). Следовательно, (a)(f°g)=[(а)f] g. Пусть символы SYML (A) FL(A) и SYRR(A)FR(A) обозначают подгруппы, которые состоят из взаимно однозначных отображений множества A.

Пусть S — полугруппа, определим отображение L : S →Fl (S1), для которого L(s)(r)=sr, где sS и rS1. Отображение L — взаимно однозначный гомоморфизм, так как

L (s1s2) (r) = s1s2r = L (s1) [L (s2) (r)] = L (s1) L (s2) (r)

и L(s)(1)=s для любых элементов s, s1,s2S и любого элемента rS1. Мономорфизм L называется левым регулярным представлением полугруппы S. Следовательно, каждая полугруппа изоморфна подполугруппе из Fl (А) для некоторого множества А.

Аналогично отображение R:S→FR(S1), определяемое соотношением (r) R (s) = rs, где r S1, s S, является мономорфизмом, который называется правым регулярным представлением полугруппы S.

Заметим, что полугруппа FR(X) изоморфна подполугруппе из (2Х×Х, •). Элементы этой подполугруппы — всевозможные отношения R, которые обладают следующим свойством: для каждого элемента х X существует один и только один элемент у X, такой, что (х, у) R. Полугруппа Fl (X) изоморфна из (2Х×Х, •) , что состоящей из всевозможных отношений, для которых для элемента у существует единственный элемент х, такой, что (х, у) R.

10. Пусть X - конечное множество. Симметричной инверсной полугруппой на множестве X называется множество всех взаимно однозначных эпиморфных отображений, областью определения и областью значения которых являются подмножества из X*. Пусть f:A→В и g:C→D — отображения с такими свойствами. Тогда отображение gf имеет область определения f-1(BC) и область значения g(В C), отображение gf удовлетворяет соотношению gf(a)=[gf(a)]. Построенная полугруппа обозначается SISL(X). Аналогично определяется полугруппа SISR (X).

11. Пусть S - полугруппа. Тогда по определению r (S) есть полугруппа (S, • ), для которой s1 • s2 = s2s1, где s1, s2 S. Очевидно, r [r (S)] = S. Равенство r (S)=S выполнено тогда и только тогда, когда полугруппа S — абелева. Если S представляет собой группу, то отображение х→х-1 определяет изоморфизм группы S с группой r(S), поскольку (ху)-1=у-1х-1. Однако при | А |≥2 полугруппа Аl не изоморфа полугруппе r (Аl) = АГ.

Определение, теорема, конструкция и т. д., которые сформулированы для полугруппы S, всегда имеют двойственный аналог для полугруппы r(S), т. е. соответствующее определение, теорему, конструкцию относительно полугруппы r(S). Мы не будем давать точного определения понятия двойственности, однако, когда оно будет появляться, его смысл всегда будет ясен для конкретной ситуации. Например, понятие левого регулярного представления и правого регулярного представления — двойственные конструкции.

12. Пусть А — непустое множество и для каждого элемента а А задано множество Ха. Тогда декартовым произведением множеств Ха называется функция f : А→ {Ха : а А}, такая, что для любого элемента а A, f(a)Ха. Декартово произведение обозначается как П{Ха : а А}, его можно представить как множество последовательностей длины А, причем для любой последовательности элемент с номером а принадлежит множеству Ха. Если для всех а А множество Ха=В, то справедливое соотношение

П {Ха:а А} = F (А, В) (см. 9).

Если для каждого аА множество Sa — полугруппа, то на множестве П {Sa : a А} можно определить структуру полугруппы, положив

(f • g)(а)=f(a)• g(а). Эта полугруппа называется прямым произведением полугрупп Sa. В частности, если S — полугруппа, то множество F (A, S) будет полугруппой, для которой закон композиции определяется операцией умножения в полугруппах Sa = S для всех а А. Этот закон композиции часто называется поточечным умножением или покоординатным умножением.

Для каждого элемента а А определено отображение