§1. Основні поняття алгебри.
1.1. Початкові поняття.
Як починається будь-яка казка? У тридев'ятому царстві у тридесятій державі жили-були… Не тільки в казках, а й у математиці та програмуванні важливе оточення, де розгортається вся дія – охоплюючий універсум, середовище програмування.
Два наші основні об'єкти - це числа та багаточлени. Де вони живуть? Як зазвичай прийнято в математиці, вони «живуть» в деякій множині, яка називається алгебраїчною системою.
Алгебраїчна система- це непорожня множина, в якій задана одна або кілька алгебраїчних операцій.
Що таке операція алгебри? Їх дуже багато, нам знадобиться бінарна операція алгебри.
Бінарною операцією алгебрина множині А називається будь-яке відображення, яке кожній парі елементів з множини А ставить у відповідність елемент множини А.
У цьому сенсі суми чи добутку чисел, многочленів чи матриць є алгебраїчними операціями. Бінарні операції алгебри зазвичай називають додаванням або множенням. Це скорочення для довгої тиради «бінарна операція алгебри». Позначають їх також по-різному. Наведемо найпоширеніші позначення: +, ·, ×, •, , , *.
Якщо безліч А містить 10 елементів, то пар елементів буде 100. Так як будь-якій парі з 100 можна поставити у відповідність будь-який з 10 елементів, то загальна кількість різних операцій алгебри на множині з 10 елементів буде дорівнює 10 100 . Як відомо атомів у видимій частині всесвіту приблизно 10 50 тому вивчати всі алгебраїчні операції немає ніякої можливості.
Визначення.Алгебраїчна операція «+» називається:
має нейтральний елемент, якщоe+a=a+e=a;
що має оборотні елементи, якщо
Дуже небагато з алгебраїчних операцій мають хоча б одну з перерахованих вище властивостей, а тим більше всіма чотирма.
На безлічі натуральних чисел введемо нову операцію алгебри
Приклад 2.На множині натуральних чисел з доданим нулем введемо нову операцію
Визначення.Якщо на множині А задана асоціативна алгебраїчна операція, то така множина називаєтьсянапівгрупою.Якщо ця операція комутативна, то напівгрупа називаєтьсякомутативною.
Приклад 3.Безліч натуральних чисел щодо операції звичайного додавання є комутативною напівгрупою.
Визначення.Якщо на множині А задана асоціативна алгебраїчна операція з нейтральним елементом, то така множина називаєтьсянапівгрупою з одиницеюабомоноїдом. Якщо ця операція комутативна, то моноїда називається комутативним.
Приклад 4.Безліч натуральних чисел щодо операції звичайного множення є комутативним моноїдом. Якщо до натуральних чисел додати нуль, ми отримаємо коммутативний моноід і за додаванням.
Оскільки формальним додаванням нейтрального елемента будь-яку напівгрупу можна перетворити на моноід, то ці поняття часто не розрізняють.
Визначення.Якщо на множині А задана асоціативна операція, що має нейтральний елемент і всі її елементи мають зворотні, то множина А називаєтьсягрупою. Якщо операція ще й комутативна, то група називаєтьсякоммутативнойабоабелевойна честь Нільса Хенріха Абеля (1802-1829).
Приклад 5. Безліч цілих чисел щодо операції звичайного додавання є комутативною групою. Безліч ненульових цілих чисел щодо операції звичайного множення є комутативним моноїдом, але з групою.
Приклад 6. Безліч ненульових раціональних чисел щодо операції звичайного множення є комутативною групою.
Як назвати операцію алгебри - додаванням або множенням, в тому випадку, якщо вона одна єдина, зовсім не важливо. Але якщо операцій дві, то додаванням зазвичай називають ту, яка коммутативна.
Тепер перейдемо до систем алгебри, на яких задані дві алгебраїчні операції. Якщо ці операції ні як одна з одною не взаємодіятимуть, то нічого істотно нового не виникне. Є інопланетяни на Землі чи ні, зовсім не важливо, оскільки вони не втручаються у наше життя.
Визначення.Нехай на множині А задано дві операції алгебри. Одна з операцій є асоціативною, комутативною, має нейтральний елемент і всі елементи множини мають зворотні. Назвемо її додаванням. Друга операція, яка називається множенням асоціативна. Між собою операції пов'язані законом дистрибутивності
(a+b)c=ac+bc,c(a+b)=ca+cb,
І тут безліч А називається кільцем. Якщо множення комутативно, то кільце називається комутативним.
До речі, комутативні кільця абелевими ніколи не називають.
Більш точно, введена нами дистрибутивність називається дистрибутивністю складання щодо множення. Операції у цій властивості нерівноправні. Якби виконувалася і дистрибутивність множення щодо складання, то були б вірні формули
.
Поєднуючи разом обидві дистрибутивності, отримуємо
.
Якщо кільце містить нейтральний елемент за множенням, його зазвичай називають одиницею і позначають 1 (не плутати з числом 1), то підставляючи
с=1, отримаємо, що . Явна суперечність. Отже, справедливість, тобто. симетричність визначення кільця щодо додавання та множення, неможлива принципово.
Приклад 7.Безліч цілих чисел щодо звичайних операцій складання та множення є комутативним кільцем.
Приклад 8.Нехай К – кільце, безліч многочленів K[x] від змінноїхз коефіцієнтами з кільця До щодо звичайних операцій складання та множення багаточленів є кільцем. Якщо кільце К комутативно, те й кільце K[x] теж комутативно.
1. Якщо нейтральний елемент існує, він єдиний.
2. Якщо операція асоціативна і в елементааіснує зворотний елемент, він теж єдиний і позначається «-а», якщо операція називається додаванням, і «а-1» або «1/a», якщо операція називається множенням.
3. У кільці для нейтрального елемента по додаванню, званого нулем, виконується рівність .
4. У кільці для зворотних елементів по додаванню виконується рівність .
1. Припустимо, є два нейтральні елементиxіy, тоді за визначенням нейтрального елементаxмаємоxy=yі, з іншого сторони,xy = x. Значить, x=y .
2. Нехай «b» та «c»- Елементи зворотні елементу «а». В силу аксіоми асоціативності маємоb=b1=b(ас)=(ba)с=1с=с.
3. Маємо, 0а=(0+0)а=0а+0а, отже, 0а=0. Зазначимо, що в цьому доказі використовувалася аксіома нейтрального елемента за додаванням, аксіома наявності зворотного за додаванням, дистрибутивність та неявно асоціативність за додаванням. Усього чотири аксіоми.
(До речі, при скороченні обох частин на елемент 0а, яке ми справили в одну дію, насправді використовувалося три аксіоми – наявність зворотного за складання, асоціативність додавання, аксіома нейтрального елемента. Докладно це виглядає так. Нехай «b» - елемент зворотний до додавання елемента 0а, тоді з 0а=0а+0а, слід
4. Спочатку доведемо, що (-а)b=-(ab). Для цього потрібно перевірити, що елемент (-a)bє оберненим за додаванням до елементаab. Справді, ab+ (-а)b=(a-a)b=0а=0. Тут використовувалася дистрибутивність, властивість зворотного за додаванням та властивість нуля, а також пункт 3 нашого доказу.
Тепер, використовуючи щойно отриманий результат, обчислюємо
Пізнавальний сенс слідства у цьому, що пояснює, чому за множенні на 0 завжди виходить 0 і чому «мінус на мінус дає плюс». Обидві ці властивості виконуються, якщо вірні чотири аксіоми: асоціативність додавання, дистрибутивність, наявність нейтрального елемента та зворотного елемента по додаванню.
З погляду програмування доведене вище слідство те саме дуже корисно. Аксіоми - це асемблерні команди, елементарні операції, апаратно реалізовані в процесорі. Наші звичні перетворення, наприклад, приведенняподібних членів або множення на 0 - це команди мови високого рівня. Ми фактично виступили в ролі компілятора. Це корисно зробити хоча б один раз, що при зміні середовища програмування означає, що потрібно переробляти.
Приклад 9.Нехай К - кільце, Mn(K) - безліч квадратних матриць розміруn×nз коефіцієнтами з кільця К Щодо звичайних операцій складання та множення матриць Mn(K) є кільцем.
Зазначимо, що на відміну від кільця багаточленів К[8>x ] кільце Mn(K) не успадковує комутативність від кільця коефіцієнтів К.
Приклад 10.Розглянемо безліч залишків (відрахувань)
Zn=n-1> від розподілу на натуральне числоn.Введемо на ньому операції складання та множення
,
деa+bіabпозначають звичайні додавання та множення цілих чисел.
Щодо введених операцій безліч Znє комутативним кільцем з одиницею.
Найменше кільце, і улюблене програмістами, це кільце Z2 = відрахувань по модулю 2. Надалі ми використовуватимемо позначення , , а користуватися звичною плюсом і точкою.
Попередження.Нерідко вважають, що якщоn>m, то кільце Znмістить кільце Zm. Це шкідлива помилка. Звичайно, зовні кільце Z5= виглядає як підмножина кільця Z8=. Однак, у першому кільці 3·3=4, 3+3=1, а у другому 3·3=1, 3+3=6. Елемент 3 у першому кільце відрізняється від елемента 3 у другому, як Вася Петров від Васі Іванова. Це омоніми – слова, що однаково звучать, з різним змістом.
І завершимо наше коротке введення алгебри визначенням поля.
Визначення.Комутативне кільце з одиницею, в якому всі ненульові елементи мають зворотний помноження, називається полем.
Приклад 11.БезлічQраціональних чисел зі звичайними операціями складання та множення є полем.
БезлічRдійсних чисел із звичайними операціями складання та множення є полем.
Кільце відрахувань Zp, деp- будь-яке просте число, є полем. (Це ми доведемо пізніше).
Перевірити, що кільце многочленів K[x] не є полем. (Підказка. Який багаточлен є зворотним до багаточленах2 за множенням?).
Перевірити, що кільце матриць Mn(K) приn>1 не є полем.