Підсистеми, Дискретна математика
Нехай A = (A, Ω, П) — довільна система алгебри і В ⊆ А — непорожня безліч.
Безліч В називаютьзамкнутим щодо операцій з Ω (Ω-замкненим безліччю ), якщо результат застосування будь-якої n-арної операції з Ω до будь-яких елементів з належить В, тобто. для будь-якої n-арної операції і будь-яких елементів а1, . аn ∈ елемент ω(a1, . an) ∈ B.
Наприклад, у напівгрупі (ℕ, +) підмножина парних чисел замкнута щодо операції додавання, а підмножина непарних чисел не замкнута. У кільці цілих чисел підмножина натуральних чисел замкнута щодо операцій складання та множення, але не замкнута щодо операції взяття протилежного елемента.
Алгебраїчну систему В = (B, Ω, ПB), де В ⊆ А, називаютьпідсистемою алгебраїчної системи A, якщо В Ω-замкнуто і ПB є безліч обмежень на всіх відносин з П: ПB = B: p ∈ П>.
Очевидно, що алгебраїчні системи A та В однотипні, і часто замість ПB будемо в такому випадку писати просто П.
ЯкщоA — алгебра, то будь-яку її підсистему називають її подалгеброю (точніше, Ω-подалгеброю).
Зауваження 4.2. У визначенні Ω-подалгебри потрібна лише замкнутість щодо операцій з Ω. Якщо ж ми хочемо, щоб при переході до подалгебри „успадковувалися” якісь спеціальні властивості операцій вихідної алгебри, то це потрібно спеціально обговорювати. Саме так ми й чинили, визначаючи поняття підгрупи, підкільця, підполя тощо. визначити і через властивість замкнутості, але лише в тому випадку, якщо в сигнатуру групи включити не тільки одну бінарну операцію „множення” (яка має спеціальні „групові властивості”, див. 2.2), але також унарну операцію взяття зворотного елемента танульарну операцію – одиницю групи.
Аналогічно, виключно через вимогу замкнутості можна визначити поняття підмоноїда. Отже, таким чином можна визначити і підкільце.
Складніша ситуація з тілом і полем. Ми не можемо визначити поле як алгебру з сигнатурою 0,1, де операція - є операція обчислення протилежного елемента (зворотного за додаванням), а операція 1 - операція обчислення зворотного елемента по множенню, так як остання операція є часткове відображення і не визначено для елемента0. Тому вона не може бути введена в алгебри сигнатури, за визначенням містить тільки всюди визначені- певні операції.
Звернімо увагу і на те, що переходячи до Ω-замкнутого підмножини, ми можемо отримати алгебру як збагачену новими властивостями операцій сигнатури Ω, так і деякі з властивостей, що втратила. Наприклад, моноід (ℕ0, +, 0) буде лише підмоноїдом групи (ℤ, +, 0) (але не підгрупою), а підмоноїд бієкцій у симетричному моноїді деякої нескінченної множини буде вже групою (це не підгрупа, а саме підмоноїд, що є групою !). #
У наступній теоремі сформульовано просту, але дуже важливу властивість замкнутих підмножин.
Теорема 4.1. Непусте перетин довільного сімейства Ω-замкнутих підмножин Ω-замкнуто.
◀Для простоти розглянемо доказ для перетину двох Ω-замкнутих підмножин.
Нехай в алгебрі (А, Ω) Ω-замкнуті підмножини В1 та B2 мають непустий перетин. Тоді для будь-якого n ≥ 0, а також будь-яких (не обов'язково різних) a1, . аn ∈ В1 ∩ B2 елемент ? . аn)∈ В1 і ω(a1, . аn) ∈ В2. ▶
Розглянемо алгебру A = (А, Ω) та підмножину B ⊆ A, не обов'язково Ω-замкнуте.
З теореми 4.1 випливає, що існує Ω-замкнене підмножина, що збігається з перетином всіх Ω-замкнутих підмножин, що містять В. Його називають замиканням підмножини щодо операцій з Ω (або Ω-замиканням підмножини В) і позначають [B]Ω. Хоча б одне Ω-замкнене підмножина, що містить В, обов'язково знайдеться - весь носій А. У тому випадку, коли [B]Ω = А, підмножина В називають системою утворюють алгебри А=(А,Ω), а її саму називають алгеброю, породженою безліччю В. Алгебру, яка має кінцеву систему утворюючих, називають звичайно породженою.
Примітка 4.3. Визначення замикання можна уявити й у дещо іншій формі, яка змістовно асоціюється з деякою процедурою побудови множини [B]Ω по кроках.
Визначимо сімейство множин (Bi)i≥0, B0 = B, a
Таким чином, безліч B1 складається з усіх елементів B0 = і до них додаються всі елементи, які можуть бути отримані як результат застосування операцій сигнатури Ω до аргументів операції з В0. Безліч В2 так само містить всі елементи множини В1 плюс всі результати застосування операцій з Ω до аргументів з В1 і т.д. За визначенням, В = В0 ⊆ В1 ⊆ В2 ⊆ . ⊆ Вi ⊆ Вi+1 ⊆ . тобто. для будь-якого i ≥ 0 мають місце включення Вi ⊆ Вi+1 і Вi ⊆ [B]Ω ⊆ A. Можна показати, що
Замкнутість означає з точки зору такого визначення, що всі множини Ві збігаються з безліччю В. Крім того, може виявитися, що процес утворення множин Вi "оборветься на деякому кроці", тобто знайдеться таке i, що Вi +1 = Вi .Тоді Вi = [B]Ω.
Для кінцевої алгебри описану вище процедуру можна розглядати як алгоритм побудови замиканнявихідної множини (при тому, що кожній операції зіставлено якийсь алгоритм її обчислення). На першому кроці алгоритму замикання [B]Ω поміщають всі елементи множини, а потім застосовують операції сигнатури Ω до вихідних і знову одержуваних елементів до тих пір, поки не перестануть з'являтися нові елементи.
Інакше це можна описати так:
1) всі елементи множини В0 вважаються і елементами замикання Ω;
2) які б не були елементи b1, . bn, щодо яких відомо, що вони належать [B]Ω (тобто якійсь множині Bi з певного вище сімейства), до наявних елементів замикання [B]Ω додають всі елементи ω(b1, . bn) для довільної n -арної операції ω сигнатури Ω.
Ніякі інші елементи, крім тих, що можуть бути отримані вище розглянутим способом, замиканню [B]Ω не належать.
Образно кажучи, В - це "деталі конструктора", a [B]Ω - все, що можна зібрати з цих деталей за деякими заздалегідь обумовленими "правилами складання" (якими є операції сигнатури Ω). #
Розглянемо приклади побудови Ω-замикання.
Приклад 4.2. а. В алгебрі (ℕ, +) візьмемо одноелементну множину В = = В0. Тоді В1 = , В2 = , В3 = і т.д. Безліч Вi при i ≥ 1 складається зі всіх сум виду m + m, де m, n ∈ Bi-1. Неважко помітити, що Bi = , де k = 2 i-1 , i ≥ 0. Зрозуміло, що в даному випадку і, таким чином, безліч є системою, що утворює цю алгебру.
б. У мультиплікативної групі відрахувань за модулем 23 (тобто. у групі Z * 23 ) побудуємо замикання множини В = , вважаючи, що сигнатура групи складається з єдиної операції множення (за модулем 23).
Оскільки в цій алгебрі сигнатура складається з однієї операції, а вихідна безліч також одноелементно, то замикання буде складатися з усіхступенів елемента 3. Отже, для побудови замикання множини У цьому випадку досить обчислювати послідовно ступеня (за модулем 23) елемента 3. Маємо
3 2 = 9, 3 3 = 4, 3 4 = 4⋅3 = 12, 3 5 = 12⋅3 = 13,
З 6 = 13⋅3 = 16, 3 7 = 16⋅3 = 2, З 8 = 2⋅3 = 6,
З 9 = 6⋅3 = 18, 3 10 = 18⋅3 = 8, 3 11 = 8⋅3 = 1.
Оскільки отримана одиниця, то „коло замкнулося", і тим самим обчислено замикання множини. Зауважимо, що в цьому випадку безліч В1 складається з усіх ступенів трійки, починаючи з першого і закінчуючи другий, безліч В2 — з усіх ступенів, починаючи з першого і кінчаючи четвертою, безліч В3 - з усіх ступенів з першої по восьму, а безліч В4 - з усіх ступенів з першої по 16-й, але оскільки починаючи з 12-го ступеня елементи повторюються, тобто 3 12 = 3, 3 13 = 32, З 14 = 33, 3 15 = 34 і, нарешті, 3 16 = 35, то вже безліч В5 збігатиметься з безліччю B4, так що в даному випадку [B] = В4 .
Породжена безліччю група збіглася з циклічною підгрупою групи ℤ23 з утворюючим елементом 3. Цей результат легко узагальнити, довівши, що для довільної кінцевої групи g = (G, ⋅), що розглядається як алгебра з сигнатурою, що складається тільки з операції множення, її циклічна підгрупа з утворюючим елементом збігається з підгрупою, породженою безліччю . #
Циклічна група є одним із найважливіших прикладів звичайно породженої алгебри.
У зв'язку з цим звернемо увагу на одну тонкість. Якщо g — циклічна група з утворюючим елементом а, її, взагалі кажучи, не можна розглядати як алгебру з системою утворюючих . Усе залежить від конкретної сигнатури груп-групи. Справді, якщо сигнатуру групи включити лише множення, то нескінченної циклічної групи 1 ≠ а n будь-якого позитивного n. Тому замикання множинищодо множення не містить одиниці. Якщо ж сигнатуру групи як алгебри доповнити унарною операцією взяття зворотного, тобто. зведення в ступінь -1, то циклічна група з утворюючим елементом а буде алгеброю із системою утворюючих. За такого підходу адитивна група цілих чисел, що розглядається як алгебра (ℤ, +, -, 0), є нескінченна циклічна група, породжена безліччю .
Приклад 4.3. а. Алгебра (ℤ, ⋅, 1) (мультиплікативний моноід кільця цілих чисел) не є звичайно породженою. Справді, у цьому моноіді у систему утворюючих необхідно включити всі прості числа, оскільки жодне їх не можна уявити як добуток інших чисел. Але безліч простих чисел нескінченна.
б. Будь-яка кінцева алгебра буде, зрозуміло, і звичайно породженою. Зокрема, будь-яке кільце відрахувань за модулем до (поле відрахувань при простому k) — звичайно породжена алгебра, навіть якщо в сигнатурі немає операції знаходження зворотного елемента.
в. Вільний моноід, породжений кінцевою множиною (алфавітом) А є звичайно породжена (і нескінченна) алгебра, система утворюють яку дорівнює А ∪ , де А - порожній кортеж.
г. Хорошим прикладом замикання служить лінійна оболонка заданої множини векторів довільного лінійного простору [IV]. Як відомо, лінійна оболонка V множини векторів x1, . хm лінійного простору L є безліч всіх лінійних комбініцій виду , де xi ∈ V, i = 1, m, m ≥ 1. Лінійна оболонка замкнута щодо операцій складання векторів та множення вектора на число, оскільки лінійна оболонка безлічі векторів є лінійним підпростором. Більш того, лінійна оболонка V множини векторів x1, . хm - це найменше (щодо відношення включення множин) замкненемножина, що містить задану множину векторів, оскільки будь-яка замкнута множина, що містить вектори x1, . хm, містить і їх лінійні комбінації, тобто. включає в себе V. Зазначимо, що кінцевий лінійний простір - звичайно породжена алгебра, так як воно є лінійною оболонкою будь-якого зі своїх базисів.