Алгебраические структуры

План
Частково-впорядковані множини
Напівгрупи та напіврешітки
Решітки
Групи
Групи і гомоморфізми

Умовні позначення
!
- визначення
- приклад
- примітка
- важливо!
☑
- теорема

Частково-впорядковані множини
Відношення R на множині А є відношенням порядку, якщо
воно рефлексивне, антисиметричне і транзитивне. Множину A в цьому випадку називають частково впорядкованою множиною або ЧВ-множиною з порядком R.
Для підмножини B ЧВ-множини A елемент а з A називають верхньою гранню B, якщо а ≥ b ∀ b з В. Елемент а називають найменшою верхньою гранню (нвг) підмножини B, якщо: (а) а – верхня грань B; (b) якщо будь-який інший елемент
а' множини A є верхньою гранню B, то а ≤ а'.
Найменшу верхню грань всієї ЧВ-множини A (якщо вона існує) називають найбільшим елементом А.
Найбільшу нижню грань всієї ЧВ-множини A (якщо вона існує) називають найменшим елементом A.
Лекція 1. Алгебраїчні структури. Слайд 4 з 25

Елемент а підмножини B ЧВ-множини A називають максимальним елементом B, якщо для будь-якого елемента b ∈ B з того, що b ≥ а, випливає b = а. Тобто, в множині B немає елемента, який був би "більшим", ніж а.
Елемент а підмножини B ЧВ-множини A називають мінімальним елементом В, якщо для для будь-якого b ∈ B з того, що b ≤ а, випливає b = а. Тобто, в B немає елемента, який був би "менший", ніж а. Звичайно терміни "мінімальний" і "максимальний" елемент відносять до всієї множини.
Лекція 1. Алгебраїчні структури. Слайд 5 з 25

Нехай C = {1, 2, 3} і X - булеан множини C: X = P(C) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Визначимо відношення ≤ на множині X : T ≤ V, якщо T ⊆ V.
За означенням, {1, 2} є найбільша нижня грань для {∅, {1}, {2}}, а також для {∅, {1}, {2}, {1, 2}}. Множина {1, 2, 3} - найменша верхня грань для X. Елемент ∅ є найбільшою нижньою гранню для всіх трьох множин.
Лекція 1. Алгебраїчні структури. Слайд 6 з 25

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

Напівгрупи та напіврешітки
Напівгрупа – це множина S з однією асоціативною бінарною операцією: a * (b * c) = (a * b) * c.
Якщо для всіх а і b з S виконується а * b = b * а, то множину S з оператором * називають абелевою (комутативною) напівгрупою.
Якщо в (S, *) існує елемент І такий, що I * а = а* I = а для всіх а з А, то таке І називають одиницею напівгрупи (S, *), а (S, *) - називають напівгрупою з одиницею, або моноїдом.
Якщо (S, *) - напівгрупа, і S′ ⊆ S, то S′ називають піднапівгрупою напівгрупи S, якщо * - бінарна операція на S′. Це еквівалентно наступному: (S′, *) – піднапівгрупа напівгрупи (S, *), якщо S′ ⊆ S, і для кожних а, b ∈ S′ маємо а * b ∈ S′.
Лекція 1. Алгебраїчні структури. Слайд 8 з 25

(S, ⋅) - напівгрупа матриць n × n раціональних чисел з операцією ⋅ матриць, (S, ·) - напівгрупа матриць n × n цілих чисел. Тоді (S, ⋅) - піднапівгрупа напівгрупи (S, ⋅).
Sn0 ={x : x ∈ Z і x ≥ n} ∪ {0} для n ∈ N. Напівгрупа Sn0 - комутативний моноїд з операцією + цілих чисел і нейтральним 0. Sn1 = {x : x ∈ Z і x ≥ n} ∪ {1}. Sn1 - комутативний моноїд з операцією ⋅ цілих чисел і одиницею. Якщо m ≥ n, то Sm0 - піднапівгрупа напівгрупи Sn0 і Sm1 - піднапівгрупа напівгрупи Sn1.
Лекція 1. Алгебраїчні структури. Слайд 9 з 25

