Основні Алгебраїчні структури.

Індивідуальне завдання №1

МНОЖИНИ ТА ВІДОБРАЖЕННЯ.

Під множиною розуміють клас, сукупність різних предметів. Множини можуть складатись з найрізноманітніших предметів. Цим і пояснюється можливість застосуваня теорії множин в різних областях знань – математиці, механіці, фізиці, хімії, біології, лінгвістиці... Об’єкти, які входять до множини, називають її елементами. Елементи множини позначають звичайно x, y, z,…(або x₁, x₂, x₃, …), а самі множини позначають А, В, С,... Вважаємо, що всі елементи множини різні. Множина, що складається із скінченного числа елементів, називається скінченною. Наприклад, множина всіх двоцифрових чисел, множина вершин шестикутника. Кількість елементів скінченої множини А будемо позначати n(A). Множина, яка містить необмежену кількість елементів, називається нескінченною. Наприклад, множина натуральних чисел, множина всіх точок відрізка. Нескінченні множини бувають зчисленні і незчисленні. Нескінченна множина є зчисленною (зліченною), якщо її елементи можна пронумерувати. Наприклад множина натуральних чисел, множина парних чисел.

Знаком Î позначають належність елемента до тієї чи іншої множини. Наприклад, вираз означає, що елемент x належить множині А. Якщо х не є елементом множини А, то пишуть .

Множина вважається заданою, якщо ми можемо для будь – якого предмету визначити, належить він цій множині, чи ні. Задати множину можна різними способами. Якщо множина скінченна, можна задати повний список її елементів (у фігурних дужках). Наприклад: {2, 3, 5, 7}. Порядок елементів у записі значення не має. Якщо перелік елементів надто довгий або множина нескінченна, використовують задання множини за допомогою характеристичної властивості: М= {x | P(x)} – множина М складається зі всіх х, які задовольняють властивість Р(х).

Дві множини називаються рівними, якщо вони складаються з тих самих елементів.

Множина, яка не містить елементів, називається порожньою і позначається Æ. Наприклад множина дійсних коренів рівняння є порожньою.

Множина, яка складається із всіх можливих елементів називається універсальною множиною і позначається U.

Якщо кожний елемент множини А є елементом множини В, то множину А називають підмножиною множини В і позначають АÌВ або ВÉА. Наприклад {2, 5}Ì{1, 2, 3, 5, 8}. Очевидно, що будь-яка множина є підмножиною універсальної множини. Якщо властивості, якими задана множина і її підмножина співпадають, то ці множини будуть рівні. Тому вважають, що кожна множина є підмножиною самої себе. Якщо властивість, з допомогою якої задається деяка підмножина протирічить властивості, за якою задана множина, то ця підмножина буде порожньою. Тому і порожню множину вважають підмножиною кожної множини. Для будь-якої множини вона сама і порожня множина називаються невласними підмножинами, а всі інші підмножини - власними.

Приклад 1.1. Які підмножини має множина А={a, b, c}. Які з них є власними? Множина А={a, b, c} і порожня множина Æ є невласними підмножинами цієї множини. Крім цього, множина А має власні підмножини: {a}, {b}, {c}, {a, b}, {a, c}, {b, c}.

Нехай А, В, С,... – підмножини деякої універсальної множини U. В множині всіх можливих підмножин універсальної множини визначимо чотири дії: об’єднання, переріз, різниця та доповнення. Результат дій над множинами звичайно зображають графічно на діаграмах Ейлера – Венна.

Об’єднанням множин А і В називається множина, що складається з елементів, які належать хоч одній з цих множин (мал.1.1). і позначається АÈВ, .

Наприклад, {2, 4, 6, 8}È{1, 2, 3, 4} = {1, 2, 3, 4, 6, 8},

{a, b, c, d}È{b, f} = {a, b, c, d, f},

{1, 2, 3, 4.} }È{ 2, 4} = {1, 2, 3, 4}.

Об’єднанням довільної множини А з порожньою множиною є сама множина А. Об’єднанням універсальної множини з будь-якою множиною є універсальна множина.

