Напівгрупи

Означення 11. Алгебра G=(A,W) називається напівгрупою, якщо W складається з однієї бінарної асоціативної операції. Бінарну операцію напівгрупи часто позначають символом * й називають множенням. Бінарна операція * на множині А називається асоціативною, якщо для будь-яких x,y,z з множини А виконується умова x*(y*z)=(x*y)*z.

Розглянемо приклади напівгруп. Алгебра (N,+) має сигнатуру, що складається з однієї бінарної операції (+); для будь-яких невід’ємних цілих чисел x,y,z виконуєтьс, як відомо, умова x+(y+z)=(x+y)+z, тобто операція + асоціативна. Таким чином, алгебра (N,+) є напівгрупою. Напівгрупами є також алгебри (N,´), (Z,+), (Z,´), (R,+), (R,´).

Алгебра (Z,-) не є напівгрупою, оскільки операція віднімання чисел (-) не асоціативна. Дійсно, x-(y-z)=x-y+z, (x-y)-z=x-y-z; оскільки не для усіх цілих x, y, z x-y+z=x-y-z, то умова асоціативності операції віднімання (тобто умова x-(y-z)=(x-y)-z) не виконується.

Розглянемо поняття напівгрупи слів у скінченному алфавіті.

Означення 12. Алфавітом називається множина символів. Скінченним алфавітом називається скінченна множина символів.

Означення 13. Словом у алфавіті Х називається скінченна послідовність символів алфавіту Х, записана без проміжків та розділових знаків між цими символами. Порожнімсловом будемо називати послідовність, що не містить символів. Порожнє слово позначається e. Позначимо F(X)={p| p – слово у алфавіті X або e}. Кількість входжень символів у слово р називається довжиною слова р; порожнє слово має довжину 0.

Наприклад, словами у алфавіті X={a,b,c} є послідовності аассс, са, b, сbb. Довжина слова аассс дорівнює п’яти (адже у це слово входять п’ять символів: двічі символ “a” та тричі символ “c”), довжина слова са дорівнює 2, слова b – 1, слова cbb – 3. Послідовність асе не є словом у даному алфавіті Х, бо вона містить символ “е”, що не належить алфавіту Х.

Визначимо на множині F(X) бінарну операцію злиття (конкатенації) слів (позначимо її conc). Нехай p,qÎF(X), p=x₁…x_n, q=y₁…y_m, n,mÎN (вважаємо, що коли n (m) дорівнює нулю, то p (q) – порожнє слово). Покладемо conc(p,q)=x₁…x_ny₁…y_m. Зрозуміло, що при р=e conc(p,q)=q, при q=e conc(p,q)=р, а при р=q=e conc(p,q)=e.

Покажемо, що операція conc асоціативна. Нехай p,q,rÎF(X) й p=x₁,…,x_n, q=y₁,…,y_m, r=z₁,…,z_k, n,m,kÎN⁺. Перевіримо, чи виконується умова асоціативності для операції conc: conc(p,conc(q,r))=conc(conc(p,q),r). Маємо:

conc(p,conc(q,r))=conc(x₁,…,x_n,conc(y₁,…,y_m,z₁,…,z_k))=conc(x₁,…,x_n,y₁,…,y_mz₁,…,z_k)= =x₁,…,x_ny₁,…,y_mz₁,…,z_k;

conc(conc(p,q),r)=conc(conc(x₁,…,x_n,y₁,…,y_m),z₁,…,z_k)=conc(x₁,…,x_ny₁,…,y_m,z₁,…,z_k)= =x₁,…,x_ny₁,…,y_mz₁,…,z_k;

отже, conc(p,conc(q,r))=conc(conc(p,q),r), тобто операція conc асоціативна. Зрозуміло, що коли принаймні одне зі слів p, q, r порожнє, умова conc(p,conc(q,r))=conc(conc(p,q),r) виконується.

Напівгрупою слів у алфавіті Х назвемо алгебру (F(X), conc).

Означення 14. Напівгрупа (А,*) називається комутативною, якщо операція * комутативна, тобто для будь-яких х та у з множини А виконується х*у=у*х.

Наприклад, напівгрупи (N,+), (N,´), (Z,+), (Z,´), (R,+), (R,´) комутативні, адже операції додавання та множення чисел, як відомо, комутативні. Напівгрупа слів у алфавіті Х (тобто алгебра (F(X), conc)) не є комутативною, адже слова conc(p,q) та conc(q,p) не завжди однакові; нехай, наприклад, Х={a,b,c}, p=ab, q=cb, тоді conc(p,q)=abcb, а conc(q,p)=cbab; бачимо, що conc(p,q)¹conc(q,p).

Означення 15. Алгебра (А,*) називається напівгрупою з одиницею, або моноїдом, якщо (А,*) – напівгрупа й існує такий елемент е множини А, що для будь-якого х з А х*е=е*х=х. Елемент е називається одиничним (нейтральним, одиницею). Алгебра (А,*) називається комутативною напівгрупою з одиницею (комутативним моноїдом), якщо вона є напівгрупою з одиницею й операція * комутативна.

Наприклад, алгебра (N,+) є моноїдом, адже вона є напівгрупою, й у множині N існує таке число (позначимо його е), що для будь-якого х з N виконується умова х+е=е+х=х. Дійсно, рівності х+е=е+х=х мають розв’язок відносно е: е=0. Таким чином, напівгрупа (N,+) має одиничний елемент: це число 0. Отже, алгебра (N,+) є напівгрупою з одиницею, або моноїдом. Алгебри (Z,+), (R,+), (R,´), (N,´), (Z,´) також є моноїдами. Одиничним елементом моноїдів (Z,+), (R,+) є число 0. Одиничним елементом моноїдів (R,´), (N,´), (Z,´) є число 1. Оскільки операції додавання та множення чисел комутативні, то алгебри (N,+), (Z,+), (R,+), (R,´), (N,´), (Z,´) є комутативними моноїдами.

Напівгрупа слів у алфавіті Х є моноїдом; одиничним елементом є порожнє слово, адже для будь-якого слова р з множини F(X) маємо: conc(p,e)=p=conc(e,p).

Твердження 2. Нехай G=(A,*) – напівгрупа з одиницею, е – одиничний елемент. Тоді е єдиний.

Доведення (від супротивного). Припустимо, що у множині А існує принаймні ще один елемент (позначимо його е¢), що відмінний від е, й такий, що для будь-якого х із А виконується умова: х*е¢=е¢*х=х. Оскільки еÎА, то й для е дана умова також виконується, тобто е*е¢=е¢*е=е. Оскільки е – одиничний елемент напівгрупи G, то для будь-якого х з А маємо: х*е=е*х=х. Дана умова виконується й для х=е¢, адже е¢ÎА, а тому е¢*е=е*е¢=е¢. Таким чином, е=е¢, що суперечить припущенню про те, що елемент е¢ відмінний від е. Отже, одиничний елемент напівгрупи з одиницею єдиний.

Контрольні питання

1. Що таке асоціативна операція?

2. Що таке комутативна операція?

3. Що таке напівгрупа?

4. Що таке комутативна напівгрупа?

5. Що таке напівгрупа з одиницею?

6. Що таке моноїд?

7. Що таке напівгрупа слів у алфавіті Х?

8. Що таке одиничний елемент напівгрупи?

9. Що таке комутативна напівгрупа з одиницею?

Групи

Означення 16. Алгебра (А,*) називається групою, якщо вона є напівгрупою з одиницею (е) й для кожного елемента х множини А існує такий елемент х^-1 множини А, що х*х^-1=х^-1*х=е. Елемент х^-1 називається оберненим до х. Група (А,*) називається комутативною, якщо операція * комутативна.

Розглянемо, наприклад, алгебру (Z,+). Вона є напівгрупою з одиницею (одиничним елементом є число 0). Перевіримо, чи існує для кожного цілого числа x обернений елемент, тобто таке ціле число х^-1, що x+x^-1=x^-1+x=0. Знаходимo розв’язок рівнянь: х^-1=-х. Оскільки хÎZ, -хÎZ. Отже, для кожного цілого числа х існує обернене до нього, а саме: число -х. Таким чином, (Z,+) є групою. Оскільки операція + комутативна, алгебра (Z,+) є комутативною групою.

Розглянемо приклад некомутативної групи. Нехай А – множина усіх взаємно однозначних відображень множини N₃ у множину N₃. Побудуємо ці відображення: f₁={<1,1>,<2,2>,<3,3>}, f₂={<1,1>,<2,3>,<3,2>}, f₃={<1,2>,<2,1>,<3,3>}, f₄={<1,2>,<2,3>,<3,1>}, f₅={<1,3>,<2,1>,<3,2>}, f₆={<1,3>,<2,2>,<3,1>}.

Множина А замкнута відносно операції композиції. Для перевірки обчислимо вирази виду f_i*f_j для усіх i та j (1£i£6, 1£j£6). Результати обчислень заносимо у таблицю.

Бачимо, що f_i*f_jÎА, 1£i£6, 1£j£6, отже, множина А замкнута відносно операції *. Таким чином, (А,*) – алгебра. Оскільки операція композиції відображень асоціативна, алгебра (А,*) є напівгрупою. Відображення f₁ є одиницею цієї напівгрупи, адже f₁ – тотожнє відображення, а тоді f₁*f_i=f_i*f₁=f_i, 1£i£6. Таким чином, алгебра (А,*) є напівгрупою з одиницею. За таблицею знайдемо для кожного відображення обернений елемент. Маємо: f₁^-1=f₁, f₂^-1=f₂, f₃^-1=f₃, f₄^-1=f₅, f₅^-1=f₄, f₆^-1=f₆. Отже, алгебра (А,*) є групою. Ця група не комутативна, адже не для усіх відображень f_i та f_j виконується f_i*f_j=f_j*f_i. Дійсно: f₂*f₅¹f₅*f₂, адже f₂*f₅=f₆, f₅*f₂=f₃, а f₆¹f₃.

Твердження 3. Нехай (A,*) – група, хÎА. Тоді елемент, обернений до х, єдиний.

Доведення. Припустимо, що існує принаймні два різні елементи (y₁ та y₂), обернені до х. Оскільки y₁ обернений до х, маємо: х*y₁=y₁*х=е, а оскільки y₂ обернений до х, то х*y₂=y₂*х=е. Маємо: y₁=y₁*е=y₁*(х*y₂)=(y₁*х)*y₂=е*y₂=y₂. Отже, y₁=y₂, що суперечить припущенню про те, що y₁ та y₂ різні. Таким чином, для кожного елемента х з множини А елемент, обернений до х, єдиний.

Теорема 1. Алгебра G є групою тоді й тільки тоді, коли сигнатура алгебри G містить одну бінарну операцію (*), одну 0-арну операцію (е), одну унарну операцію (^-1) й для будь-яких x, y, z з носія алгебри G виконуються умови:

x*(y*z)=(x*y)*z, x*e=e*x=x, x*x^-1=x^-1*x=e.

Доведення випливає з тверджень 2 та 3.

Контрольні питання

1. Що таке група?

2. Що таке комутативна група?