Напівгрупу
називають циклічною напівгрупою, породженою елементом а.
ТЕОРЕМА 16.1. Нехай (S, ⋅) - напівгрупа і a1, a2, ..., ak ∈ S. Нехай А = {a1, a2, ..., ak} і А* =
- множина всіх скінченних добутків елементів a1, a2, ..., ak. Тоді А* - напівгрупа і А* - найменша піднапівгрупа напівгрупи S, що містить А.
Напівгрупу А* називають напівгрупою, породженою множиною А. Якщо для кожної власної підмножини B множини А маємо В* ≠ А*, то А називається мінімальною породжуючою множиною для напівгрупи А*.
Лекція 1. Алгебраїчні структури. Слайд 10 з 25
☑

Нехай (S, ⋅) і (T, ◦) - напівгрупи і f : S → T -
така функція, що f(s · s') = f(s) ◦ f(s'). Функцію f називають гомоморфізмом з S в Т.
ТЕОРЕМА 16.2. Нехай (S, ⋅) і (T, ◦) - напівгрупи і f : S → T – гомоморфізм з S в Т. Якщо S' - піднапівгрупа напівгрупи S, то f(S' ) піднапівгрупа напівгрупи Т.
ТЕОРЕМА 16.3. Нехай (S, ⋅) і (T, ◦) – напівгрупи і f : S → T – гомоморфізм з S в Т. Якщо Т' - піднапівгрупа напівгрупи T, то f-1(Т') – піднапівгрупа напівгрупи S.
Лекція 1. Алгебраїчні структури. Слайд 11 з 25
☑
☑

Нехай (S, ⋅) - напівгрупа і R - відношення еквівалентності на S. R має властивість: якщо s1Rs2 і s3Rs4, то s1s3Rs2s4 ∀ s1, s2, s3, s4 ∈ S. Тоді R називають відношенням конгруентності.
ТЕОРЕМА 16.4. Нехай (S, ⋅) і (T, ◦) - напівгрупи і f : S → T – гомоморфізм з S у Т. Відношення R на множині S таке: sRs', якщо f(s) = f(s'). Тоді відношення R - відношення конгруентності.
Комутативну напівгрупу (S, *) називають напіврешіткою, якщо а * а = а для всіх а ∈ S.
ТЕОРЕМА 16.5. Нехай S - напіврешітка. Відношення ≤ на S визначимо так: а ≤ b, якщо а * b = b для а, b ∈ S. Тоді (S, ≤) - це ЧУ-множина, і а * b – найменша верхня грань для а і b. Отже, (S, *) – верхня напіврешітка. Аналогічно, (S, *) можна розглядати як нижню напіврешітку.
Лекція 1. Алгебраїчні структури. Слайд 12 з 25
☑
☑

Решітки
Решітка – це множина М з двома бінарними операціями ∧ і ∨, такими, що виконуються наступні умови (аксіоми решітки)
а) Комутативність
а ∧ b = b ∧ a;
а ∨ b = b ∨ a.
б) Асоціативність
(а ∧ b) ∧ с = а ∧ (b ∧ с);
(a ∨ b) ∨ c = a ∨ (b ∨ c).
в) Поглинання
а ∧ (а ∨ b) = а;
а ∨ (а ∧ b) = а.
Лекція 1. Алгебраїчні структури. Слайд 13 з 25

Непорожню підмножину S' решітки (S, ∨, ∧) називають підрешіткою решітки S, якщо для всіх а, b ∈ S' а ∧ b ∈ S' і а ∨ b ∈ S'.
Решітку (S, ∨, ∧) називають обмеженою, якщо множина S, як ЧВ-множина, має найменшу верхню грань (позначають 1) і найбільшу нижню грань (позначають 0). Еквівалентно, решітка обмежена, якщо існують елементи 0, 1 ∈ S такі, що 0 ∧ а = 0 і 1 ∨ а = 1 для всіх а ∈ S.
ТЕОРЕМА 16.6. B обмежених решітках 1 ∧ а = 1 і 0 ∨ а = а для всіх а з решітки.
Решітку (S, ∨, ∧) називають дистрибутивною, якщо для всіх а, b, с ∈ S маємо а ∧ (b ∨ с) = (а ∧ b) ∨ (а ∧ с); а ∨ (b ∧ с) = (а ∨ b) ∧ (а ∨ с).
Лекція 1. Алгебраїчні структури. Слайд 14 з 25
☑

Групи
Групою є множина G разом з бінарною операцією ◦ на G × G, що має наступні властивості:
1. асоціативність: а ◦ (b ◦ с) = (а ◦ b) ◦ c ∀ а, b і c ∈ G.
2. існування одиниці: в G існує такий елемент 1, ∀ а ∈ G а ◦ 1 = 1 ◦ а = а.
3. існування симетричного (оберненого, протилежного) елементу: ∀ а ∈ G ∃ a-1 ∈ G, такий, що а ◦ a-1 = a-1 ◦ а = 1.
Група – це моноїд, в якому ∀ а ∃ a-1 що а * a-1 = a-1 * а = 1.
Лекція 1. Алгебраїчні структури. Слайд 15 з 25

Якщо група G має властивість а ◦ b = b ◦ а ∀ а, b з G, то її називають комутативною (абелевою) групою.
Якщо G - група з n елементами, то n називається порядком групи G.
Будь-яка група є напівгрупою. Обернене не завжди вірно.
ТЕОРЕМА 16.7. Одиниця групи G єдина.
ТЕОРЕМА 16.8. В кожній групі обернений елемент для кожного елементу єдиний.
TEOPEMA 16.9. Для кожного елемента а групи G (a-1)-1 = a.
TEOPEMA 16.10. Для елементів а і b групи G маємо
(a ◦ b)-1 = b-1 ◦ a-1.
ТЕОРЕМА 16.11. Нехай G - група і а - елемент групи G.
а) an ◦ a-n = 1 ∀ n ∈ N.
б) а(m+n) = am ◦ an для всіх цілих чисел n і m.
в) (am)n = amn для всіх цілих чисел m і n.
г) (a-n)-1 = аn для всіх цілих чисел n.
Лекція 1. Алгебраїчні структури. Слайд 16 з 25
☑

ТЕОРЕМА 16.12. Якщо а - елемент групи (G, ◦) і а ◦ а = а, тo а = 1, одиниці групи G.
ЛЕМА. Якщо G - скінченна група і а - елемент G, то as = 1 для деякого натурального числа s.
ТЕОРЕМА 16.13. Нехай G - група і а - елемент G такий, що as =1 для деякого s. Якщо p - найменше додатне ціле число таке, що ар = 1, то p | s. Ціле число p називають порядком а.
Підмножина H групи G є підгрупою G, якщо H з тією ж самою операцією, що і G, також є групою.
Нехай (R, +) - група дійсних чисел з операцією +. Тоді група (Q, +) - раціональні числа з +, є підгрупою групи (R, +).
Нехай (R+, ·) - група додатніх дійсних чисел з множенням. Група (Q+, ·) додатніх раціональних чисел з множенням є підгрупою групи (R+, ·).
Лекція 1. Алгебраїчні структури. Слайд 17 з 25
☑
☑

TEOPEMA 16.14. Непорожня підмножина H групи (G, ⋅) буде підгрупою тоді і лише тоді, коли для всіх h1, h2 ∈ H h1 ⋅ h2-1 ∈ H.
TEOPEMA 16.15. Якщо g - елемент групи G | gn = 1 для деякого n, і p - найменше натуральне число | gp = 1, тоді множина {g, g2,..., gp} є підгрупою групи G.
Множину {g, g2,..., gp} називають циклічною групою, породженою g. Вона позначається через
.
TEOPEMA 16.16. Нехай (G, ⋅) – група і а1, а2, а3,…, аk ∈ G. Нехай А = {а1, а2, а3,…, аk} і А* = <а1, а2, а3,…, аk> - множина всіх скінченних добутків елементів а1, а2, а3,…, аk і обернених до них. Тоді А* - група. Більш того, А* - найменша підгрупа групи G, що містить А.
Лекція 1. Алгебраїчні структури. Слайд 18 з 25
☑
☑
☑

Підгрупу А* називають групою, породженою множиною А. Якщо для кожної власної підмножини B множини А маємо В* ≠ А*, тоді А називають породжуючою множиною для А*. Якщо множина А породжує групу G і жодна власна підмножина множини А не породжує G, тоді А називається мінімальною породжуючою множиною для групи G.
Для підгрупи H групи G і довільного а з G а ◦ H = {x: x = а ◦ h для деякого h з H} називають лівим суміжним класом підгрупи H групи G.
ЛЕМА. Для фіксованої підгрупи H групи G ліві суміжні класи підгрупи H групи G утворюють розбиття групи G.
Лекція 1. Алгебраїчні структури. Слайд 19 з 25