Під об’єднанням кількох (і навіть безлічі) множин розуміють множину всіх тих і тільки тих елементів, які належать принаймні одній з цих множин. Якщо А₁, А₂,... A_n,... – нескінченна послідовність множин, то їх об’єднання позначають коротко так: . Схоже просте позначення використовують замість об’єднання множин А₁È А₂ È...È A_n.

Перетином (перерізом) множин А і В називається множина, що складається з елементів, які одночасно належать як до множини А, так і до множини В і позначається АÇВ (мал.1.2). Це означення можна записати наступним чином: .

Наприклад, {2, 4, 6, 8}Ç{1, 2, 3, 4} = {2, 4},

{a, b, c, }Ç{a, c, d, f} = {a, c}.

Цілком аналогічно перетином кількох (і навіть безлічі) множин називається множина всіх їх спільних елементів. Переріз множин А₁Ç А₂ Ç...Ç A_n позначають символом . Так само переріз А₁Ç А₂ Ç...Ç A_n Ç... позначають через .

Перетином довільної множини з порожньою множиною є порожня множина. Перетином універсальної множини з будь-якою множиною А є сама множина А.

Різницею множин А і В називається множина, яка складається з елементів, що належать до А, але не належать до В і позначається А\В (мал.1.3). Пишуть .

Наприклад, {2, 4, 6, 8}\{1, 2, 3, 4} = {6, 8},

{a, b, c, }\{a, c, d, f} = {b},

{1, 2, 3, 4}\{2, 4} = {1, 3}.

Доповненням множини А називається множина, яка складається з тих елементів універсальної множини U, які не належать множині А і позначається (мал.1.4). . Очевидно, що будь-який елемент універсальної множини належить або А, або . Якщо АÌВ, то В\А називається доповненням множини А до множини В. Очевидно, що доповненням універсальної множини є порожня множина і навпаки.

Приклад 1.1. Нехай А – множина всіх дільників числа 18, В = {x Î Z | 0<x ≤ 6}. Знайдіть АÈВ, АÇВ, В\А, А\В.

Оскільки А = {1, 2, 3, 6, 9, 18}, B = {1, 2, 3, 4, 5, 6}, то АÈВ = {1, 2, 3, 4, 5, 6, 9, 18}, АÇВ = {1, 2, 3, 6}, В\А = {4, 5}, А\В = { 9, 18}.

Приклад 1.2. Знайти підмножини Х і У множини Е, якщо для будь-якої підмножини А множини Е має місце наступна рівність АÇХ = АÈУ.

Якщо рівність АÇХ = АÈУ має місце для будь-якої підмножини множини Е, то вона справедлива і при А = Е та при А = Æ. При А = Е з рівності ЕÇХ = ЕÈУ отримаємо Х = Е, а, при А = Æ, з рівності ÆÇХ = ÆÈУ - Æ = У.

Основні закони операцій над множинами:

1. Закон тотожності: А = А.
2. Закон протиріччя: Æ.
3. Закон виключення третього: .
4. Закони ідемпотентності: , .
5. Закони комутативності: А Ç В = В Ç А і А È В = В È А.
6. Закони асоціативності: А Ç(В Ç С) = (А Ç В)Ç С і А È(В È С) = (А È В)È С.
7. Закони дистрибутивності: (А Ç В)È С = (А È С)(В È С) і (А È В)Ç С = (А Ç С)(В Ç С).
8. Закони поглинання: , .
9. Закони де Моргана: , .
10. Закон подвійного заперечення: .

Якщо аÎА і bÎВ, то пару елементів а і b, записану (а, b), називають впорядкованою парою, при цьому вважають, що пари (а₁, b₁) і (а₂, b₂) рівні, якщо а₁=а₂ і b₁= b₂. Множину, елементами якої є всі впорядковані пари (а, b), де аÎА і bÎВ, називають прямим або декартовим добутком множин А і В, який позначають А´В. Зауважимо, що А´В¹В´А, коли А¹В.

Приклад 1.3. a) Нехай А={1, 2}, a B={2, 3}, то А´В={(1, 2), (1,3), (2, 2), (2, 3)}, a В´А={(2, 1), (2, 2), (3, 1), (3, 2)}.

б) Нехай А=={a, b, c}, a B={a, f}, то А´В ={(a, a), (a, f), (b, a), (b, f), (c, a), (c, f)}, a В´А={(a, a), (a, b), (a, c), (f, a), (f, b), (f, c)}.

