Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементи абстрактної алгебри
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Елементи абстрактної алгебри
Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № 6 від 21 січня 2003 року
Львів – 2003
Алгебри та операції : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 15 с.
Укладачі: Р. Попович, к.т.н., доцент
І. Мороз, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Вступ
Основу сучасних швидких та якісних технологій обробки інформації становлять комп’ютери – від персональних до супер-ЕОМ. Подання інформації для ЕОМ дискретне, і її обробка складається з послідовностей елементарних перетворень тих чи інших інформаційних одиниць (слів, літер, цифр тощо). Тобто, фундаментальною ідеєю щодо відображення реального світу в комп’ютері є ідея дискретизації об’єктів. Для ефективної застосування комп’ютерів необхідно навчитися будувати моделі реальних об’єктів та процесів їх перетворення. Досить часто такими моделями можуть бути конструкції дискретної математики, зокрема, такі, як алгебраїчні структури, що розглядаються в даних методичних вказівках.
Під абстрактною оболонкою більшості аксіоматичних теорій алгебри ховаються цілком конкретні задачі прикладного характеру. Складна взаємодія теоретичних і прикладних аспектів теорії, яка притаманна всій математиці, в алгебрі проявляється дуже виразно.
Наведемо кілька прикладів практичного використання алгебраїчних структур – множин з алгебраїчними операціями.
Однією з галузей застосування є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Це досягається шляхом введення при кодуванні надлишковості, яка дозволяє так вибрати множини символів для передачі, щоб вони задовольняли додатковим умовам, перевірка яких після прийому дає можливість виявити й виправити помилки. Найкращих результатів досягнуто, коли символи, що передаються, розглядаються як елементи певних алгебраїчних структур, зокрема скінченних полів (полів Галуа). При цьому простими стають процедури кодування й декодування, зменшується ймовірність неправильного декодування даних (циклічні коди, коди Ріда-Соломона тощо).
Іншою галуззю застосування є криптографія: захист інформації шляхом її перетворення, що виключає прочитання цієї інформації сторонньою особою. Ще кілька десятиліть тому такий підхід стосувався в основному військових операцій або був пов’язаний з шпигунськими історіями, а не був предметом широкого використання. Причиною бурхливого розвитку криптографії є широке використання комп'ютерних мереж, зокрема глобальної мережі Internet, якими передаються великі обсяги інформації державного, військового, комерційного й приватного характеру, що не допускає можливості доступу до неї сторонніх осіб. При виконанні сучасних алгоритмів шифрування з таємним ключем використовуються алгебраїчні структури скінчених полів (наприклад, стандарт AES симетричного шифрування США). Широко вживаний алгоритм RSA шифрування з відкритим ключем (багато провідних світових ІТ-компаній вклали в його розвиток значні кошти, він стоїть в основі функціонування Internet - платежів eMoney) ґрунтується на алгебраїчному понятті фактор-кільця кільця цілих чисел за модулем великого натурального числа.
Алгебраїчні операції
Нехай Х – довільна множина. n-арною операцією на множині Х називається відображення f: Хn ( Х, яке кожному вектору (x1, x2, …, xn) ( Хn ставить у відповідність однозначно визначений елемент x ( Х. Це записується наступним чином: x = f(x1, x2, …, xn). Таких операцій на множині Х можна задати декілька. Множина операцій, заданих на Х, називається його сигнатурою й позначається F = (f1, f2, …).
Множину Х разом з її сигнатурою F називаємо алгеброю (алгебраїчною структурою) та позначаємо A(X, F). Множина Х – це так звана множина-носій алгебри.
Найбільш поширеними є бінарні операції, які далі будемо називати просто операціями. Бінарна операція (або закон композиції) на Х – це довільне (але фіксоване) відображення f:Х2 ( Х. Таким чином, будь-якій впорядкованій парі (x1, x2) елементів із Х ставиться у відповідність однозначно визначений елемент f(x1, x2) цієї ж множини Х. Часто бінарну операцію позначають якимось спеціальним символом: T, *, ◦, + та замість f(x1, x2) = z записують x T y = z. Коли зрозуміло про що йдеться, символ операції може пропускатися.
Операція Т називається асоціативною, якщо для будь-яких x, y, z ( Х виконується умова (x T y) T z = x T (y T z).
Операція Т називається комутативною, якщо для будь-яких x, y ( Х виконується умова x T y = y T x.
Операція T1 називається дистрибутивною зліва відносно операції T2, якщо для будь-яких x, y, z ( Х виконується умова x T1 (y T2 z) = (x T1 y) T2 (x T1 z). Операція T1 називається дистрибутивною справа відносно операції T2, якщо для будь-яких x, y, z ( Х виконується умова (y T2 z) T1 x = (x T1 y) T2 (x T1 z). Операція T1 називається дистрибутивною відносно операції T2, якщо вона одночасно є дистрибутивною зліва й справа.
Елемент е є нейтральним (одиничним) зліва відносно операції Т, якщо для будь-якого x ( Х виконується e T x = x. Елемент е є нейтральним (одиничним) справа відносно операції Т, якщо для будь-якого x ( Х має місце рівність x T e = x. Елемент е є нейтральним (одиничним) відносно операції Т, якщо він є одночасно нейтральним зліва й справа, тобто для будь-якого x ( Х виконується x T e = e T x = x. Якщо нейтральний елемент існує, то він є єдиним: дійсно, коли e1 ( e2, то з e1 = e1 T e2 = e2 отримуємо суперечність.
Елемент x-1 називається оберненим зліва до елемента x ( Х відносно операції Т, коли x 1 T x = e. Елемент x-1 називається оберненим справа до елемента x ( Х відносно операції Т, коли x T x-1 = e. Елемент x-1 називається оберненим до елемента x ( Х відносно операції Т, коли він є одночасно оберненим зліва й справа, тобто x-1 T x = x T x-1 = e.
У випадку, коли алгебраїчна структура має скінченне число елементів, можна для кожної заданої на ній бінарної операції будувати так звану таблицю Келі, яка повністю описує дану операцію. Число рядків і стовпців таблиці рівне числу елементів алгебри, а на перетині рядка й стовпця записується результат виконання операції над відповідними цим рядку й стовпцю двома елементами. Побудова таблиці Келі для операції Т алгебри показана далі.
Т
a1
a2
…
an
a1
a1Ta1
a1Ta2
…
a1Tan
a2
a2Ta1
a2Ta2
…
a2Tan
…
…
…
…
…
an
anTa1
anTa2
…
anTan
Півгрупи
Множина Х із заданою на ній бінарною асоціативною операцією називається півгрупою. Півгрупу з нейтральним елементом прийнято називати моноїдом або просто півгрупою з одиницею.
Наведемо деякі приклади півгруп та півгруп з одиницею (моноїдів).
1) Нехай Ω - довільна множина й М(Ω) - множина всіх її перетворень (відображень Ω в себе). Задамо на М(Ω) операцію, яка є природною композицією відображень. Тоді М(Ω) стає некомутативною півгрупою з одиницею. Нейтральним елементом є тотожне відображення.
2) Множина матриць з дійсними значеннями Мn(R) розміру nxn відносно множення матриць є некомутативним моноїдом з нейтральним елементом – одиничною матрицею;
3) Нехай знову Ω - довільна множина й Р(Ω) - множина всіх підмножин цієї множини. Задаємо на Р(Ω) операцію перетину множин. Тоді Р(Ω) стає комутативним моноїдом. Нейтральним елементом тут є множина Ω.
4) Множина цілих чисел, які діляться на деяке фіксоване натуральне число n > 1, відносно операції множення утворює комутативну півгрупу без одиниці.
Групи
Півгрупа з одиницею, в якій для кожного елемента існує обернений, називається групою.
Іншими словами, групою називається множина G, на якій задана бінарна операція (символ операції пропускаємо) з наступними властивостями:
(G1) операція асоціативна: (x y) z = x (y z) для всіх x, y, z ( G;
(G2) G містить нейтральний (одиничний) елемент е: e x = x e = x для всіх x ( G;
(G3) для кожного елемента x ( G існує обернений x-1, x-1 x = x x-1 = e.
Група, в якій операція є комутативною, тобто для будь-яких x, y ( G виконується умова x y = y x, називається комутативною (абелевою) групою.
Група називається скінченною, якщо вона має скінченне число елементів. У протилежному випадку група називається нескінченною. Якщо група G скінченна, то число її елементів позначається | G | і називається порядком групи.
З аксіом групи (G1) - (G3) випливають наступні прості наслідки.
1. Закон скорочення: якщо x y = x z, то y = z (ліве скорочення);
якщо y x = z x, то y = z (праве скорочення);
2. Для кожного елемента групи обернений елемент єдиний;
3. Для кожної пари елементів a, b ( G рівняння a x = b та y a = b мають єдині розв’язки.
Наступні множини є групами відносно вказаних операцій:
1) множина Z цілих чисел відносно додавання;
2) множини Q \ {0}, R \ {0}, C \ {0} відносно множення. Позначатимемо ці групи відповідно Q*, R*, C*;
3) множини Q, R, C відносно додавання;
4) множина Cn коренів n-го степеня з одиниці відносно множення;
5) множина Aut(M) всіх бієктивних відображень множини M на себе. Якщо множина M є скінченною і має n елементів, то в цьому випадку вказані бієктивні відображення називаються підстановками n елементів, а множина Sn всіх підстановок утворює групу підстановок n елементів;
6) множина GLn(C) невироджених (тобто з відмінним від нуля визначником) комплексних матриць розміру nxn відносно множення матриць.
Зауважимо, що для кожного натурального числа n можна збудувати абелеву групу, яка має порядок n. Для цього треба розглянути фактор-множину Zn = {} класів еквівалентності цілих чисел, порівняних за модулем n. Перетворимо цю множину в групу, задавши на ній операцію додавання ( класів цілих чисел за модулем n. Щоб додати два класи і потрібно спочатку додати цілі числа r і s, а потім знайти остачу від ділення знайденої суми на число n. Клас знайденої остачі й буде результатом додавання класів і . Множина Zn разом із заданою на ній операцією додавання ( є абелевою групою, яка має порядок n.
Далі наведено таблицю Келі для операції додавання ( групи Z5:
(
Непорожня підмножина Н групи G називається підгрупою, якщо вона є групою відносно визначеної в групі G операції.
Зауважимо, що не всяка підмножина А групи G є підгрупою. Розглянемо, наприклад, підмножину A = {1, i} групи C4 = {1,-1, i, -i} з операцією множення комплексних чисел. Маємо i i = -1 . Як бачимо добуток двох елементів множини A не належить до цієї множини. Інакше кажучи, множина A не замкнена відносно визначеної в групі G операції. Якщо тепер розглядати множину A у відриві від групи, але з операцією, яка була визначена в групі, то не для всіх пар елементів цієї множини існує добуток.
Розглянемо ще підмножину B = {1, 2, …, 2n, …} групи Q*. Тут групова операція не виходить за межі множини B, але всі елементи, крім 1, не мають обернених у цій множині.
Переконаємося в справедливості такого критерію: підмножина Н групи G є підгрупою, тоді і лише тоді, коли:
а) для всіх h1, h2 ( H: h1 h2 ( H;
б) для всіх h ( H: h-1 ( H.
Дійсно, умова а) дозволяє ввести на множині Н ту саму операцію, яка була в групі. Зрозуміло, що ця операція є асоціативною. Умова б) гарантує існування обернених елементів в Н. Нарешті, з умов а) і б) випливає, що нейтральний елемент групи належить до Н: якщо h ( H, то h-1 ( H і тоді h h-1 = е ( H.
Далі наведено приклади підгруп:
1) кожна група G має дві так звані тривіальні підгрупи {е} і G;
2) в ланцюгу Z ( Q ( R ( C кожна попередня група є підгрупою наступної;
3) група Cn є підгрупою групи C*. Отже, нескінченна група може мати скінченні підгрупи;
4) множина всіх парних підстановок n елементів є підгрупою групи Sn. У той же час множина всіх непарних підстановок не утворює підгрупу;
5) множина всіх матриць, визначник яких рівний (1, є підгрупою групи GLn(C).
Елемент g групи G називається елементом скінченого порядку, якщо існує таке натуральне n, що gn = e. Найменше натуральне число з такою властивістю називається порядком елемента g і позначається через O(g).
Наприклад, у групі C*, O(i) = 4, O(cos(2( / 5)+ i sin(2( / 5)) = 5, елемент 2 має нескінченний порядок.
Група, в якій кожний елемент має скінчений порядок, називається періодичною.
Розглянемо всі степені (додатні та від’ємні) фіксованого елемента g групи G: e, g, g2, …, g-1, g-2, …. Зрозуміло, що ця множина є підгрупою групи G. Вона називається циклічною підгрупою, а елемент – її твірним елементом.
Далі наведено приклади циклічних підгруп:
1) множина C4 = {i, i2 = -1, i3 = -i, i4 = 1} – циклічна підгрупа групи C* з твірним елементом i;
2) нехай a ( S3 є підстановкою a = (1, 2). Тоді a2 = e, a3 = e, a4 = e і т.д., a-1 = a. Отже, множина {e, a} є циклічною підгрупою групи S3;
3) матриця породжує циклічну підгрупу групи GL2(C). Легко перевірити, що , m ( Z. Маємо приклад нескінченної циклічної підгрупи.
Група G називається циклічною, якщо знайдеться такий елемент g ( G, що породжена ним циклічна підгрупа співпадає з G.
Прикладами скінченних циклічних груп є групи Cn i Zn. Група Z відносно додавання є нескінченною циклічно групою з твірним елементом 1 (степенем елемента тут є його кратне). Зрозуміло, що будь-яка циклічна група є абелевою.
Нехай Н – підгрупа групи G, g – фіксований елемент у G. Лівим суміжним класом групи G за підгрупою Н (з представником g) називається множина елементів вигляду gh, де h пробігає всі елементи підгрупи Н; цю множину позначатимемо через gH. Аналогічно визначається правий суміжний клас групи G за підгрупою Н.
Далі наведено приклади суміжних класів:
1) нехай G = S3 , H – група парних підстановок. Позначимо елементи групи S3 наступним чином e = 1, a = (1, 2, 3), a2 = (1, 3, 2), b = (1, 2), c = (2, 3), d = (1, 3). H = {e, a, a2}.
Лівим суміжним класом в G є множина {be, ba, ba2}. Перемноживши підстановки, переконаємось, що ba = (2, 3) = c, ba2 = (1, 3) = d. Отже, bH = {b, c, d}. Можна перевірити, що bH = Hb. У даному прикладі лівий суміжний клас співпадає з відповідним правим суміжним класом. Проте таке співпадіння не завжди має місце, як показує наступний приклад;
2) нехай G = S3, H = {e, b}. Лівий суміжний клас, породжений елементом d, складається з двох елементів: dH = {de, db} = {d, a}. Правий суміжний клас Hd = {ed, bd} = {d, a2}. Як бачимо, в цьому випадку dH ( Hd;
3) нехай G = Z, H – підгрупа цілих чисел, кратних числу 5. Суміжний клас, утворений числом 1, є множиною 1 + 5Z = {1, 1(5, 1(2·5, …}. Це всі цілі числа, які при діленні на 5 дають остачу 1.
Очевидно, що існує тільки 5 різних класів групи Z за підгрупою 5Z: 5Z, 1 + 5Z, 2 + 5Z, 3 + 5Z, 4 + 5Z.
Зафіксуємо деяку підгрупу H групи G і розглянемо всі можливі ліві суміжні класи за цією підгрупою, утворені елементами групи G. Перш за все ясно, що кожний елемент g ( G належить до деякого класу , а саме, до класу gH, бо g = ge ( gH.
Далі, якщо підгрупа H скінченна і має n елементів, то кожен суміжний клас також має n елементів. Дійсно, якщо h1 ( h2 , то gh1 ( gh2, бо за законом скорочення із gh1 = gh2 отримуємо h1 = h2.
Для нескінченної підгрупи ці міркування означають, що множини gH та H рівнопотужні. Тоді й ліві суміжні класи рівнопотужні.
Усе раніше сказане справедливе й для правих суміжних класів.
Лема. Усякі два суміжні класи або не перетинаються або співпадають.
Доведення. Треба довести: із g1H ( g2H ( ( випливає g1H = g2H. Нехай g0 ( g1H ( g2H, тобто g0 = g1h1 = g2h2, де h1, h2 ( H. Тоді g1H ( g2H. Це випливає з низки рівностей: для будь-якого h ( H: g1h = g1(h1(h1)-1)h = g0h' = g2h2h' = g2h'' ( g2H.
Аналогічно можна довести, що g2H ( g1H.
Теорема Лагранжа. Порядок будь-якої підгрупи H скінченої групи G є дільником порядку групи.
Доведення. Кожен елемент g ( G належить принаймні до одного класу, а саме до класу gH. Тому суміжні класи утворюють покриття групи. За доведеною лемою бачимо, що група є об’єднанням суміжних класів, які не перетинаються. Число класів позначатимемо через j і назвемо індексом підгрупи H у групі G. Оскільки всі класи мають однакове число елементів, то n = j m, де n – порядок групи G; m – порядок підгрупи H. Теорему доведено.
Наслідок. Група простого порядку не має жодних підгруп, крім тривіальних. Порядок елемента скінченої групи ділить порядок групи. Група простого порядку завжди циклічна.
Не слід думати, що для будь-якого дільника m порядку групи завжди існує підгрупа порядку n. Так, у групі A4 (парні підстановки в S4) порядку 12 не існує підгруп порядку 6.
Підгрупа Н групи G називається нормальною підгрупою, якщо gH = Hg для всіх g ( G. Остання умова означає, що відповідні ліві й праві суміжні класи за нормальною підгрупою співпадають. Сукупність суміжних класів за нормальною підгрупою утворює групу. Операція множення суміжних класів визначається за допомогою рівності g1H•g2H = (g1 g2)H. Ця група називається фактор-групою групи G за нормальною підгрупою Н і позначається G / Н.
Відображення f: G1 ( G2 групи (G1, •) в групу (G2, () називається гомоморфізмом, якщо для будь-яких елементів x, y ( G1, f(x • y) = f(x) ( f(y).
Розглянемо два приклади.
а) C2 = {-1, 1} – група квадратних коренів з одиниці. Групова операція визначається рівностями 1·1 = 1, 1·(-1) = (-1)·1 = -1, (-1)·(-1) = 1.
б) S2 – група підстановок другого порядку. Елементами є підстановки e = (1), a = (1, 2). Тут ee = e, ea = ae = a, aa = e.
Розглянемо тепер довільну групу другого порядку, абстрагуючись від природи її елементів. Вона мусить мати нейтральний елемент e і ще один елемент a, відмінний від нейтрального. Групова операція задається наступною таблицею Келі:
Т
е
а
е
е
а
а
а
е
Це єдино можливий варіант таблиці. Дійсно, рівності еТе = е, еТа = аТе = а випливають із визначення нейтрального елемента. Рівність аТа неможлива, бо це означало б, що а – нейтральний елемент. Значить, аТа = е.
Групи C2 і S2 мають таку саму таблицю; в першому випадку треба замінити e i a на 1 і –1. Зауважимо, що ці групи є циклічними, а тому й абелевими.
Отже, з точки зору побудови закону композиції всі групи другого порядку не відрізняються між собою. Це можна виразити ще так. Нехай (G1, •) = {e1, a1}, (G2, () = {e2, a2} – дві групи. Існує бієктивне відображення f: G1 ( G2 , визначене рівностями f(e1) = e2, f(a1) = a2, при якому зберігаються закони композиції. Це означає, що f(e1 • a1) = f(e1) ( f(a1), f(а1 • a1) = f(а1) ( f(a1). Справді, f(e1 • a1) = a2 та f(а1 • a1) = e2, f(e1) ( f(a1) = e2 ( a2 = a2 та f(а1) ( f(a1) = a2 ( a2 = e2.
Слід зауважити, що друге можливе тут відображення g: G1 ( G2,визначене рівностями g(e1) = а2, g(a1) = е2, не зберігає законів композиції. Це видно з наступного: g(а1 • a1) = a2 та g(а1) ( g(a1) = e2 ( e2 = e2. Отже, g(а1 • a1) ( g(а1) ( g(a1).
Бієктивне відображення f: G1 ( G2 групи (G1, •) в групу (G2, () називається ізоморфізмом, якщо для будь-яких елементів x, y ( G1, f(x • y) = f(x) ( f(y).
Іншими словами, ізоморфізмом з групи G1 в групу G2 називається бієктивний гомоморфізм з групи G1 в групу G2.
Дві групи G1 i G2 називаються ізоморфними, якщо існує ізоморфізм групи G1 в групу G2; це позначають G1 ( G2.
Таким чином, нами встановлено, що всі групи другого порядку ізоморфні. Проте, як далі бачимо, існують неізоморфні групи, навіть якщо існує бієктивне відображення однієї групи на іншу.
Групи Q+ додатних раціональних чисел відносно множення й Q раціональних чисел відносно додавання неізоморфні. Правда, існують бієктивні відображення множини Q+ на множину Q, але жодне з них не може бути ізоморфізмом. Справді, яке б не було бієктивне відображення f: Q+ ( Q, завжди існують такі елементи а ( Q і х ( Q+, що f(2) = а і f(х) = а/2. Якби це відображення було ізоморфізмом, то повинно бути f(х2) = а/2 + а/2 = а = f(2). Звідси за бієктивністю відображення х2 = 2, що неможливо, бо х - додатнє раціональне число.
Дві скінченні ізоморфні групи мають однакові таблиці Келі в такому розумінні: якщо всі елементи аі в першій таблиці замінити відповідно на f(аі) (f - ізоморфізм груп), то отримаємо другу таблицю.
Покажемо, що існує лише одна таблиця для групи третього порядку G={e, a, b}. Перший рядок та перший стовпець таблиці мусять мати вигляд: e, a, b. Як можна заповнити порожні місця ? Зауважимо, що в кожному рядку й у кожному стовпці повинні бути всі елементи без повторень незалежно від порядку групи. Дійсно, коли б ai aj = ak і as aj = ak, то було б ai aj=as aj. Звідси за законом скорочення ai = as (при i ( s), що неможливо.
Чому може дорівнювати а2 ? Це не може бути е, бо в другому рядку на останньому місці доведеться ставити b. Але b вже є в третьому стовпці. Залишається тільки варіант а2 = b. Тепер легко заповнити всю таблицю.
Т
е
а
b
е
е
а
b
а
а
b
е
b
b
е
а
Треба ще довести, що бінарна алгебраїчна операція, задана цією таблицею, асоціативна. Це можна зробити обхідним шляхом. Відомо, що існують групи третього порядку (група C3 і підгрупа парних підстановок групи S3) з такою ж таблицею.
Таким чином, з точністю до ізоморфізму існує лише одна група третього порядку, яка, як видно з таблиці, є абелевою. Інакше кажучи, всі групи третього порядку ізоморфні між собою.
Збудуємо таблицю Келі операції для циклічної групи четвертого порядку за рівностями a2 = b, a3 = c, a4 = e.
Т
е
а
b
c
е
е
а
b
c
а
а
b
c
e
b
b
c
e
a
c
c
e
a
b
Виникає запитання: чи існують нециклічні групи четвертого порядку ? Слід зауважити, що за теоремою Лагранжа всі її елементи повинні мати порядок 2, тобто a2 = b2 = c2 = е Далі показано, як заповнити (це можна зробити єдиним способом) таблицю Келі для цього випадку
Т
е
а
b
c
е
е
а
b
c
а
а
e
c
b
b
b
c
e
a
c
c
b
a
e
Т
е
а
b
c
е
е
а
b
c
а
а
e
b
b
e
c
c
e
Легко перевірити, що таку таблицю має група підстановок множини з чотирьох елементів a = (1, 2)(3, 4), b = (1, 3)(2, 4), c = (1, 4)(2, 3), e = (1). Ця група є абелевою, бо таблиця Келі симетрична відносно головної діагоналі. Це так звана група Клейна.
Отже, з точністю до ізоморфізму існує лише дві групи четвертого порядку.
Теорема Келі. Будь-яка група G ізоморфна деякій підгрупі групи Aut(G).
Наслідок. Якщо G – скінченна група порядку n, то вона ізоморфна деякій підгрупі групи підстановок Sn.
Таким чином, вивчення скінчених груп можна звести до вивчення груп підстановок.
Кільця та поля
Нехай К – непорожня множина, на якій задані дві бінарні алгебраїчні операції + (додавання) і ∙ (множення), які задовольняють наступним умовам:
(K1) (K, +) – абелева група;
(К2) (K, ∙) – півгрупа;
(К3) операція множення дистрибутивна відносно операції додавання:
(x + y) z = x z + y z, z (x + y) = z x + z y
для всіх x, y, z ( K.
Тоді (K, +, ∙) називається кільцем.
Структура (K, +) називається адитивною групою кільця, а (K, ∙) - його мультиплікативною півгрупою.
Якщо (K, ·) – моноїд, то кажуть, що (K, +) – кільце з одиницею. Кільце називається комутативним, якщо (K, ∙) – абелева півгрупа (на відміну від груп, комутативне кільце не прийнято називати абелевим). Нейтральний елемент 0 – відносно додавання і 1 – відносно множення (якщо він існує) називають відповідно нулем і одиницею кільця.
Далі наведено приклади кілець:
1) множина (Z, +, ∙) цілих чисел відносно звичайних операцій додавання й множення;
2) множина (Q, +, ∙) раціональних чисел відносно звичайних операцій додавання й множення;
3) множина (R, +, ∙) дійсних чисел відносно звичайних операцій додавання й множення;
4) множина (C, +, ∙) комплексних чисел відносно звичайних операцій додавання й множення;
5) множина дійснозначних матриць Мn(R) розміру nxn відносно додавання та множення матриць є кільцем з одиницею. Роль нейтрального елемента відносно множення тут відіграє одинична матриця Е. Таке кільце називається повним матричним кільцем над R або кільцем квадратних матриць порядку n над R. Це один з найважливіших прикладів кілець. Оскільки при n > 1, матриці при множенні, як правило не можна переставляти, то Мn(R) – некомутативне кільце.
Підмножина L кільця К називається підкільцем, якщо для будь-яких елементів x, y ( L
x + y ( L i x ∙ y ( L.
Підкільце L кільця К з одиницею називається ідеалом, коли для будь-яких елементів x ( L та a ( K виконується a∙x ( L, x∙a ( L.
Нехай К - кільце з одиницею, а L – ідеал у цьому кільці. Фактор-групу К / L адитивної групи (K, +) кільця за ідеалом L (який є нормальним дільником в адитивній групі) можна перетворити в кільце, наступним чином задаючи операцію множення суміжних класів: (x + L) ( (y + L) = x∙y + L. Це кільце називається фактор-кільцем кільця К за ідеалом L і позначається К / L.
Нижче наведено приклад фактор-кільця, який широко використовується. Множина nZ цілих чисел, кратних деякому фіксованому натуральному числу n, є ідеалом в кільці цілих чисел Z. Розглянуту раніше фактор-групу Z / nZ = Zn можна перетворити в кільце задаючи операцію множення ( класів за модулем числа n. Щоб перемножити два класи і потрібно спочатку перемножити цілі числа r і s, а потім знайти остачу від ділення знайденого добутку на число n. Клас знайденої остачі й буде результатом множення класів і . Множина Zn разом із заданими на ній операціями додавання ( та множення ( є комутативним кільцем з одиницею, яке має n елементів.
Далі наведено таблицю Келі для операції множення ( кільця Z5:
(
Відображення f: К1 ( К2 кільця (К1, +, ∙) в кільце (К2, (, () називається гомоморфізмом, якщо воно зберігає всі операції, тобто коли для будь-яких елементів x, y ( К1
f(x + y) = f(x) ( f(y),
f(x ∙ y) = f(x) ( f(y).
Якщо гомоморфізм кілець є бієктивним відображенням, то він називається ізоморфізмом кілець. Два кільця К1 i К2 називаються ізоморфними, якщо існує ізоморфізм кільця К1 в кільце К2; факт ізоморфізму кілець коротко записують у вигляді К1 ( К2.
Поле Р – це комутативне кільце з одиницею, в якому кожен відмінний від нуля елемент має обернений відносно операції множення. Іншими словами комутативне кільце з одиницею Р є полем, коли сукупність його відмінних від нуля елементів утворює абелеву групу відносно операції множення.
Два поля Р1 i Р2 називаються ізоморфними, якщо вони ізоморфні як кільця.
Поле, яке має скінченне число елементів, називається скінченним полем або полем Галуа.
Теорема. Будь-яке скінченне поле має рn елементів, де р – просте, а n – натуральне число. Для фіксованих простого числа р і натурального числа n існує і, з точністю до ізоморфізму, лише одне поле з числом елементів рn.
Скінченні поля з точністю до ізоморфізму будуються наступним чином.
Скінченне поле з р елементів ізоморфне кільцю Zp цілих чисел за модулем р.
Скінченне поле з рn елементів отримується таким чином. Розглядаємо кільце многочленів Zp[x] від змінної х над полем Zp. Беремо в цьому кільці многочлен f(x) степеня n, який є нерозкладним над Zp. Позначаємо через (f(x)) ідеал, який складається з елементів, що діляться на f(x). Тоді фактор-кільце Zp[x]/(f(x)) є бажаним полем з рn елементів. Виконання операцій над елементами цього поля здійснюється за двома модулями: за модулем числа р і за модулем многочлена f(x). Часто це позначається наступним чином: (mod f(x), p).
Гомоморфізми та ізоморфізми алгебр
Розглянемо алгебри A(X; (1, …, (k) і B(Y; (1, …, (k), в яких операції (l та (l є однаково ni арними, i = 1, 2, …, k. Відображення f: X ( Y з умовою для всіх та всіх називається гомоморфізмом алгебри A(X; (1, …, (k) в алгебру B(Y; (1, …, (k). Гомоморфізм, який є одночасно бієктивним відображенням, називається ізоморфізмом алгебр.
Множина Y ( X називається замкнутою відносно n-арної операції ( на Х, коли ((Yn) ( X. Якщо підмножина Y ( X замкнута відносно всіх операцій алгебри A(X; (1, …, (k) і їй відповідає алгебра B(Y; (1, …, (k), то остання називається підалгеброю алгебри A(X; (1, …, (k).
Для випадків груп та кілець поняття гомоморфізму, ізоморфізму та підалгебри були розглянуті раніше.
Приклади розв’язування задач
1. Алгебра складається з усіх відображень множини {1,2} в себе: , , , . Операцією є композиція ○ відображень. Скласти таблицю Келі та дослідити властивості операції в цій алгебрі.
Розв’язування. Таблиця Келі для операції ○ в заданій алгебрі має вигляд
○
а
b
c
d
а
a
b
a
b
b
a
b
b
a
c
a
b
c
d
d
a
b
d
c
Як відомо композиція відображень є асоціативною, отже алгебра A = (X; ○} є півгрупою, де X = {a, b, c, d}. У півгрупі A є одиничний (нейтральний) елемент c, оскільки (x ( X, x○c = c○x = x. Отже, півгрупа A є моноїдом. Оскільки a○b = b, а b○a = a, то моноїд не є абелевим.
2. Перевірити, чи утворює групу множина R+ операція T, якщо вона задається як a T b = a2b4.
Розв’язування. Для того, щоб алгебра була групою необхідно, щоб у алгебрі існував нейтральний елемент. Умовою існування нейтрального елемента e є (x ( R+, e T x = x T e = x. Нехай e1 –лівий, а e2 –правий нейтральний елементи. Тоді e1 T x = e12x4 = x, звідси e1 = x –3/2. Разом з тим x T e2 = x2e24 = x і e2 = x –1/4. Як бачимо e2 ≠ e1. Таким чином, нейтрального елемента не існує, і тому задана алгебра не є групою.
3. Показати, що група додатних дійсних чисел відносно операції множення (R+; () ізоморфна групі дійсних чисел відносно операції додавання (R; +).
Розв’язування. Для доведення ізоморфізму можна використати наступне бієктивне відображення ln : R+ ( R, яке зберігає групові операції - ln(a(b) = ln(a) + ln(b).
4. Довести, що множина всіх чисел виду (a та b – цілі числа), які додаються та множаться як звичайні дійсні числа, є кільцем.
Розв‘язування. Справді, замкнутість цієї множини відносно операцій додавання та множення випливає зі співвідношень () + () = (a + b) + (c + d) та ()() = (ac + 3bd) + (ad + bc). Таким чином, наведені операції є дійсно бінарними операціями на заданій множині.
Перевіримо спочатку, що задана множина з операцією додавання є абелевою групою. Оскільки числа виду є частковим випадком дійсних чисел, то операція їх додавання є асоціативною й комутативною. Нейтральним елементом відносно додавання, очевидно, є елемент . Оберненим для елемента відносно операції додавання є елемент .
Числа виду є частковим випадком дійсних чисел. Тому й операція їх множення є асоціативною. Значить, вказана множина відносно заданої операції множення є півгрупою.
Як згадувалося раніше, операції множення та додавання на заданій множині є операціями над дійсними числами. Тому вказана операція множення є дистрибутивною відносно операції додавання.
Отже множина всіх чисел виду (a та b – цілі числа), які додаються та множаться як звичайні дійсні числа, є кільцем.
Зауважимо, що згадана множина не є полем, бо не існує нейтрального елемента відносно операції множення, як показують наступні міркування.
Нехай - нейтральний елемент відносно операції множення. Тоді повинна виконуватися рівність . З неї отримуємо, що . Як бачимо зліва стоїть ціле число, а справа – ірраціональне. Ми отримали суперечність.
ЛІТЕРАТУРА
1. Дискретна математика: Підручник / Ю.М.Бардачов, Н.А.Соколова, В.Є.Ходаков; за ред. В.Є.Ходакова. – К.: Вища школа, 2002. – 287с.
2. Основи дискретної математики: Підручник / Ю.В.Капітонова, С.Л.Кривий, О.А.Летичевський, Г.М.Луцький, М.К. Печурін. – К.: Наукова думка, 2002. – 568с.
3. Луцький Г.М., Кривий С.Л., Печурін М.К. Основи дискретної математики. – К.: ВІПОЛ, 1995. – 252с.
4. Бородін О.I., Потьомкін Л.В., Сліпенко А.К. Основні поняття сучасної алгебри. - К.: Вища школа, 1993. -112 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора