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

Говорят, что множество X порождает полугруппу S, если <Х>=S. Очевидно, справедливо соотношение <S> = S. Пусть аS. Тогда полугруппа <а> называется циклической подполугруппой полугруппы S, порожденной элементом а, здесь <а>=<{а}>. S будет циклической полугруппой, если S = <а> для некоторого элемента а S.

Говорят, что S — периодическая полугруппа, если для любого элемента а S подполугруппа <а> конечная.

3. Определение. Пусть S1 и S2 — полугруппы. Тогда отображение

φ: S1→S2 представляет собой гомоморфизм, если для любых элементов

s1, s2 S1 выполнено соотношение φ(s1s2) = φ (s1)φ(s2). Если X S1, то φ (X) обозначает множество {у S2: у = φ(s) для некоторого элемента s X}. Если φ(S1)=S2, то гомоморфизм φ будет эпиморфизмом, который записывается в виде φ: S1→→S2. Полугруппа S2 называется гомоморфным образом полугруппы S1. Если для любых элементов s, tS1, таких, что s≠t, справедливо неравенство φ(s)≠φ(t) то φ — взаимнооднозначный (обозначается 1:1) гомоморфизм, или мономорфизм. Изоморфизмом называется взаимнооднозначный эпиморфизм. Полугруппа S1 изоморфна полугруппе S 2, S1 S2, если существует изоморфизм φ: S1→→S2. Если φ : S1 →→S2 — изоморфизм, можно определить обратное φ-1 : S 2→→S1 для отображения φ, полагая, что φ-1(s) - единственный элемент из S1, для которого φ [φ -1(s)] = s. Очевидно, что отображение φ-1:S2→→S1 представляет собой изоморфизм. Из этого легко вывести: ( ) есть отношение эквивалентности на классе полугрупп.

3.2. Примеры (определения, обозначения, дополнения).

Далее приведены примеры полугрупп. Они помогут читателю овладеть введенными понятиями и облегчат изучение последующего материала.

1. Пусть А — непустое множество. Тогда Аr (соответственно Аl) обозначает полугруппу (А, • ), для которой а1• а2 = а2 (соответственно а1• а2=a1), где а1, а2 - произвольные элементы множества А. Когда |А|>1, Аr и Аl являются полугруппами и не являются группами. Следовательно, Аr (соответственно Аl) есть множество А, которое мы превратили в полугруппу, потребовав, чтобы каждый элемент из А действовал как правый (соответственно, левый) нуль.

2. Пусть X - некоторое множество, а 2х обозначает множество всех подмножеств множества X. Тогда (2х, ) есть абелева полугруппа. Полугруппа (2х, ) изоморфна полугруппе (2х, ), изоморфизм задается отображением

А→Х — А = {х X : х А}.

3. Пусть S— полугруппа, А и В - подмножества в S. Положим

А• В={ab : а A, b В} (сокращенно это записывается как АВ). Тогда отображение s→{s} есть мономорфизм полугруппы S в (2s, •). Условимся, что А • = • А = , где — пустое множество.

4. Пусть X — множество. Отношением R на X называется любое подмножество R X×X. Будем писать x1Rx2 или х1≡х2 (mod R) тогда и только тогда, когда (х1, х2) R. Тогда (2Х×Х, • ) есть полугруппа всех отношений на множестве X, закон композиции для нее определяется следующим образом:

R1 • R2 = {(х, у): для некоторого z X, (х, z) R1, (z, у) R2}.

Если R — отношение, то по определению R -1={(у, х):(х, у) R}. Тогда

(R • S)-1=S-1R-1 для любых отношений S и R на множестве X. Тождественное отношение на множестве X есть ∆(X)={(х, х) : х X}. Отношение R называется отношением эквивалентности тогда и только тогда, когда

1) ∆(X) R (R рефлексивно);

2) R = R-1 (R симметрично);

3) R • R R (R транзитивно).

Включение отношений (как множеств) определяет частичную упорядоченность на множестве всех отношений на X. Если ограничиться рассмотрением только отношений эквивалентности, то эта частичная упорядоченность сведется к структуре. [Структура есть частично упорядоченное множество, для любых двух элементов которого существует точная нижняя (LUB) и точная верхняя грань (GLB)]. Если R1 и R2 — отношения эквивалентности, то GLB(R1, R2)=R1R2 и LUB(R1, R2)={(R1R2)п:1≤п≤∞}, т. е. LUB (R1, R2) есть транзитивное замыкание множества R1 R2. Следовательно, х эквивалентен у в LUB (R1, R2) тогда и только тогда, когда существует последовательность элементов х=х0, х1,х2,...,хп=у, таких, что х1R1хі+1 или х1R2хі+1 при i = 0, 1, ..., п— 1. Если R1 и R2 — отношение эквивалентности, для которых R1 • R2 = R2 • R1, то легко видеть, что R1 • R2 — отношение эквивалентности и, следовательно, R1• R2 = LUB (R1, R2).

5. Пусть S — полугруппа. Отношение эквивалентности ≡ на S называется конгруэнтностью, если для любых элементов s1, s2 S,

таких, что s1≡s2, и любого элемента s S справедливые соотношения ss1≡ss2 и s1s≡s2s. Отношение ≡ называется левой или правой конгруэнтностью, если справедливо первое или второе из предыдущих соотношений. Если ≡ есть конгруэнтность на S, обозначим через [s] класс элементов, эквивалентных s S. Пусть S/≡ представляет собой множество таких классов эквивалентности, а отображение η≡: S→→S/≡ определяется как η≡(s)=[s]. Тогда умножение [s]•[t]=[st] корректно, множество S/≡ с таким умножением — полугруппа, а отображение η≡ — эпиморфизм.

Наоборот, если φ : S→→ S1 есть эпиморфизм, то с его помощью можно определить конгруэнтность на S, а именно s1(mod φ)s2 тогда и только тогда, когда φ(s1) = φ (s2). Следовательно, определено отображение φ*: S/(mod φ)→S1, φ*([s])=φ(s), которое будет изоморфизмом, и φ = φ*η(mod φ).

6. Пусть А — непустое множество. Тогда свободной некоммутативной полугруппой без единицы ∑А, порожденной А, называется множество всех конечных непустых упорядоченных последовательностей элементов из А с полугрупповой операцией, которая задается сшиванием последовательностей, т. е.,

(a1, ..., ап) • (b1..., bт) = (а1, ..., ап, b1, ..., bт).

∑А есть бесконечная полугруппа.

∑А называется свободной полугруппой на множестве А, поскольку любое отображение φ множества А в полугруппу S может быть единственным способом продолжено до гомоморфизма φг полугруппы ∑А в S; φг определяется по формуле φг (а1 ..., ап) = φ (а1) ... φ (ап). В частности, если А — множество, которое порождает полугруппу S, а φ — тождественное отображение, тo φ г: ∑А → S есть эпиморфизм. Следовательно, каждая полугруппа есть гомоморфным образом свободной полугруппы.