Декартів добуток А´А часто називають декартовим квадратом множини А. Згідно з означенням декартового добутку А´А = {(х; у)| х А, у А}.

Наприклад, декартів квадрат R´R=R², множини дійсних чисел - це множина всіляких пар дійсних чисел. Якщо на площині вибрати прямокутну систему координат, то ці пари стають назвами точок площини, і таким чином множина R² дістає важливе геометричне тлумачення. Ототожнивши назви точок (тобто елементи із R²) з самими точками, можна сказати, що R²– це множина точок площини.

Найпростіші властивості декартових добутків:

1. (АÇВ)´С=(А´С)Ç(В´С), С´(АÇВ)=(С´А)Ç(С´В).
2. (АÈВ)´С=(А´С)È(В´С), С´(АÈВ)=(С´А)È(С´В).
3. (А₁ÇА₂)´(В₁ÇВ₂)=(А₁´В₁) Ç (А₂´В₂).
4. (A\B)´С=(А´С)\(В´С), С´(А\В)=(С´А)\(С´В).
5. A´B=Æ Û A=Æ Ú B=Æ.

Розглянемо доведення однієї з цих властивостей, а саме С´(А\В)=(С´А)\(С´В). За означенням (x, y) Î С´(А\В) тоді і тільки тоді, коли x Î С і y Î А\В, тобто x Î С, y Î А i y ÏВ. Це означає, що (x, y)Î С´А i (x, y) Ï С´В. Звідси (x, y) Î (С´А)\(С´В).

Доведення решти властивостей пропонуємо виконати самостійно.

Під відношення між елементами множини розуміють який-небудь зв’язок між цими елементами. Наприклад на множині натуральних чисел вам відомі відношення більше (>) і менше (<), а в геометрії, на множині прямих – відношення паралельності чи перпендикулярності. Задавати відношення можна різними способами. Один з них – за допомогою пар. Наприклад на множині А ={1, 2, 3, 4, 5} задамо відношення “більше” - тобто випишемо всі пари елементів, де перше число більше за друге: (2, 1), (3,1), (3, 2), (4,1), (4,2), (4,3), (5,1), (5, 2), (5,3), (5,4). Така множина пар є підмножиною декартового добутку А´А. Бінарним відношенням Â, заданим у множині A є деяка підмножина Â декартового добутку A´A. Розглядають також відношення між елементами двох різних множин. Відношенням між елементами множин А і В називається будь-яка підмножина Â декартового добутку А´В. Позначають відношення буквою Â (від латинського слова relatio – відношення). Для бінарного відношення пишуть aÂb замість (a, b) Î Â.

Об’єднання і перетин двох відношень між множинами А і В – це, відповідно, об’єднання і перетин відповідних підмножин декартового добутку.

Якщо Â₁ÌА´В і Â₂ÌВ´С – два бінарні відношення, то можна означити добуток відношень Â_1°Â₂, як наступну підмножину декартового добутку А´С:

Â_1°Â₂={(a, c)Î А´С | $ b (a, b) Î Â₁ Ù (b, c) Î Â₂}.

Нехай ÂÌА´В – бінарне відношення. Тоді обернене бінарне відношення Â^-1 є наступною підмножиною декартового добутку В´А: Â^-1={(b, a) Î В´А | (a, b) Î Â}.

Бінарне відношення Â на множині А´А називається рефлексивним, якщо "a ÎÂ: aÂa. Прикладами рефлексивних відношень є відношення подібності на множині трикутників (будь-який трикутник подібний сам до себе), відношення рівносильності на множині рівнянь і т.д.

Бінарне відношення Â на множині А´А називається симетричним, якщо "a, b ÎÂ: aÂb Þ bÂa. Відношення паралельності на множині прямих, відношення подібності на множині трикутників, відношення рівносильності на множині рівнянь є симетричними.

Бінарне відношення Â на множині А´А називається транзитивним, якщо "a, b, c ÎÂ: (aÂb Ù bÂc) Þ aÂc. Транзитивними є відношення паралельності на множині прямих, відношення подібності на множині трикутників, відношення подільності на множині натуральних чисел.

Відношення Â на множині А називається відношенням еквівалентності, якщо воно водночас має властивості рефлексивності, симетричності, транзитивності.

Якщо на множині А зафіксоване певне відношення еквівалентності j, то про елементи х і у, які перебувають у цьому відношенні кажуть, що вони еквівалентні. Із поняттям еквівалентності на множині А тісно пов’язане поняття класифікації елементів цієї множини або розбиття множини на класи. Кажуть, що множину А розбито на класи L₁, L₂,… L_n, якщо:

1) L₁È L₂È…È L_n=A;

2) L_i Ç L_j =Æ, якщо i ¹ j;

3) L_i ¹Æ для всіх i =1, 2,..., n.

Кожний клас складається з усіх еквівалентних між собою елементів. Тому ці класи називаються класами еквівалентності. Множина всіх класів еквівалентності називається фактор-множиною множини А за еквівалентністю j.

Приклад 1.4. Нехай дано множину А={1, 2, 3, 4, 5}. Знайдемо будь-яке розбиття А. Виділимо з А дві підмножини: парних і непарних чисел. Отримаємо А₁={2, 4} і А₂={1, 3, 5}. Система { А₁, А₂} є розбиттям А на класи, оскільки:

1) А₁ÈА₂=А;

2) А₁ÇА₂=Æ;

3) А₁¹Æ, А₂¹Æ.

Звичайно, множина А має і інші розбиття, наприклад { А₁, А₂, А₃, А₄, А₅}, де А₁={1}, А₂={2}, А₃={3}, А₄={4}, А₅={5}.

Приклад 1.5. Розглянемо відношення нa  : означає, що ділиться на m. Його прийнято записувати так: () і читати: “ х конгруентне y за модулем m ”. Так як то воно рефлексивне; так як з випливає то воно симетричне;

з того, що і випливає тому це відношення транзитивне. Отже, - відношення еквівалентності. Його класи еквівалентності – це m арифметичних прогресій …, при .

Кожен такий клас (прогресію), що відповідає значенню , далі позначаємо через . Отже , … . Елементи цієї фактор множини називають класами лишків за модулем m.

 

Поняття відображення (функції), як і поняття множини, є фундаментальним.

Відображенням (функцією) f з множини А в множину В () називається закон, згідно якого елементам з першої множини А ставляться у відповідність елементи з другої множини В. Щоб задати конкретну функцію, потрібно задати множини А і В, та закон, який встановлює відповідність між елементами цих множин. Законом може бути або перечислення, або деяке загальне правило.

Теорема. Кожна функція визначає бінарне відношення на множині А´В, і, навпаки, кожне бінарне відношення на множині А´В визначає функцію .

Доведення. Нехай задана функція . Тобто задані множини А і В та закон f. Розглянемо прямий добуток А´В. Задамо на ньому бінарне відношення наступним чином: aÂb, якщо а відображається в b.

Закон відповідності між елементами x ÎA і y ÎB записують у вигляді y=f(x), при цьому елемент y називають образом елемента x, a x – прообразом елемента y.

Множину тих елементів x ÎA, кожний з яких має образ, називають областю визначення відображення f і позначають D(f).

Множину тих елементів y ÎB, для кожного з яких існує прообраз, називають множиною значень відображення f і позначають E (f).

Графіком функції f з областю визначення А і множиною значень В називають підмножину Г декартового добутку А´В, яка складається з усіх елементів (x, f (x)), де x ÎA, f (x)ÎB.

Функція називається ін’єктивною, якщо кожен елемент з В відповідає єдиному елементу з А. Функція сюр’єктивна, якщо для кожного елемента з В існує прообраз з А. Функція бієктивна (взаємно однозначна), якщо вона ін’єктивна і сюр’єктивна одночасно. Якщо існує хоча б одна взаємно однозначна відповідність між множинами А і В, то вони називаються еквівалентними.

Якщо функція f є взаємно однозначною відповідністю між множинами А і В, то визначена і функція f ^-1, яка буде взаємно однозначною відповідністю між множинами В і А, причому f ^-1(b)=a тоді і тільки тоді, коли f (a)=b. Функцію f ^-1 називають оберненою до функції f.

Суперпозицією двох даних функцій i називається функція , закон якої g _° f задається наступним чином: Û $bÎB: ( Ù ). Функція , отримана таким чином з функцій g і f називається їх композицією.

Нехай А- деяка скінченна множина, яка складається з n різних елементів: A={a₁, a₂, a₃, …, a_n}. Всі можливі скінченні впорядковані множини з n елементів, які можна отримати міняючи місцями елементи множини А називаються перестановками з n елементів.

Наприклад, (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) та (3, 2, 1) всі можливі перестановки множини {1, 2, 3}.

Кількість перестановок з n елементів дорівнює n!. Вважаємо, що порожню множину можна впорядкувати єдиним способом, тому вважається, що 0!=1.

Якщо в заданій перестановці поміняти місцями будь-які два елементи, а решту елементів залишити на своїх місцях, то отримаємо нову перестановку. Таке перетворення перестановки називається транспозицією. Наприклад, перестановка (1, 3, 2) отримується з перестановки (1, 2, 3) внаслідок обміну місцями 2 і 3.

Всі n! перестановок з n елементів можна розташувати в такому порядку, що кожна наступна перестановка буде отримуватись із попередньої однією транспозицією, причому у якості вихідної перестановки можна вибрати будь-яку з перестановок. Зокрема від довільної перестановки з n елементів можна перейти до довільної іншої перестановки з тих само елементів за допомогою декількох транспозицій. Перестановка називається парною, якщо вона отримується з перестановки з допомогою парної кількості транспозицій і непарною у протилежному випадку.

Приклад 1.6. Нехай А = (1; 2; 3; 4). Перестановка (1; 2; 3; 4) за означенням парна. Парною буде і перестановка (4; 2; 1; 3) так, як вона може бути отримана з перестановки (1; 2; 3; 4) за допомогою парної кількості транспозицій: поміняємо місцями в перестановці (4; 2; 1; 3) перший і четвертий елементи, отримаємо перестановку (3; 2; 1; 4) і тепер у ній міняємо місцями перший і третій елементи. Отримали вихідну перестановку (1; 2; 3; 4), як результат двох транспозицій. Аналогічно можна переконатися, що перестановка (4; 1; 2; 3) буде непарною, - вона переходить у перестановку (1; 2; 3; 4) після трьох транспозицій: (4; 1; 2; 3)® (1; 4; 2; 3) ® (1; 2; 4; 3) ® (1; 2; 3; 4). Кожна транспозиція міняє парність перестановки, кількість парних перестановок з n – елементів дорівнює кількості непарних, тобто дорівнює n!/2.

Нехай А - деяка скінченна множина, яка складається з n різних елементів. Для простоти будемо вважати, що це перші n натуральних чисел: A={1, 2, 3, …, n}. Взаємно однозначне відображення f множини А на себе називається підстановкою n – го степеня. Для позначення підстановки f використовують запис , де (i₁, i₂, i₃,..., i_n) та (k₁, k₂, k₃,..., k_n) – дві перестановки з n елементів множини А (k₁, k₂, k₃,..., k_n образи елементів i₁, i₂, i₃,..., i_n при відображенні f). Одна і та ж підстановка n-го степеня може бути записана багатьма способами, зокрема у вигляді . При такому записі різні підстановки відрізняються перестановками, що стоять у нижній стрічці, а тому кількість підстановок n-го степеня дорівнює кількості перестановок з n елементів, тобто n!. Тотожною підстановкою називається підстановка . Якщо парності верхньої та нижньої перестановок у підстановці співпадають, то підстановка називається парною, якщо не співпадають – непарною.

Введемо операцію множення на множині підстановок n-го степеня. За означенням підстановок n-го степеня – це взаємно однозначне відображення f скінченої множини з n елементів у себе. Послідовне виконання двох підстановок n-го степеня знову буде взаємно однозначним відображенням множини А в себе і приводить до третьої підстановки n-го степеня, яку називають добутком першої з даних підстановок на другу.

Приклад 1.7. Нехай дано дві підстановки четвертого степеня і . При підстановці f число 1 переходить в 4, а при підстановці g число чотири переходить в число 2, тобто після послідовного виконання цих двох підстановок 1 перейде в 2. Аналогічно 2®3®4, 3®2®1, 4®1®3. У результаті отримуємо підстановку .