ЛЕМА. Якщо G - скінченна група і H - підгрупа групи G, то всі ліві суміжні класи підгрупи H групи G містять однакову кількість елементів, а саме, кількість елементів, що містяться в підгрупі H.
ТЕОРЕМА. (Лагранж) Якщо G - скінченна група і H - підгрупа групи G, то порядок H ділить порядок G.
ТЕОРЕМА 16.17. Якщо G - група порядку n і а ∈ G, то gn = 1.
Лекція 1. Алгебраїчні структури. Слайд 20 з 25
☑
☑

Групи і гомоморфізми
Нехай (G, •) і (H, *) - групи, де • і * - операції на G і H відповідно.
Нехай f : G→H - функція. Функція f називається гомоморфізмом, якщо f(g•g')= f(g)*f(g') для всіх g і g' з G. Гомоморфізм f називається мономорфізмом, якщо функція f - ін'єкція, епіморфізмом, якщо функція f – сюр’єкція, і ізоморфізмом, якщо функція f - бієкція.
ТЕОРЕМА 16.18 Нехай f : G → H - гомоморфізм з групи G в групу H і 1 - одиниця групи G. Тоді f(1) - одиниця групи H.
ТЕОРЕМА 16.19. Нехай f : G → H - гомоморфізм з групи G в групу H і g' - елемент, обернений елементу g з G. Тоді f(g') є елемент, обернений елементу f(g) з H.
ТЕОРЕМА 16.20. Якщо f : G → H - гомоморфізм з групи G в групу H і K - підгрупа групи H, то f-1(K) - підгрупа групи G.
Лекція 1. Алгебраїчні структури. Слайд 21 з 25
☑
☑
☑

ТЕОРЕМА 16.21. Якщо f : G → H - гомоморфізм з групи G в групу H і K - підгрупа G, то f(K) - підгрупа групи H.
TEOPEMA 16.22. Якщо H, J і K - підмножини групи (G, ◦), то (H◦ J) ◦ K = H ◦ (J ◦ K).
Якщо H - підгрупа групи (G, ◦), що має властивість gHg-1 = H для всіх g ∈ G, то така група H називається нормальною підгрупою.
Нехай f : G → H - гомоморфізм з групи G в групу H. Ядром гомоморфізму f називається множина {x : x ∈ G і f (x) = 1} = f -1({1}), де 1 - одиниця групи H.
ТЕОРЕМА 16.23. Ядро гомоморфізму f : G → H є нормальна підгрупа групи G.
Лекція 1. Алгебраїчні структури. Слайд 22 з 25
☑
☑
☑

ТЕОРЕМА 16.24. Підгрупа H групи (G, ◦) є нормальною підгрупою тоді і лише тоді, коли gH = Hg для всіх g ∈ G.
ТЕОРЕМА 16.25. Якщо H - підгрупа групи (G, ◦), то H ◦ H = H.
ТЕОРЕМА 16.26. Якщо H - нормальна підгрупа групи (G, ◦), то abH = (aH)(bH) для всіх а, b ∈ G.
НАСЛІДОК. Якщо Н - нормальна підгрупа групи (G, ◦), то суміжні класи підгрупи Н в групі G породжують групу відносно операції (аН)(bН) = аbН. Ця група називається фактор-групою і позначається G/H.
НАСЛІДОК. Якщо f : G → G/H визначити
співвідношенням f(a) = aH, то f - гомоморфізм.
Лекція 1. Алгебраїчні структури. Слайд 23 з 25
☑
☑
☑

Література
Андерсон Д.А. Дискретная математика и комбинаторика: Пер. с англ.. – М.: Изд. дом «Вильямс», 2003. – 960 с
Грэхем Р., Кнут Д., Паташник О., Конкретная математика. Основание информатики: Пер. с англ. – М.: Мир, 1998. – 703 с.
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – Спб.: Питер, 2008. – 384 с.
Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов. 3-е изд. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с.