Оберненою підстановкою до підстановки n-го степеня f називається така підстановка n-го степеня g, що добуток цих двох підстановок дає тотожню підстановку: fg = gf = e.

Приклад 1.8. Знайти обернену підстановку до підстановки .

Якщо , то . Перевіримо

 

ОСНОВНІ АЛГЕБРАЇЧНІ СТРУКТУРИ.

Нехай М – довільна множина елементів a, b, c... Під бінарною алгебраїчною операцією, або алгебраїчною операцією в множині М розуміють закон (правило), за яким будь-яким двом елементам a i b цієї множини ставиться у відповідність єдиний елемент із цієї ж множини.

Тут важливою є вимога однозначності операції і вимога її здійснення для будь-яких двох елементів множини М, а також порядок, у якому беруться елементи множини М під час виконання ними операції. Тобто задати алгебраїчну операцію на множині М означає задати відображення .

Приклад 1.9. Додавання і множення на множині натуральних чисел є алгебраїчними операціями, бо для довільних натуральних чисел a i b їхня сума і добуток визначаються однозначно і є знову натуральними числами. Водночас операції віднімання і ділення не алгебраїчні операції у цій же множині натуральних чисел. Справді, якщо взяти, наприклад, числа 5 і 7, то не існує таких натуральних чисел p i q, для яких 5-7=р і 5/3=q.

Для позначення довільної алгебраїчної операції, встановленої на множині М, користуватимемося символом *.

Елемент е з множини М називають нейтральним елементом відносно операції *, якщо для будь-якого елемента m з множини М виконується рівність . Нейтральний елемент відносно алгебраїчної операції додавання, визначеної на множині М, називають нулем, а відносно операції множення – одиницею.

Наприклад, на множині цілих чисел число 0 є нейтральним елементом відносно додавання, а число 1 – нейтральним елементом відносно множення.

Елемент а^-1 з множини М називають оберненим елементом до елемента а відносно операції *, якщо . Елемент а^-1, обернений до елемента а відносно операції додавання називають протилежним до а.

Наприклад, у множині цілих чисел відносно операції додавання кожне число а має (обернене) протилежне число (-а).

Нейтральний елемент є оберненим до себе, бо .

Твердження 1. Якщо відносно операції * на множині М є нейтральний елемент, то він єдиний.

Доведення. Припустимо, що існують два різних нейтральних елемента е₁ ¹ е₂. Тоді е₁ =е₁*е₂ = е₂*е₁= е₂. Звідки е₁ = е₂.

Твердження 2. Якщо відносно операції * на множині М для елемента а існує обернений елемент а^-1, то він єдиний.

Доведення. Припустимо, що для елемента а існують два різних обернених елемента а₁^-1 ¹ а₂^-1. Тоді а₁^-1 = е* а₁^-1 = а*а₂^-1* а₁^-1 = а₂^-1. Звідки а₁^-1 = а₂^-1.

Алгебраїчні операції можуть мати наступні властивості:

1.Асоціативність: для будь-яких елементів а, b і с з М виконується рівність .

2.Існування нейтрального елемента е з М.

3.Існування оберненого елемента а^-1 з М для будь-якого елемента а з М.

4.Комутативність: для будь-яких елементів а і b з М виконується рівність .

Результат виконання алгебраїчної операції на скінченній множині часто задають за допомогою таблиць Келі. Ці таблиці нагадують таблицю множення чисел. Щоб побудувати таблицю Келі для множини М={a, b, …, d} випишемо у стовпчик і у рядок угорі всі елементи множини М, додержуючи одного і того ж порядку, а результат операці x * y - на перетині рядка, який відповідає елементу x та стовпчика, який відповідає елементу y (мал.2.1).

Приклад 1.10. Скласти таблицю Келі групи підстановок множини трьох елементів.

Розв'язок. Введемо позначення:

Тоді таблиця Келі групи така:

	e	a	b	c	d	f
e	e	a	b	c	d	f
a	a	b	e	f	c	d
b	b	e	a	d	f	c
c	c	d	f	e	a	b
d	d	f	c	b	e	a
f	f	c	d	a	b	e

Тому, що

 

Приклад 1.11. Нехай - множина неперервних функцій на множині R. Поставимо у відповідність кожній парі () елементів в С(R) таку функцію яка в кожній точці приймає значення f(x) + g(x), де “ + ” означає звичайне додавання дійсних чисел. Це можна записати так:

Оскільки сума неперервних функцій є функція неперервна, то – алгебраїчна операція.

Приклад 1.12. Розглянемо множину . . Задамо алгебраїчну операцію на цій множині так: якщо то + = тобто, сума двох класів еквівалентності є клас еквівалентності, що містить . Пояснимо це докладніше. Щоб додати цілі числа, і за модулем m (тобто знайти суму ) потрібно спочатку додати їх, а потім знайти остачу від ділення цієї суми на число m. Якщо , то і + = Наприклад, коли m=5 то 3+4=2 (), бо і, отже, + в множині . Далі позначатимемо множину Через .

Приклад 1.13. Нехай дано два відображення та (множини X, Y, Z - довільні). Композицією (добутком) відображень f і g називається таке відображення Інакше кажучи, під композицією відображень розуміємо їх послідовне виконання. Позначимо через S(X) множину всіх сюр’єктивних відображень множини X на себе. На S(X) композиція відображень є алгебраїчною операцією.

ГРУПА.

Непорожня множина G називається групою відносно операції *, якщо виконуються такі властивості (аксіоми групи):

1. Операція * є алгебраїчною на множині G, тобто

: .

2. Операція * є асоціативною, тобто .

3. У множині G існує нейтральний елемент відносно операції *, тобто .

4. У множині G для будь-якого її елемента існує обернений елемент, тобто .

Приклад 1.14. Множина всіх цілих чисел відносно операції додавання є групою, а відносно операції множення ця сама множина не є групою. Справді, операції додавання та множення на множині цілих чисел є алгебраїчними (сумою (добутком) будь-яких двох цілих чисел є відповідне ціле число) та асоціативними ( , ). Роль нейтрального елемента відносно додавання відіграє ціле число 0, а відносно множення - число 1. Оберненим для числа а відносно додавання у множині цілих чисел є протилежне число (-а). А відносно множення обернені елементи існують у множині цілих чисел лише для 1 та -1.

З аксіом груп випливають такі властивості:

Твердження 1. виконується закон скорочення:

- ліве скорочення,

- праве скорочення.

Доведення. Дійсно, якщо , то і , звідки . Отримали . Аналогічно для маємо .

Твердження 2. Для кожної пари елементів існують єдині розв’язки рівнянь та - і .

Єдність розв’язків випливає з законів скорочення.

Група називається скінченною, якщо вона має скінченне число елементів, у протилежному випадку група називається нескінченною. Кількість елементів скінченої групи називається її порядком.

Групу відносно операції множення називають мультиплікативною (від латинського слова multiplication – множення), а відносно операції додавання - адитивною (від латинського слова addition – додавання) групою.

Приклад 1.15. Перевіримо, чи множина підстановок n-го степеня є групою:

1. Операція множення підстановок n-го степеня є алгебраїчною, оскільки будь-яким двом підстановкам f i g n-го степеня ставиться у відповідність єдина підстановка n-го степеня.

2. Операція множення підстановок n-го степеня є асоціативною:

3. У множині підстановок n-го степеня існує нейтральний елемент відносно операції множення підстановок – тотожня підстановка.

4. У множині підстановок n-го степеня для будь-якого її елемента існує обернений елемент – обернена підстановка.

Група підстановок n-го степеня називається симетричною групою степеня n і позначається S_n.

Приклад 1.16. Перевірити, чи є асоціативною операція композиції відображень на множині S(X).

Нехай , відображення. Для всіх маємо:

Отже, . Тому операція композиції відображень на множині S(X) асоціативна.

Приклад 1.17. Перевірити, чи є асоціативною алгебраїчна операція Т на множині R, яка кожній парі (a, b) ставить у відповідність середнє арифметичне чисел a і b. Тобто . Дійсно

Якщо , то

Приклад 1.18. Перевірити, чи є групою множина матриць , де і відносно операції множення матриць.

Дійсно, добуток матриць такого виду знову буде матриця такого ж виду:

=

Нейтральним елементом є одинична матриця, яка одержується при

Обернена матриця існує для кожної матриці такого ж виду:

=

Отже, якщо = , то

Це група не комутативна, бо

=

 

Приклад 1.19. Довести, що множина є абелевою групою відносно додавання за модулем n.

Дійсно ця операція є алгебраїчною та асоціативною, а нейтральним елементом є бо

Оберненим до елемента є елемент , бо . Ясно, що в операція додавання за модулем n комунікативна.

Приклад 1.20. Чи утворює групу множина , якщо на ній операцію Т визначити так:

Розв'язок. Перевіримо асоціативний закон:

Таким чином . І множина відносно так визначеної операції Т групи не утворює.

Приклад 1.21. Чи утворює групу множина , якщо операцію визначити так:

Розв'язок. Асоціативний закон:

Існування нейтрального елемента:

Існування оберненого елемента:

Оскільки для 1Є не існує оберненого елемента, то групи не утворює відносно операції .

Приклад 1.22. Довести, що

а) в довільній групі

б) .

Розв'язок.

а) Дійсно,

Так як обернений елемент єдиний, то а) доведено. Пункт б) пропонуємо довести читачеві самостійно, використавши метод математичної індукції.

Приклад 1.23. Нехай для довільного елемента групи довести, що група комутативна.

Розв'язок. Так як для довільного елемента то для будь-яких елементів і маємо .

Помножимо обидві частини цієї нерівності зліва на і справа на . Одержимо:

Так як і , то і . Але і довільні елементи групи , тому група - абелева.

 

ПІДГРУПИ

Не порожня множина H групи G називається підгрупою, якщо вона є групою відносно визначеної в групі G операції.

Зауважимо, що не підмножина групи G є підгрупою. Розглянемо, наприклад підмножину групи Тут . Отже сума деяких елементів множини А їй не належать. Якщо тепер множину А розглядати у відриві від групи, але з операцією, яка була визначена в групі, то не для всіх елементів цієї множини існує сума.

Критерій підгрупи.

Твердження. Підмножина Н групи G є підгрупою тоді і лише тоді, коли:

а) для довільних : ;

б) для кожного : .

Справді, умова а) дозволяє ввести на множині ту ж саму операцію,яка була в групі G разом з властивістю асоціативності.

Умова б) забезпечує існування обернених елементів в . Нарешті, з умов а) і в) випливає, що нейтральний елемент групи належить до

:

Умови а) і б) можна замінити одною:

.

Пропонуємо, як вправу, довести, що а), б) г).

Приклади підгруп: а) Кожна група G має так звані тривіальні підгрупи: і G.

б) В ланцюгу кожна попередня група є підгрупою наступної.

в) В групі підгрупою є множина .

г) В групі C(R) підмножина многочленів є підгрупою.

Приклад 1.24. Знайти всі підгрупи .

Розв'язок. Це дві тривіальні групи: , . Підгрупа парних підстановок з таблицею Келі

	e a b
a b	a b e b e a

Три підгрупи другого порядку:

З однаковими таблицями Келі:

	e с..
e c	e с c e

 

СУМІЖІ КЛАСИ. ТЕОРЕМА ЛАГРАНЖА.

Нехай H підгрупа групи G. Задамо відношення на групі G. Вважатимемо, що , тобто два елементи еквівалентні, якщо добуток . Покажемо, що відношення еквівалентності.

а) бо (бо H – підгрупа).

б) Якщо , то . Дійсно, з того, що випливає, що і .

Однак , бо =

в) Покажемо, що з і випливає .

Нехай і тоді , бо підгрупа. Однак = .

З а), б), в) випливає, що відношення еквівалентності на групі G. За теоремою 2.5 групі G розбивається на класи, що не перетинаються:

Кожен такий клас складається з тих елементів , що. . Іншими словами, коли для деякого , або .Отже, класи еквівалентності – це множини .

Наприклад. а)Нехай група цілих чисел, кратних числу 3. Суміжний клас, утворює число 1 є множиною 1+3 Це всі цілі числа, які при діленні на 3 дають остачу 1. Зрозуміло, що існують тільки 3 рівні класи групи за підгрупою

б) Нехай , .Суміжний клас, утворений елементом в бо