Бiнарнi вiдношення. Вiдношення порядку. Курiнний Г.Ч. Невмержицька О.М. Шугайло О.О. Травень — 2015 Змiст 1 Бiнарнi вiдношення 1.1 Запис. Використання. Приклади . . . . . . . . . 1.2 Операцiї над бiнарними вiдношеннями . . . . . . 1.3 Властивостi бiнарних вiдношень . . . . . . . . . 3 3 4 8 2 Вiдношення порядку 9 2.1 Вiдношення часткового та лiнiйного порядку . . 9 2.1.1 Означення та приклади . . . . . . . . . . 9 2.1.2 Найбiльший, найменший, максмальний та мiнiмальний елементи . . . . . . . . . . . 11 2.1.3 Алфавiтниий порядок та порядок на прямому добутку двох чвм . . . . . . . . . . 12 2.1.4 Використання лiнiйного порядку в iнформатицi . . . . . . . . . . . . . . . . . . . . 14 2.1.5 Нетранзитивнi вiдношення “краще“ та “сильнiше“ . . . . . . . . . . . . . . . . . . . . . 15 2.2 Дiаграми . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Дiаграми скiнченних чвм . . . . . . . . . 16 1 Лiнiйний та деревоподiбний порядок на скiнченних множинах . . . . . . . . . . . 2.2.3 Ключi в iнформатицi, в базах даних . . . 2.2.4 Ключi в iнформатицi, в криптографiї . . 2.3 Iзоморфiзм частково впорядкованих множин . . 2.3.1 Означення та приклади . . . . . . . . . . 2.3.2 Сортування. Сiм фундаметальних алгоритмiв сортування. . . . . . . . . . . . . . 2.4 Верхнi та нижнi межi . . . . . . . . . . . . . . . 2.4.1 Означення та позначення . . . . . . . . . 2.4.2 Властивостi операцiй знаходження точної верхньої та точної нижньої межi. . . . . . 2.4.3 Напiвгратки та гратки. . . . . . . . . . . 3 Гратка пiдалгебр унiверсальної алгебри 3.1 Найменше пiдкiльце на найменше пiдполе . . . . 3.2 Найменша пiднапiвгрупа . . . . . . . . . . . . . 3.3 Найменша група . . . . . . . . . . . . . . . . . . 3.4 Найменше пiдполе, що мiстить заданий елемент 3.5 Найменша пiднапiвгрупа, що мiстить заданий елемент . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Найменша група, що мiстить заданий елемент . 3.7 Найменший пiдунар, що мiстить заданий елемент 3.8 Алгоритм знахоження всiх пiдалгебр заданої унiверсальної алгебри . . . . . . . . . . . . . . . . . 3.9 Забороненi гратки . . . . . . . . . . . . . . . . . 4 Ординальнi числа. 4.0.1 Цiлком впорядкованi множини . . . . . . 4.0.2 Мотивацiя вивчення ординалiв . . . . . . 4.0.3 Ординали, ординальнi числа. . . . . . . . 2 2.2.2 18 20 22 23 23 25 38 38 41 43 46 51 56 56 57 58 58 59 59 64 65 65 69 70 1 1.1 Бiнарнi вiдношення Запис. Використання. Приклади Нижче розглядаємо бiнарнi вiдношення R ⊆ A2 на певнiй множинi A. Те, що два елементи a, b ∈ A знаходяться у вiдношеннi R, крiм стандартного запису (a, b) ∈ R, який в iсторичному масштабi з’явився лише сьогоднi вранцi, використовувалися i використовуються i iншi: • R(a, b) — префiксний кембрiджський запис; • Rab — префiксний польський запис; • abR — зворотний постфiксний польський запис; • aRb — iнфiксний запис; • (a, b)R — постфiксний запис з дужками. Вибiр того чи iншого запису для бiнарного вiдношення диктується традицiєю, мовним оточенням i вподобаннями того, хто цей запис використовує. Так, для вiдношення < традицiя вимагає писати a < b а не (a, b) ∈<. А мова програмування ЛIСП вимагає те ж саме записувати у виглядi < (ab). Вибiр тiєї чи iншої форми запису для бiнарного вiдношення може надавати тi чи iншi переваги транслятору програми чи аналiзатору програми в програмуваннi. Вибiр форми запису в текстi висловить повагу чи байдужiсть автора до читача. Звернемо увагу, що бiнарнi вiдношення вельми часто зустрiчаються в обчислювальних системах, зокрема в реляцiйних1 базах даних. Вiдмiтимо три бiнарнi вiдношення на множинi A 1 Англiйською мовою relation — вiдношення 3 1. порожнє вiдношення ∅, воно визначається умовою ∀x, y ∈ A(¬((x, y ) ∈ ∅)); 2. вiдношення рiвностi = або дiагональ ∆, це вiдношення визначається умовою ∀x, y ∈ A((x, y ) ∈ ∆ ⇔ x = y ); 3. унiверсальне вiдношення A2 , воно визначається умовою ∀x, y ∈ A((x, y ) ∈ A2 ). 1.2 Операцiї над бiнарними вiдношеннями Над бiнарними вiдношеннями можна виконувати звичайнi теоретикомножиннi операцiї — перетин, об’єднання, рiзниця, симетрична рiзниця, доповнення — унiверсальною множиною вважається A2 . Крiм того, на множинi бiнарних вiдношень (на заданiй множинi A) визначено операцiю множення (чи композицiї, чи суперпозицiї). Якщо R1 , R2 ⊆ A2 два бiнарнi вiдношення, то добутком R3 = R1 · R2 = R1 R2 називають вiдношення (a, b) ∈ R3 ⇔ ∃c((a, c) ∈ R1 ∧ (c, b) ∈ R2 ). Для прикладу, нехай A = R i (a, b) ∈ R1 ⇔ a2 + b2 = 1, тобто R1 це коло радiуса 1, а (a, b) ∈ R2 ⇔ (a > 0 ∧ b > 0, тобто R2 є першим квадрантом. 4 (1) (2) 6 6 6 1- 1- 1- Рис. 1: Добутком кола на кквадрант є смуга Тодi (a, b) ∈ R1 R2 ⇔ ∃c(a2 + c2 = 1 ∧ c > 0 ∧ b > 0. Таким чином (див. рис. 1.2), R1 R2 = {(a, b)| − 1 < a < 1, b > 0}. Подiбним чином R2 R1 = {(a, b)|0 < a, −1 < b < 1}. Множина разом iз бiнарною операцiєю в цiй множинi називається магмою або групоїдом. Оскiльки бiнарнi вiдношення на заданiй множинi можна множити, то сукупнiсь бiнарних вiдношень на цiй множинi є магмою або групоїдом. Теорема 1.1 Множення вiдношень асоцiативне, тобто для будь-яких трьох бiнарних вiдношень α, β, γ на заданiй множинi A виконується рiвнiсть (α · β ) · γ = α · (β · γ ). 5 (3) Доведення. Нехай A — деяка множина i α, β, γ ⊆ A2 — три бiнарнi вiдношення на цiй множинi. Потрiбно довести, що для будь-яких a, b ∈ A (a, b) ∈ (α · β ) · γ ⇔ (a, b) ∈ α · (β · γ ). (4) За визначенням множення вiдношень (a, b) ∈ (α · β ) · γ тодi i тiльки тодi, коли для деякого y ∈ A (a, y ) ∈ (α · β ) i (y, b) ∈ γ, а (a, y ) ∈ (α · β ) тодi i тiльки тодi, коли для деякого x ∈ A (a, x) ∈ α i (x, y ) ∈ β. Отже (a, b) ∈ (α · β ) · γ тодi i тiльки тодi, коли для деяких x, y ∈ A (a, x) ∈ α, (x, y ) ∈ β i (y, b) ∈ γ. (5) Подiбним чином (a, b) ∈ α · (β · γ ) тодi i тiльки тодi, коли для деякого x ∈ A (a, x) ∈ α i (x, b) ∈ β · γ, а (x, b) ∈ β · γ тодi i тiльки тодi, коли для деякого y ∈ A (x, y ) ∈ β i (y, b) ∈ γ. Отже (a, b) ∈ α · (β · γ ) тодi i тiльки тодi, коли для деяких x, y ∈ A (a, x) ∈ α, (x, y ) ∈ β i (y, b) ∈ γ. (6) Iз (5) i (6) випливає (4) Множину разом iз асоцiативною бiнарною операцiєю називають напiвгрупою. 6 Використовуючи введене означення, теорему 1.1 можна переформулювати наступним чином. Теорема 1.2 Сукупнiсть бiнарних вiдношень на заданiй множинi разом iз операцiєю множення утворює напiвгрупу. Прикладом напiвгрупи є множина натуральних чисел разом iз операцiєю множення. Натуральнi числа разом iз операцiєю додавання також утворює напiвгрупу. Число 0 та число 1 у множинi дiйсних чисел видiляються властивостями ∀x ∈ R(1x = x1 = x), ∀x ∈ R(0x = x0 = 0). У напiвгрупi бiнарних вiдношень також є елементи, що мають подiбнi властивостi — їх називають нулем та одиницею напiвгрупи. Для вiдмiчених бiнарних вiдношень ∅, ∆ i для довiльного бiнарного вiдношення α ⊆ A2 можна записати ∅ · α = α · ∅ = ∅; i ∆ · α = α · ∆ = α. З кожним бiнарним вiдношенням R пов’язують вiдношення R−1 : (a, b) ∈ R−1 ⇔ (b, a) ∈ R. Вiдношення R−1 називають оберненим до R. Нехай, для прикладу, маємо множину R дiйсних чисел. Уявляємо її як дiйсну пряму. Тодi R2 уявляємо як площину iз прямокутною системою координат. Вiдношенням буде будь-яка пiдмножина площини. Два вiдношення будуть взаємно оберненими, коли множини на площинi симетричнi вiдносно бiсектриси 7 (7) (8) 1-3 координатних кутiв. На множинi дiйсних чисел вiдношення R1 , R2 , що заданi властивостями (1),(2), самi до себе оберненi, тобто симетричнi, а вiдношення R1 · R2 , що задане властивостями (3), само до себе не обернене, не симетричне. 1.3 Властивостi бiнарних вiдношень Вiдношення R на множинi A називають • рефлексивним, коли ∆ ⊆ R, тобто коли ∀x(x, x) ∈ R. На множинi студентiв вiдношення “студент x вчиться iз студентом y в однiй групi“ є рефлексивним, тому що кожен студент сам з собою вчиться в однiй групi. • транзитивним, коли R2 ⊆ R, тобто коли ∀x, y, z ∈ A((x, y ) ∈ R ∧ (y, z ) ∈ R ⇒ (x, z ) ∈ R). Вiдношення “вчитись в однiй групi“ є транзитивним, а “бути сусiдом“ не обов’язково транзитивне вiдношення. • симетричним, коли R−1 = R, тобто коли ∀x, y ∈ A((x, y ) ∈ R ⇔ (y, x) ∈ R). Вiдношення “бути сусiдом“ симетричне. А вiдношення “ x подобається y “ не обов’язково симетричне. • антисиметричним, коли R ∩ R−1 = ∅, тобто коли (x, y ) ∈ R ⇒ (y, x) ∈ / R. Вiдношення “сидiти справа“ антисиметричне. Антисиметричним буде також вiдношення “ x є власною пiдмножиною множини y “. • антирефлексивним, коли R ∩ ∆ = ∅, тобто коли ∀x(x, x) ∈ / R. Вiдношення “не дорiвнюати самому собi“ є антирефлексивним. 8 2 2.1 2.1.1 Вiдношення порядку Вiдношення часткового та лiнiйного порядку Означення та приклади Вiдношення R називають вiдношенням строгого часткового порядку, якщо воно транзитивне, антисиметричне i антирефлексивне; вiдношенням строгого лiнiйного порядку, коли воно тринзитивне, антисиметричне, антирефлексивне, i для будь-яких x, y ∈ A або (x, y ) ∈ R або (y, x) ∈ R. вiдношенням нестрогого часткового порядку, якщо воно одержується iз часткового строгого порядку об’єднанням з дiагоналлю; вiдношенням нестрогого лiнiйного порядку, якщо воно одержується iз лiнiйного строгого порядку об’єднанням з дiагоналлю. Вiдношення “бути власною пiдмножиною“ — це вiдношення строгого часткового порядоку. А вiдношення “бути пiдмножиною“ — це вiдношення нестрогого часткового порядку. Вiдношення < та ≤ є вiдношеннями строгого та нестрогого лiнiйного порядку на множинi цiлих чисел. Можна перевiрити, що оберненим до часткового строгого порядку є вiдношення часткового строгого порядку; оберненим до часткового нестрогого порядку є вiдношення часткового строгого порядку; оберненим до лiнiйного строгого порядку є вiдношення лiнiйного строгого порядку; оберненим до лiнiйного нестрогого порядку є вiдношення лiнiйного нестрогого порядку. 9 Вiдношення часткового нестрого порядку частiше всього позначають ≤ i називають його “менше або дорiвнює“. З використанням цього позначення визначення часткого нестрогого порядку запишеться так • x ≤ x для будь-якого елемента x ∈ A ; • якщо x ≤ y i y ≤ x, то x = y ; • якщо x ≤ y i y ≤ z , то x ≤ z . Обернене вiдношення до “менше або дорiвнює“ називається “бiльше або дорiвнює“. Це вiдношення позначається ≥. Вiдповiдно, для строгого часткового i лiнiйного порядку використовується позначення <, яке називається “строго менше“. Обернене до вiдношення “строго менше“ називається “строго бiльше“ i позначається >. Множина A разом iз вiдношенням часткового порядку ≤ називається частково впорядкованою множиною i позначається ⟨A; ≤⟩ . Те, що в рiзних частково впорядкованих множинах рiзнi вiдношення порядку позначаються однаково, звичайно не приводить до непорозумiнь. Якщо ж така унiфiкацiя створює незручностi, то потрiбно для рiзних вiдношень порядку вживати рiзнi познаення — наприклад, можна використовувати знаки ≤1 , ≤2 , ≤3 , . . . . Для прикладу, на триелементнiй множинi , ⋆, △ в один i той же час можна використовувати порядок △ ≤1 ≤1 ⋆, i порядок ⋆ ≤2 △ ≤ 2 . Iснує традицiя довгу словосполуку “частково впорядкована множина“ замiняти абревiатурою чвм. Так чинять не тiльки 10 в українськiй мовi. В англiйскiй замiсть partially ordered set пишуть poset, а в росiйськiй замiсть “частично упорядоченое множество“ пишуть чум. Крiм того, iснує традицiя без особливої потреби не пiдкреслювати порядок частковий чи лiнiйний, строгий чи нестрогий — уточнення виловлюються iз мовного оточення. Якщо для двох елементiв a, b ∈ A частково впорядкованої множини ⟨A, R⟩ виконується одна iз умов (a, b) ∈ R або (b, a) ∈ R, (9) то кажуть, що елементи a, b ∈ A порiвнюванi. Якщо ж умова (9) не виконується, то елементи a, b ∈ A непорiвнюванi. Порожнє вiдношення є вiдношенням строгого часткового порядку — нiякi два елементи не порiвнюванi. Дiагональ є вiдношення нестрогого порядку — кожен елемент порiвнюваний лише сам з собою. Вiдношення “бути дiльником“ є вiдношенням порядку на множинi натуральних чисел. 2.1.2 Найбiльший, найменший, максмальний та мiнiмальний елементи Найбiльшим елементом множини називається такий елемент, який бiльше кожного iншого. Природно, що коли найбiльший елемент iснує, то вiн єдиний. Елемент, для якого не iснує бiльшого, називають максимальним. Елементи b, c в чвм на рис. 2 максимальнi, а найбiльшого елемента ця множина не має. Таке розрiзнення максимальних i найбльших елементiв в математицi дещо вiдрiзняється вiд побутового вжитку, де цi слова звичайно означають одне i те ж. Елемент чвм, який менше (або дорiвнює) кожного елемента 11 множини, називають найменшим. Якщо для заданого елемента строго меншого вiд нього немає,то такий елемент називають мiнiмальним. Множина дiйсних чисел не має нi найменшого нi мiнiмального елемента. 2.1.3 Алфавiтниий порядок та порядок на прямому добутку двох чвм На алфавiтi — множинi, з елементiв якої будуються послiдовностi — слова, звичайно вводять лiнiйний порядок. Цей порядок дозволяє на множинi слiв, що будуються iз елементiв алфавiту (букв), також ввести порядок (як у словнику). Його називають i алфавiтним i лексикографiчним. Наприклад, коли алфавiт складається iз букв а, б, в, г, i на множинi букв введений порядок — а йде ранiше вiд б, б йде ранiше вiд в, а в йде ранiше вiд г, то слово “баба“ йде ранiше вiд слова “гав“, Лексикографiчний порядок використовують для того, що записати пiдряд (в лiнiйному порядку) доданки многочлена вiд багатьох змiнних. В такому випадку змiннi лiнiйно впорядковують — припустимо x < y < z . Далi добутки змiнних записують у виглядi степенiв змiнних — спочатку йде степiнь першої змiнної, потiм iде степiнь другої змiнної i так далi. Наприклад, zxxyzyyxxxzyyyyzxxx = x8 y 7 z 4 , zzzzzzzxyzyyxxyyyyyyyxzyyyyz = x4 y 14 z Потiм по черзi порiвнюють степенi змiнних — в якому доданку степiнь змiнної виявився бiльшим, той доданок i пишеться першим. В нашому випадку 8 > 7 i доданок x8 y 7 z 4 потрiбно записувати перед доданком x7 y 14 z 10 . 12 Нехай за того ж порядку на змiнних x, y, z потрiбно записати доданки суми (многочлена) f = x + 8 − 159y 2 + x3 z 12 y − 2x3 + 11y 14 z + xz (10) в лексикографiчному порядку. Спочатку переписуємо суму з використанням нульового степеня: f = xy 0 z 0 +8x0 y 0 z 0 −159x0 y 2 z 0 +x3 z 12 y 1 −2x3 y 0 z 0 +11x0 y 14 z 1 +x1 y 0 z 1 . Далi виписуємо уже в лексикогрфiчному порядку — спочатку доданки, що мiстять x3 , потiм доданки, що мiстять x2 ,потiм доданки, що мiстять x1 , i нарештиi доданки, що мiстять x0 : f = x3 y 1 z 12 −2x3 y 0 z 0 +x1 y 0 z 1 +x1 y 0 z 0 +11x0 y 14 z 1 −159x0 y 2 z 0 +8x0 y 0 z 0 = . = x3 yz 12 − 2x3 + xz + x + 11y 14 z − 159y 2 + 8. Виписувати доданки многочлена можна не тiльки в спадному порядку, коли спочатку виписуються бiльшi доданки, а потiм меншi, а i в зростаючому порядку — коли спочатку виписуються меншi доданки а потiм бiльшi. В зростаючому порядку многочлен (10) матиме наступний запис f = 8 − 159y 2 + 11y 14 z + x + xz − 2x3 + x3 yx12 . Вибiр того чи iншого порядку запису доданкiв залежить вiд того, на що збираємося звернути увагу, якщо нам у многочленi f (x) = 7x − 3 + 5x2 важливi доданки малого степеня, то ми пишемо f (x) = −3 + 7x + 5x2 , якщо ж важливi доданки бiльшого степеня, то ми пишемо f (x) = 5x2 + 7x − 3. В многочленах вiд кiлькох змiнних важливою є сума степенiв змiнних у доданках. Тодi лексикографiчний порядок використовують лише щоб впорядкувати тi доданки, якi мають 13 один i той же степiнь. Так многочлен з дiйсними коефiцiєнтами вiд двох змiнних, в якому сума степенiв змiнних у доданках не перевищує 2, має настпний стандартний запис a11 x2 +a12 xy +a22 y 2 +a1 x+a2 y +a0 , a11 , a12 , a22 , a1 , a2 , a0 ∈ R). Якщо заданi двi чвм A, B i C = A × B , то на прямому добутку C вводиться наступний частковий порядок: для a1 , a2 ∈ A, b1 , b2 ∈ B, c1 = (a1 , a2 ), c2 = (a2 , b2 ) ∈ C (c1 < c2 ) ⇔ ((a1 < a2 ) ∧ (b1 < b2 )). 2.1.4 Використання лiнiйного порядку в iнформатицi В машиннiй обробцi даних часто приходиться шукати потрiбний елемент в множинi. Один iз способiв — лiнiйно впорядкувати множину i по черзi перебирати елементи до тих пiр, поки не знайдеться порiбний. Але часто на множинi уже iснує певний частковий порядок. Для таких випадкiв розробленi спецiальнi прийоми. Крiм того, буває недоцiльно зберiгати всi данi для обробки — наприклад, всi доданки певної суми. Може бути, що бiльш доцiльно всi цi данi послiдовно породжувати (створювати) — а для цього знову ж потрiбно встановити на даних певний порядок i потiм їх по черзi породжувати. Для прикладу вiзьмемо завдання — надрукувати (вивести на друк, породити) всi пiдмножини множини {1, 2, . . . , n}. Для цього можна запропонувати наступний алгоритм. Спочатку виводимо символ порожньої, множини. Потiм виконуємо n крокiв — на першому кроцi до вивиденої множини (порожньої) додаємо 1 — вивели одноелементну множину {1}. Далi на другому кроцi до виведених множин додаємо 2 — виводимо {2} i 14 {1, 2}. На третьому кроцi до виведених на попереднiх кроках пiдмножин додаємо 3 — виводимо {3}, {2, 3}, {1, 2, 3}. I так далi — на останньому n−у кроцi до ранiше виведених множин додаємо число n i результат виводимо на друк. Таким чином ми всi пiдмножини розташували у послiдовнiсть, тобто лiнiйно впорядкували. Але цей порядок суттєво вiдрiзняється вiд порядку, який визначається вiдношенням включення, вiдношення “бути пiдмножиною“. 2.1.5 Нетранзитивнi вiдношення “краще“ та “сильнiше“ Найвiдомiшою множиною iз нетранзитивним вiдношенням “сильнiше“ є камiнь, ножицi,папiр. Папiр сильнiший за камiнь, тому що може його обгорнути. Камiнь сильнiший за ножицi, тому що камiнь може ножицi затупити. А ножицi сильнiшi за папiр, тому що вони можуть папiр розрiзати. Використовується значна кiлькiсть рiзновидiв цiєї множини, — i в дитячих iграх, i у випадковому виборi одного iз кiлькох, i в дорослих змаганнях. Другий приклад, не настiльки простий як попереднiй, i досить неочевидний, дає нам гра, яку в 1969 роцi придумав Уолтер Пенi. В цiй грi Алiса та Бiл задумують послiдовнiсть довжини 3, яка складається iз 0 та 1. Далi вони пiдкидають монету i пишуть 1, якщо монета впала гербом вверх, i пишуть 0, коли монета впала гербом вниз. Таким чином вони одержують послiдовнiсть 0 та 1. Виграє в цiй грi той, чия послiдовнiсть з’виться першою. Для прикладу, нехай Алiса задумала 000, а Бiл задумав 101. При пiдкиданнi монети записувалась послi- 15 довнiсть 011110011000 Оскiльки три нулi пiдряд появилися, а послiдовнiсть 101 не появилася, то виграла Алiса. В деяких випадках послiдовнiсть Алiси може бути “кращою“, нiж послiдовнiсть Бiла в тому розумiннi, що Алiса частiше буде вигравати, коли задуманi ними послiдовностi не змiнюватимуться. Так, припустимо, що Алiса задумала 100, а Бiл задумав 000. Тодi у випадку, коли першою вони записали 1, шансiв виграти Бiловi у Алiси немає, а коли випав 0 то шанси виграти є у обох, — в цьому випадку послiдовнiсть 100 “краща“, нiж послiдовнiсть 000. Можна довести, що для кожної послiдовностi Бiла Алiса може придумати “кращу“ послiдовнiсть, отже найкращої послiдовностi немає, i транзитивнiсть у вiдношення “краще“ вiдсутня. Наведенi приклади повиннi показати, що iз того, що якесь бiнарне вiдношення назване “бiльше“, “краще“, “вище“, не випливає його транзитивнiсть, не впливає, що це вiдношення є вiдношенням порядку. 2.2 2.2.1 Дiаграми Дiаграми скiнченних чвм Кажуть, що елемент x чвм A покриває елемент y цiєї множини i пишуть x ≻ y , коли x > y i не iснує елемента z такого, що x > z > y. Введене вiдношення використовується для побудови так званих дiаграм чвм. На дiаграмах елементи чвм зображаються точками, i якщо x ≻ y, то x зображається дещо вище вiд y i з’єднується з y вiдрiзком. Можна також будувати дiаграми 16 чвм так, що коли x ≻ y, то x зображається дещо правiше вiд y i з’єднується з y вiдрiзком. Як саме зображати — бiльший елемент зображати вище вiд меншого чи правiше вiд меншого, залежить вiд ситуацiї, вiд традицiї, вiд типографських вимог та подiбного. На рис. 7 бiльший елемент зображений правiше, а на рис. 6 бiльший елемент зображений вище. При великому бажаннi можна також бiльший елемнт зображати нижче вiд меншого Зобразимо кiлька вiдношень порядку на триелементнiй множинi {a, b, c} (див. рис. 2,3,4 5). Всього на триелементнiй множинi можна ввести 19 вiдношень часткового порядку. 17 Всi три елементи чвм на рис. 3 є i мiнiмальними i максимальними, але нi найменшого нi найбiльшого серед них немає. На рис. 2 елемент a є найменшим i, вiдповiдно, мiнiмальним, а обидва елементи b, c є максимальними, але жоден з них не є найбiльшим. На рис. 5 елемент a є i мiнiмальним i найменшим, а елемент c є максимальним i найбiльшим. 2.2.2 Лiнiйний та деревоподiбний порядок на скiнченних множинах Часто зустрiчаються два типи часткового порядку — при наявностi першого порядку будь-якi два елементи порiвнюванi, це так званий лiнiйний порядок, а множина називається в такому разi лiнiйно впорядкованою, а при наявностi другого у множинi є наменший елемент, а будь-якi непорiвнюванi елементи не мають спiльного бiльшого вiд них елемента. Дiаграми таких чвм називають деревами, а сам порядок називають деревоподiбним. Дiйснi числа лiнiйно впорядкованi, а структура сайту часто деревоподiбна. З лiнiйним порядком легше працювати, а деревоподiбний порядок постачає практика. 18 b c a a b c Рис. 3: Всi елементи непорiвнюванi Рис. 2: b > a, c > a i b, c непорiвнюванi b c b a c a Рис. 4: b > a. Елементи a, c та еле- Рис. 5: a < b < c. Будь-яка пара елементи b, c непорiвнюванi ментiв порiвнювана. 19 a1 Рис. 6: Дерево a2 a3 a4 a5 Рис. 7: Лiнiйний порядок Взаємозалежнiсть пiдроздiлiв великої органiзацiї часто зображають у виглядi дерев. 2.2.3 Ключi в iнформатицi, в базах даних Часто стан речей змушує впорядковувати великi за обсягом множини (масиви) даних — свiтлини, данi про студентiв, проплати в фiнансових закладах та подiбне. В реляцiйний базах даних данi органiзовуються у виглядi прямокутних таблиць. Елементи цих таблиць називають полями, рядки називають записами. Поля одного запису можуть бути досить рiзнорiдними — мони можуть мiстити шляхи доступу до файлiв, iмена, номери, дiйснi числа та подiбне. В одному стовпичку поля обов’язково однотипнi — якщо одне поле числове, то i всi поля стовпчика числовi, якщо одне поле мiстить текст, то i всi поля цього мiстять виключно тексти. Поля можуть бути незаповненими — в будь-якому стовпчику. Стовпчики називають 20 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 23 456 550 201 17 12445 943 5 17 1 23 4 201 2 456 3 550 7 943 6 12445 Табл. 1: Спи- Табл. 2: Перенумеро- Табл. 3: Активний сок iз 7 чисел ванй список iз 7 чисел другий ключ ключами. Поля одного стовпчика (ключа) можна лiнiйно впорядкувати. Якщо командою зробити ключ активним, то всi записи впорядкуються (рядки переставляться) так, щоб поля активного ключа йшли в порядку зростання або у порядку спадання. Наведемо приклад. Нехай є данi, що складаються iз 7 записiв, 7 чисел 23, 456, 550, 201, 17, 12445, 943. Оскiльки записи це рядки, то їх потрiбно розташувати у стовпчик (див. табл. 1). Досить зручно перенумерувати цi числа (1, 23), (2, 456), (3, 550), (4, 201), (5, 17), (6, 12445), (7, 943). (див. табл. 2). Тепер записи складаються iз двох полiв. Так запис (4,201) має поле 4 i має поле 201. Перший стовпчик табл. 2) є першим ключем i записи впорядкованi в порядку зростання першого ключа. Другий стовпчик — це другий ключ. Його можна зробити активним, i тодi таблиця прийме вигляд (табл. 3). Отже ключем свiтлини може бути її назва, а також рiк одержання, тематична спрямованiсть, кого стосується та подiбне. 21 Назву свiтлини можна назвати ключем, а мiсце, де записується назва, можна назвати полем. У кожного запису звичайно багато ключiв, якi дозволяють з належною швидкiстю вiдшукувати потрiбний запис серед багатьох подiбних. Одна з головних властивостей набору ключiв — кожен запис супроводжується унiкальним набором ключiв, тобто два рiзнi записи мають рiзнi ключi — в таблицi немає однакових рядкiв. Одна з важливих задач, яка розв’язується за допомогою часткового порядку на наборах ключiв — задача пошуку, пошуку певного елемента, певного запису, чи пошуку всiх записiв, що маєть заданi властивiсть. У файловiй системi комп’ютера файл супроводжується ключами — шляхом доступу (на якому диску, в якiй послiдовностi папок), назвою, розширенням (якою програмою створений), коли файл створений чи видозмiнений, обсяг файла, права доступу до нього. Будова файлової системи деревоподiбна. Бази даних (БД) що побудованi подiбно до файлової системи комп’ютера з використанням деревоподiбного часткового порядку, називають iєрархiчними БД. 2.2.4 Ключi в iнформатицi, в криптографiї В органiзацiях службовцi на рiзних щаблях управлiнської структури мають доступ до рiзної iнформацiї. Iнформацiя звичайно записується у такому виглядi, який не дозволяє знайомитися з нею тим, кому це не дозволене — шифрується. При шифруваннi та дешифруваннi використовуються певнi параметри — числа, послiдовностi чисел, послiдовностi букв та подiбне. Цi параметри називають ключами. Отже ключi тут дозволяють знайомитися iз зашифрованою iнформацiєю. Iснує проблема створення такої системи шифрування i, вiд22 повiдно, пiдбору ключiв, щоб службовцi з бiльш високим правом до ступу до iнформацiї могли читати те, що призначене слюжбовцю з низьким правом доступу, а службовцi з низьким правом доступу не могли читати iнформацiю, яка призначена для тих хто має високе право доступу. Службовцi одного щобля, однакового права доступу утворюють так званий клас безпеки. Оцi класи безпеки i, вiдповiдно, їх ключi, утворюють iєрархiю, деревоподiбну частково впорядковану множину. 2.3 2.3.1 Iзоморфiзм частково впорядкованих множин Означення та приклади Нехай ⟨A; ≤⟩ , i ⟨B ; ≤⟩ двi частково впорядкованi множини. Бiєктивне вiдображення (бiєкцiя) f : A → B , яке задовольняє умову ∀x, y ∈ A(x ≤ y ⇔ f (x) ≤ f (y ), (11) низивають iзоморфiзмом (або подiбнiстю) частково впорядкованих множин. В загальному випадку, коли вiдображення f не обов’язково є бiєкцiєю, але задовольняє умову (12), f називають (не строго) монотонним вiдображенням. Якщо ж умову (12) замiнити на ∀x, y ∈ A(x < y ⇔ f (x) < f (y ), (12) то функцiю, яка задовольняє цю умову називають строго монотонною. Таким чином, iзоморфiзм (український термiн — подiбнiсть) — це строго монотонна бiєкцiя. Двi частко впорядкованi множини, мiж якими можна встановити iзоморфiзм (побудувати iзоморфiзм iз однiєї чвм в другу чвм) називають iзоморфними або подiбними. Часто мiркування проводять “з точнiстю до iзоморфiзму“, тобто iзоморфнi 23 30 {a,b,c} 6 10 15 {a, b} {a, c} {b, c} 2 3 5 {a} {b} {c} 1 Рис. 8: Дiльники числа 30 ∅ Рис. 9: Пiдмножини множини {a, b, c} частко впорядкованi множини не розрiзняються, вважається, що це одна i та ж частко впорядкована множина. Бiєктивне вiдображення (бiєкцiя) f : A → B , яке задовольняє умову ∀x, y ∈ A(x ≤ y ⇔ f (x) ≥ f (y ), низвають антиiзоморфiзмом iз чвм A в чвм B . Iзоморфiзм скiнченних чвм легко розгледiти, зобразиши цi частково впорядкованi множини дiаграмами. Для прикладу, розглянемо чвм A усiх пiдмножин множини {a, b, c} i чвм B усiх дiльникiв числа 30, що впорядкованi за подiльнiстю — елемент x менше y коли x є дiльником y (див. рис. 8, 9) Iзоморфiзм мiж множиною дiльникiв i множиною пiдмножин встановлюється правилом 24 ∅ {a} {b} {c} 1 {a, b} 2 {a, c} 3 5 {b, c} {a, b, c} 6 2.3.2 10 15 30 Сортування. Сiм фундаметальних алгоритмiв сортування. Встановлення iзоморфiзму iз скiнченної лiнiйно впорядкованої множини в початковий вiдрiзок натурального ряду називають сортуванням. Для прикладу, результатом сортування частково впорядкованої множини A = {a, b, c}, де c < a < b, буде або перезапис цiєї множини у порядку зростання (елементу множини вiдповiдає номер цього елемента в результуючiй по слiдовностi), тобто A = {c, a, b}, або бiля кожного елемента iз A виписуєть той елемент початкового вiдрiзка натурального ряду, який вiдповiдає цьому елементу, в нашому випадку a b c 2 3 1 25 Елементи множини, яку потрiбно вiдсортувати, записуються у послiдовнiсть, тому замiсть слова множина в даному мовному оточеннi використовується слово список. В послiдовностi кожен елемент одержує свiй номер. Цей номер називаємо адресою елемента у списку. Найважливiшими алгоритмами сортуваня, тобто алгоритмами встановлення потрiбного iзоморфiзму, є • лiнiйний вибiр; • лiнiйний вибiр з обмiном; • лiнiйний вибiр з пiдрахунком; • стандартний обмiн; • парний обмiн; • просiювання; • лiнiйна вставка. Дiю алгоритмiв будемо пояснювати на прикладi, в якому потрiбно сортувати множину A = {23, 456, 550, 201, 17, 12445, 943}. Переписуємо множину iз вказiвкою адреси елементiв 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 (14) (13) Лiнiйний вибiр Для роботи алгоритму видiляється робоча комiрка r i мiсце результуючого списку, списку виведення. На початку роботи 26 вони порожнi, цей факт будемо позначати символом перед початком роботи алгоритму маємо r = i 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 . Отже (15) Робота алгоритму розбивається на стiльки переглядiв всього списку, скiльки елементiв в цьому списку. Отже в нашому прикладi всього буде 7 переглядiв всього списку. Прослiдкуємо за першим переглядом. Кандидатом на перший елемент результуючого списку обирається перший елемент джерела — заданого списку. В нашому випадку цим елементом є 23. В робочу комiрку заноситься адреса цього елемента — в нашому випадку адреса 1, отже r = 1. Кандидат в першi елементи по черзi порiвнюється з наступними до тих пiр, поки не знайдеться менший, або не закiнчиться перегляд. Порiвнюючи перший елемент з 5-м, бачимо, що 5-й елемент 17 менший вiд 23. Цей новий елемент (в нашому випадку 17) стає новим кандидатом на перший елемент результуючого списку, його адреса заноситься в робочу комiрку, i порiвняння продобжується знову до тих пiр, поки не зустрiнеться менший елемент, або поки не закiнчиться список. В нашому випадку список закiнчиться ранiше, нiж знайдеться менший. Коли список закiнчився, перегляд закiнчується, кандидат в найменшi елементи стає справдi найменшим елементом (першим елементом) результуючого списку, а його мiсце в джерелi заповнюється фiктивним елементом, з яким елементи не порiвнюються. Робота першого перегляду в нашому прикладi приведе до результату (фiктивний елемент позначено x) 27 23 456 550 201 x 12445 943 1 2 3 4 5 6 7 17 Наступає черга другого перегляду, результатом якого є другий елемент результуючого списку. Шукається перший нефiктивний елемент в джерелi. Вiн стає кандидатом у другi елементи, а його адреса заноситься у робочу комiрку. По черзi кандидат порiвнюється iз наступними елементами джерела. Якщо знайшовся менший, то вiн замiняє кандидата, i робоча комiрка одержує нову адресу, адресу нового елемента. Якщо ж перегляд завершився, то кандидат займає мiсце другого елемента результуючого списку, робоча комiрка стає порожньою. На мiсце перемiщеного кандидата ставиться фiктивний символ. Результатом роботи другого перегляду в нашому прикладi є x 456 550 201 x 12445 943 1 2 3 4 5 6 7 17 23 Подiбним чином здiйснюються решта переглядiв — в нашому прикладi 3, 4,5,6 та 7. Сортування закiнчене. Результуючий список створено. В нашому прикладi пiсля сьомого перегляду одержуємо x x x x x x x 1 2 3 4 5 6 7 17 23 201 456 550 943 12445 i результуючий список має вигляд B = {17, 23, 201, 456, 550, 943, 12445}. 28 Лiнiйний вибiр з обмiном. Лiнiйний вибiр з обмiном також має перегляди, але на один менше, нiж кiлькiсть елементiв у списку до сортування — джерелi. В цьому алгоритмi не видiляється мiсце для результуючого списку, результуючий список формується на мiсцi джерела. Кожен з переглядiв визначає наступний елемент результуючого спску. В нашому прикладi маємо джерело 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 Перший перегляд починається з того, що кандидатом на найменший елемент обирається перший елемент джерела. Далi вiн порiвнюється iз наступними елементами до тих пiр, поки не закiнчиться список, або не зустрiнеться менший елемент. Якщо список закiнчився, то перегляд закiнчився, а якщо зустрiвся менший елемент, то вiн мiняється мiсцем iз першим, i перегляд продовжується. Результатом першого перегляду в нашому прикладi буде 17 456 550 201 23 12445 943 1 2 3 4 5 6 7 Другий перегляд починається з того, що кандидатом на другий елемент обирається другий елемент видозмiненого перешим переглядом джерела. Далi вiн порiвнюється iз наступними елементами до тих пiр, поки не закiнчиться список, або не зустрiнеться менший елемент. Якщо список закiнчився, то перегляд закiнчився, а якщо зустрiвся менший елемент, то вiн мiняється мiсцем iз другим, i перегляд продовжується. Результатом другого перегляду в нашому прикладi буде 29 17 23 550 445 201 12445 943 1 2 3 4 5 6 7 Подiбним чином здiйснюються решта переглядiв — k -й перегляд працює з тiєю частиною видозмiненого джерела, яка починається iз k -ого мiсця. Результатом роботи алгоритму в нашому прикладi буде 17 23 201 456 550 943 12445 1 2 3 4 5 6 7 Лiнiйний вибiр з пiдрахунком Знову маємо заданий список — у прикладi ним є (14). Створюємо лiчильники — в (14) додаємо порожнiй рядок, в якому в результатi роботи алгоритму одержимо адреси (порядковi номери) елементiв джерела в результуючому списку. Одержуємо (15). Комiрку нижнього рядка називаємо лiчильником того елемента списку, що стоїть у першому рядку. Всi комiрки першого рядка — всi лiчильники, заповнюємо одиничками. Алгоритм розбивається на стiльки переглядiв всього списку, скiльки елементiв у заданому списку. При першому переглядi перший елемент джерела порiвнюється iз кожним (крiм себе) елементом джерела. Якщо порiвнюваний елемент менше першого, то до лiчильника цього першого елемента додається 1. А якщо порiвнюваний елемент бiльший першого, то не робиться нiчого, просто переходимо до наступного порiвняння. В результатi роботи першого перегляду в нижньому рядку перший елемент одержить в лiчильнику кiлькiсть елементiв, що менше нього, плюс 1. В нашому прикладi перший перегляд дасть 30 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 2 1 1 1 1 1 1 При другому переглядi другий елемент джерела порiвнюється iз кожним (крiм себе) елементом джерела. Якщо порiвнюваний елемент менше другого, то до лiчильника цього другого елемента додається 1. А якщо порiвнюваний елемент бiльший другого, то не робиться нiчого, просто переходимо до наступного порiвняння. I так далi. При k −ому переглядi k −й елемент джерела порiвнюється iз кожним (крiм себе) елементом джерела. Якщо порiвнюваний елемент менше другого, то до лiчильника цього k −го елемента додається 1. А якщо порiвнюваний елемент бiльший k −го, то не робиться нiчого, просто переходимо до наступного порiвняння. В результатi роботи алгоритму пiд кожним елементом джерела в його лiчильнику одержиться число, яке на одиничку бiльше нiж кiлькiсть елементiв джерела, що меншi за нього, тобто лiчильник позазуватиме мiсце елемента джерела в результуючому списку. В нашому прикладi матимемо 23 456 550 201 17 12445 943 1 2 3 4 5 6 7 2 4 5 3 1 7 6 Стандартний обмiн Стандартний обмiн називають також методом бульки, тому що кожен елемент списку пересуваєься на своє мiсце подiбно бульцi, що спливає вверх у водi. 31 В стандартному обмiнi додаткова пам’ять не використовується. Отже в нашому прикладi маємо джерело A = {23, 456, 550, 201, 17, 12445, 943}. При кожному переглядi ведеться пiдрахунок кiлькостi обмiнiв. Якщо обмiнiв при переглядi не було, то робота алгоритма завершується. При кожному наступному переглядi кiлькiсть учасникiв перегляду зменшується. Якщо ця кiлькiсть дорiвнює 0, то алгоритм закiнчує роботу. При першому переглядi розглядаються пари (перший-другий), (другий-третiй), (третiй-четвертий) i т.д. Якщо наступний елемент пари менше поппереднього, то вони мiняються мiсцями (вiдбувається обмiн, який враховується лiчильником). Якщо ж другий елемент бiльше першого, то переходимо до наступної пари. В результатi першого перегляду найбiльший елемент списка стане на останнє мiсце i виключається iз розглядання. В нашому прикладi перший перегляд дасть A1 = {23, 456, 201, 17, 550, 943, 12445}. Другий перегляд здiйснюється так як i перший, за винятком того, що останнiй елемент не розглядається. В нашому прикладi другий перегляд дасть A1 = {23, 201, 17, 456, 550, 943, 12445}. Другий перегляд гарантує, що два останнi елементи саме тi, якi повиннi стояти у результуючому списку. Решта переглядiв вiдбувається подiбним чином. В нашому прикладi другий перегляд дасть 32 A2 = {23, 17, 201, 456, 550, 943, 12445}, третiй перегляд дасть A2 = {17, 23, 201, 456, 550, 943, 12445}, (16) четвертий перегляд покаже, що обмiнiв не було i алгоритм закiнчив роботу. Парний обмiн В цьому алгоритмi не використовується додаткова пам’ять, але сам алгоритм органiзовується досить складно. Як i попереднi алгоритми, парний обмiн розбивається на перегляди. При кожному переглядi розглядаються пара елементiв списку-джерела. На переглядах з непарними номерами розглядаються пари позицiй (адрес) (1,2) (3,4), (5,6) i т. д. , тобто пари вигляду (2k − 1, 2k ). Порiвнюються елементи з адресами, якi утворюють пару. Якщо елемент з меншою адресою бiльший елемента з меншою адресою, то вони обмiнюються мiсцями. В протилежному випадку вони залишаються на мiсцi На переглядах з парними номерами розглядаються пари позицiй (адрес) (2,3) (4,5), (6,7) i т. д. , тобто пари вигляду (2k, 2k + 1). Порiвнюються елементи з адресами, якi утворюють пару. Якщо елемент з меншою адресою бiльший елемента з меншою адресою, то вони обмiнюються мiсцями. В протилежному випадку вони залишаються на мiсцi. Якщо останнiй елемент списку не має пари, то вiн у переглядi не бере участi. На кожному переглядi ведеться облiк кiлькостi обмiнiв позицiями. Якщо кiлькiсть обмiнiв при двох послiдовних переглядах дорiвнює нулю, то алгоритм закiнчує роботу. 33 Прослiдкуємо за роботою цього алгоритму на нашому прикладi. На першому кроцi розглядаються пари (23, 456), (550, 201), (17, 12445). I пiсля першого перегляду одержуємо список {23, 456, 201, 550, 17, 12445, 943}. На другому переглядi розглядаються пари (456, 201), (550, 17), (12445, 943). Результатом роботи перегляду буде {23, 201, 456, 17, 550, 943, 12445}. Третiй, четвертий та п’ятий перегляди дадуть списки {23, 201, 17, 456, 550, 943, 12445}, {23, 17, 201, 456, 550, 943, 12445}, {17, 23, 201, 456, 550, 943, 12445}. Шостий та сьомий перегляди переконують нас в тому, що сортування завершене, i вiдповiддю є список {17, 23, 201, 456, 550, 943, 12445}. Просiювання В просiюваннi немає окремих переглядiв всього списку, але перегляд природно розбивається на частини. На одних частинах рух вiдбувається в сторону зростання адреси, а на iнших рух вiдбувається в сторону зменшення адреси. В цьому алгоритмi порiвнюються, як i в методi стандартного обмiну, пари сусiднiх елементiв списку. Якщо бiльший елемнт має меншу адресу, то вiн мiняється мiсцем iз сусiдом, з яким порiвнюється. 34 Починається алгоритм iз порiвняння елементiв списку з адресам 1 та 2. Пiсля порiвняння переходимо до пари з адресами 2 та 3. Такий перехiд назвемо прямим переходом, або переходом у сторону зростання. Якщо в парi вiдбувся обмiн мiсцями елементiв списку, то 1. запам’ятовується мiсце, та пара, де вiдбувся обмiн; 2. починається рух в зворотному напрямку — адреси пари зменшуються на 1. Якщо при русi в зворотному напрямку вiдбувся обмiн, то рух в зворотному напрямку продовжується (якщо це можливо, коли пара не перша). Якщо ж обмiн не вiдбувся, або пара перша, то починається рух у прямому напрямку починаючи iз запам’ятованого мiсця. Алгоритм закiнчує роботу, коли розглянута остання пара в списку i вiдбувся, якщо це необхiдно, рух у зворотному напрямку. Покажемо, як працює цей метод на нашому прикладi A = {23, 456, 550, 201, 17, 12445, 943}. Спочатку розглядаються пара (23,456). Обмiну немає. Рухаємося у прямому напрямку. Переходимо до пари (456,550), обмiну немає. Рухаємося у прямому напрямку, переходимо до пари (550,210). Є обмiн. Запам’ятовуємо, що ми розглядали пару з адресами (3,4). Рухаємося у зворотному напрямку. Розглядаэмо пару (456,210). Робимо обмiн i рухаємося у зворотному напрямку. Розглядаємо пару (23,210). Обмiну немає, зворотний рух припинено. Одержали список A = {23, 210, 456, 550, 17, 12445, 943}. 35 Починаємо рух у прямому напрямку з пари, що має адреси (4,5), тобто (550, 17). Є обмiн. Запам’ятовуємо мiсце для початку наступного прямого руху. Починаємо рух назад, у зворотному напрямку. Пара (456,17) дає обмiн, рухаємося назад. Пара (210,17) дає обмiн, рухаємося назад. Пара (23, 17) дає обмiн, але рух назад припиняємо, тому що це перша пара. Одержали список {17, 23, 210, 456, 550, 12445, 943}. Починаємо рух у прямому напрямку з пари, що має адреси (5,6) — обмiну немає, рухаємося далi. Наступна пара (12445,943), обмiн є. Оскiльки пара була останньою, то запам’ятовувати мiсце не потрiбно — алгоритм закiнчиться, коли закiнчиться зворотний рух. Зворотний рух починається iз пари (550,943) — обмiну нема, зворотний рух припинився, алгоритм закiнчено, одержано кiнцевий список {17, 23, 210, 456, 550, 943, 12445}. Лiнiйна вставка. При застосуваннi цього методу спочатку утворюється порожнiй результуючий список, який в кiнцi роботи алгоритму перетворюється на справжнiй впорядкований пiдсумковий список. Кожен крок алгоритму полягає у вставляннi чергового елемента списка-джерела A = {a1 , a2 , . . . , an } у пiдсумковий список B = b1 , b2 , . . . , bn . Перед початком роботи пiдсумковий список порожнiй — символьно цей факт записуємо як bi = , i = 1, 2, . . . , n. 36 На першому кроцi береться перший елемент списка-джерела i ставиться на перше мiсце пiдсумкового списку, отже b1 = a1 . На другому кроцi береться другий елемент a2 списка-джерела A, порiвнюється iз першим елементом b1 пiдсумкового списку i, якщо a2 > b1 , то пишемо наступний елемент списка B — b2 = a2 . Якщо ж a2 < b1 , то пишемо b1 = a2 , b2 = a1 . На кожному наступному (скажемо k −му, k = 3, 4, . . . , n кроцi маємо визначенi елемент b1 , b2 , . . . , bk−1 , i при цьому {a1 , a2 , . . . , ak−1 } = {b1 , b2 , . . . , bk−1 }. Вибираємо елемент ak ∈ A i по черзi порiвнюємо його з елементами b1 , b2 , . . . , bk−1 . Якщо ak < b1 , то на перше мiсце пiдсумкового списку ставимо ak , а решту списку зсуваємо на одну позицiю вправо. Якщо ak > bk−1 , то на k −е мiсце пiдсумкового списку ставимо ak . Якщо ak < bk−1 , i ak > b1 , то знаходимо мiсце i, 1 < i < k − 1 таке, що bi < ak < bi+1 , роздiляємо пiдсумковий список на двi частини — до i−го мiсця i пiсля i−го мiсця. Праву частину зсуваємо на одну позицiю вправо. На вивiльнену i−у поозицiю вставляємо елемент ak . Черговий крок завершено. Покажемо, як працює метод лiнiйної вставки на нашому прикладi списку (13). Перед початком роботи маємо A = {23, 456, 550, 201, 17, 12445, 943}. B0 = { , , , , , , }. Випишемо 7 послiдовних виглядiв B1 , B2 , B3 , B4 , B5 , B6 , B7 = B пiдсумкового списку (рисочку ставимо зверху над тим елементом, який щойно вставлений) 37 B1 B2 B3 B4 B5 B6 B7 2.4 2.4.1 = {23, , , , , , }, = {23, 456, , , , , }, = {23, 456, 550, , , , }, = {23, 201, 456, 550, , , }, = {17, 23, 201, 456, 550, 12445, }, = {17, 23, 201, 456, 550, 12445, }, = {17, 23, 201, 456, 550, 943, 12445}. Верхнi та нижнi межi Означення та позначення Верхньою межею пiдмножини B ⊆ A частково впорядкованої множини ⟨A; ≤⟩ називають елемент a ∈ A, для якого ∀x ∈ B (x ≤ a). Одна i та ж пiдмножина може мати багато верхнiх меж. Верхня межа, яка менша (або дорiвнює) всiх iнших верхнiх меж, називається точною верхньою межею. Точна верхня межа пiдножини B ⊆ A позначається sup B . Точну верхню межу називають також “супремум“ i найменшою верхньою межею. Якщо пiдмножина чвм має верхню межу, то ця пiдмножина називається обмеженою зверху Найбiльший елемент є точною верхньою межею всєї чвм. В частково впорядкованiй множинi {a, b, c, d} з порядком a < b, c a. Якщо розглядати sup, inf як бiнарнi всюди визначенi операцiї на певнiй чвм M , то цi операцiї • iдемпотентнi, тобто sup{a, a} = a, inf {a, a} = a для будьякого a ∈ M ; • асоцiативнi, тобто sup{a, sup{b, c}} = sup{sup{a, b}, c}, inf {a, inf {b, c}} = inf {inf {a, b}, c} для будь-яких a, b, c ∈ M; • комутативнi, тобто sup{a, b} = sup{b, a}, inf {a, b} = inf {b, a} для будь-яких a, b ∈ M . 42 Мiж собою операцiю знаходження точної верхньої та точної нижньої межi двох елементiв зв’язна законами поглинання • inf {a, sup{a, b} = a; • sup{a, inf {a, b} = a. Наявнiсть виписаних властивостей обгрунтовується тим, що для будь-яких a, b ∈ M sup{a, b} ≥ a, 2.4.3 Напiвгратки та гратки. inf {a, b} ≤ a. Напiвграткою називають множину разом iз iдемпотентною, комутативною, асоцiативною операцiєю. Iз означення випливає, що чвм, в якiй для будь-яких двох елементiв iснує точна верхня межа, є напiвгракою — бiнарною операцiєю можна взяти операцiю знаходження точної верхньої межi. Також чвм, в якiй для будь-яких двох елементiв iснує точна нижня межа, є напiвгракою — бiнарною операцiєю можна взяти операцiю знаходження точної нижньої межi. Зворотне твердження оформим у виглядi теореми Теорема 2.1 В будь-якiй напiвгратцi можна ввести вiдношення часткового порядку так, що iснуюча на нiй бiнарна операцiя буде операцiєю знаходження точної верхньої (або точної нижньої) межi. Доведення. Нехай множина M разом iз операцiєю додавання + утворює напiвгратку, тобто для будь-яких елементiв a, b, c ∈ M a + a = a, a + b = b + a, 43 a + (b + c) = (a + b) + c. Введемо на M бiнарне дношення α ⊆ M 2 правилом: для a, b ∈ M (a, b) ∈ α ⇔ ∃c ∈ M (a = b + c). Доведемо, що так введене вiдношення є вiдношенням частвого порядку. Рефлексивнiсть вiдношення α випливає iз iдемпотентностi додавання ∀a ∈ M (a + a = a ⇒ ((a, a) ∈ α)). Транзитивнiсть випливає iз асоцiативного закону. Дiйсно, припустимо, що для деяких a, b, c ∈ M (a, b), (b, c) ∈ α. Тодi за визначенням вiдношення α для деяких x, y ∈ M , можна записати a = b + x, b = c + y Звiдси a = (c + y ) + x = c + (y + x), i (a, c) ∈ α. Доведемо антисиметричнiсть, тобто коли (a, b), (b, a) ∈ α, то a = b. В такому разi за визначенням бiнарного вiдношення α для деяких x, y ∈ M будуть виконуватися рiвностi a = b + x, b = a + y. Виписанi рiвностi дозволяють записати b + y = (a + y ) + y = a + (y + y ) = a + y = b, i a = (b + y ) + x = (b + x) + y = a + y = b, i антисиметричнiть перевiрена. 44 Якщо бiнарне вiдношення α назвати “бiльше або дорiвнює“, то операцiя додавання буде збiгатися iз операцiєю sup . Якщо ж бiнарне вiдношення α назвати “менше або дорiвнює“, то операцiя додавання буде збiгатися iз операцiєю inf . Теорема доведена. Граткою називають множину M разом iз двома iдемпотентними, комутативними, асоцiативними операцiями операцiями (назвемо цi операцiї додаванням та множенням), що пов’язанi мiж собою двома законами поглинання: для будь-яких x, y ∈ M x(x + y ) = x, x + xy = x. Кожна iз двох операцiй гратки визначає на множинi M , на якiй вони заданi два вiдношення порядку. А закони поглинання забезпечують збiг цих вiдношень. Наведенi мiркування дозволяють користуватися в певному розумiннi бiльш наочним означенням напiвгратки та гратки: Верхньою напiвграткою називають частково впорядковану множину, в якiй для будь-яких двох елементiв iснує точна точна верхня межа. Нижньою напiвграткою називають частково впорядковану множину, в якiй для будь-яких двох елементiв iснує точна точна нижня межа. Граткою називають частково впорядковану множину, в якiй для будь-яких двох елементiв iснує точна точна верхня межа i точна нижня межа. 45 На рис. 2 i на рис. 6 зображенi нижнi напiвгратки, якi не є верхнiми напiвгратками i, вiдповiдно, не є гратками. На рис. 8,9, 12 зображенi гратки. Важливим є випадок, коли в частково впорядкованiй множинi будь-яка пiдмножина має точну верхню межу (тодi ця чвм називаються повною верхньою напiвграткою), точку нижню межу (тодi ця чвм називається повною нижньою граткою) або будь-яка пiдмножина має у множинi i точну верхню i точну нижню межу. Чвм пiдполiв даного поля, чвм пiдгруп даної групи, чвм пiдкiлець даного кiльця i т. п. утворюють повнi напiвгратки. В кожнiй гратцi можна розглядати пiдгратки — частково впорядкованi пiдмножини (частковий порядок на пiдмножинi збiгається iз частковим порядком на всiй множинi), в яких для будь-яких двох елементiв iснує точна верхня i точна нижня межа. 3 Гратка пiдалгебр унiверсальної алгебри Нагадаємо, що унiверсальню алгеброю A = ⟨A; Σ⟩ називають множину A (її називають носiєм унiверсальної агебри A) разом iз операцiями, на цiй множинi. Множину Σ операцiй унiверсальної алгебри називають сигнатурою цiєї унiверсальної алгебри. У практичнiй роботi звичайно унiверсальну алгебру позначають так же як i її носiя. Звичайно це не призводить до непорозумiнь. Так ми можемо говорити про множину дiйсних чисел R i про R як множину дiйсних чисел разом iз операцiями додавання та множення. Унiверсальна алгебра B = ⟨B, Ξ⟩ буде пiдалгеброю алгебри A, коли B ⊆ A, 46 Σ = Ξ. Рiвнiсть Σ = Ξ розумiється як • збiг назв операцiй на A та на B • результат застосування операцiї з певною назвою до елементiв iз B буде один i той же незалежно вiд того, взяли ми операцiю з цiєю назвою iз Σ чи iз Ξ Для прикладу, якщо Σ складається тiльки з додавання, то Ξ повинна складатися також виключно iз додавання, причому сума елементiв iз B не залежить вiд того, взяли ми додавання iз Σ чи iз Ξ. Якщо в Σ є нульмiсна операцiя (видiлений елемент, наприклад, 0), то в Ξ також повинен бути вiдiлений той же самий елемент (в нашому прикладi 0). Якщо в Σ є одномiсна операцiя x → f (x), то в Ξ також повинна бути одномiсна операцiя з цим же iменем, яка є звуженням операцiї f ∈ Σ на B. Приклади пiдалгебр розглянема в наступних роздiлах — i визначення стане зрозумiлiшим. Якщо в сигнатурi алгебри є нульмiсна операцiя (видiлений елемент), то носiй пiдалгебри не може бути порожнiм — в ньому обов’язково повинен бути цей видiлений елемент. Якщо ж нульмiсних операцiй немає, то носiй може бути порожнiм. Так порожня множина буде пiдалгеброю алгебри з однiєю одномiсною операцiєю (унара). Замiсть словосплуки “унiверсальна алгебра“ будемо користуватися абревiатурою у.а. Є дещо видозмiнений пiдхiд до означення пiдалгебри унiверсальної алгебри. Нехай на множинi A задана n−мiсна операцiя f : An → A, i пiдмножина B ⊆ A має властивiсть ∀x1 , x2 , . . . , xn ∈ B (f (x1 , x1 , . . . , xn ) ∈ B ). 47 Тодi кажуть, що пiдмножина B замкнена вiдносно операцiї f . Якщо пiдмножина B замкнена вiдносно операцiї f , то операцiю f : B n → B, що задана правилом ( ) ∀x1 , x2 , . . . , xn ∈ B f (x1 , x1 , . . . , xn ) = f (x1 , x2 , . . . , xn ) , називають звуженням операцiї f на B . Точно кажучи, операцiї f i f це рiзнi операцiї, коли A ̸= B , — вони мають рiзнi областi визначення. Проте в практичнiй дiяльностi i операцiя i її звуження позначаються однаково i не розрiзняються. Щоб одержати при цьому непорозумiння, потрiбнi хист та бажання. Так, множина натуральних чисел замкнена вiдносно додавання та вiдносно множення, якi визначенi на множинi цiлих чисел, але не замкнена вiдносно операцiї вiднiмання. Множина цiлих чисел замкнена вiдносно операцiї вiднiмання, яка задана на множинi дiйсних чисел, але не замкнена вiдносно часткової операцiї дiлення (дiлення на ненульове число), яка визначена на множинi дiйсних чисел. Суму двох натуральних чисел n, m позначаємо n + m незалежно вiд того, додаємо ми їх як натуральнi числа чи як цiлi. Нехай задана у.а. A = ⟨A, Σ⟩ i пiдмножина B ⊆ A замкнена вiдносно всiх операцiй iз Σ. Тодi у.а. B = ⟨B, Σ⟩ називається пдiалгеброю у.а. A = ⟨A, Σ⟩ . Пiдалгебри заданої у.а. A частково впорядкованi: якщо B1 = ⟨B1 , Σ⟩, B2 = ⟨B2 , Σ⟩ двi пiдалгебри у.а. A = ⟨A, Σ⟩, то B1 ≤ B2 ⇔ B1 ⊆ B2 . 48 Теорема 3.1 Для будь-якої сiм’ї Bi = ⟨Bi , Σ⟩ i ∈ I ̸= ∅ пiдалгебр алгебри A = ⟨A, Σ⟩ iснує пiдалгебра B = inf {Bi |i ∈ I }, яка визначена умовою B = ⟨B, Σ⟩ =< ∩ i∈I Bi , Σ > . Доведення. Доведення. Спочатку переконаємося, що B є пiдалгеброю алгебри A, тобто переконаємося, що множина ∩ Bi B= i∈I замкнена вiдносно всiх операцiй iз Σ. Для цього вибираємо довiльну n−мiсну операцiю f ∈ Σ i елементи x1 , x2 , . . . , xn ∈ B. отрiбно довести, що f (x1 , x2 , . . . , xn ) ∈ B. Дiйсно, x1 , x2 , . . . , xn ∈ B ⇒ ∀i ∈ I (x1 , x2 , . . . , xn ∈ Bi ) ⇒ ⇒ ∀i ∈ I (f (x1 , x2 , . . . , xn ) ∈ Bi ) ⇒ f (x1 , x2 , . . . , xn ) ∈ B. Iмплiкацiї (1) та (3) правильнi за означенням перетину множин, а iмпликацiя (3) правильна тому, що Bi = ⟨Bi , Σ⟩ i ∈ I є пiдалгебрами алгебри A = ⟨A, Σ⟩ . Серед усiх пiдалгебр алгебри A є найменша — точна нижня межа всiх пiдалгебр, i є найбiльша — вся алгебра. Теорема 3.2 Для будь-якої сiм’ї Bi = ⟨Bi , Σ⟩ i ∈ I ̸= ∅ пiдалгебр алгебри A = ⟨A, Σ⟩ iснує пiдалгебра B = sup{Bi |i ∈ I }. 49 2 (3) (1) (2) Доведення. Задана сiм’я пiдалгебр має верхнi межi, однiєю з них буде вся алгебра. А точна нижня межа всiх верхнiх меж (вона iснує згiдно теореми 3.2) буде точною верхньою межею — за визначенням точної верхньої межi. Зауважимо, що носiй точної верхньої межi сукупностi пiдалгебр не обов’язково є об’єднанням носiїв пiдалгебр. Для прикладу можна взяти два пiдполя { } √ √ Q( (2)) = a + b 2|a, b ∈ Q i { } √ √ Q( (3)) = a + b 3|a, b ∈ Q поля дiйсних чисел. √ мi√ Точна верхня межа цих двох пiдполiв стить у собi √ число 6, але цього числа немає нi в полi Q( (2)) нi в полi Q( (3)). √ √ Перевiримо, що числа 6 немає в полi Q( (2)). Дiйсно, нехай для деяких рацiональних чисел a, b √ √ 6=a+b 2 (17) Тодi a ̸= 0, в протилежному випадку √ √ ми можгли б розiлiлити рiвнiсть (17) на 2 i одержати, що 3 є рацiональним числом. Число b також не√нуль, в протилежному випадку було б рацiональним число 6. Пiднiсши рiвнiсть 17 до квадрату, одержимо √ 6 = a + 2ab 2 + 2b2 , 2 √ √ тобто ми одержали, що число 2 є рацiональним. Одержане хибне твердження доводить, що рiвнiсть 17 неможлива, i sqrt6 50 6 − a2 − 2b2 , 2= 2ab не належить полю Q(2). Точно так же перевiряємо, що sqrt6 не належить полю √ Q(3). Таким чином, 6 не належить об’єднанню полiв Q(2), Q(3) i точна верхня межа цих пiдполiв не збiгається iз їх об’єднанням. Оскiльки кожна пiдалгебра унiверсальної алгебри бiльша вiд кожної пiдалгебри порожньої сукупностi пiдалгебр, i кожна пiдалгебра менша вiд кожної пiдалгебри порожньої сукупностi пiдалгебр, то найменша пiдалгебра буде точною верхньою межею всiх пiдалгебр iз порожньої сукупностi пiдалгебр, а вся алгебра буде точною нижньою межею всiх пiдалгебр iз порожньої сукупностi пiдалгебр. 3.1 Найменше пiдкiльце на найменше пiдполе Нагадаємо, що кiльце — це унiверсальна алгебра з двома бiнарними перацiями (вони називаються додаванням та множенням, однiєю нульмусною (видiлений елемент, вiн називається нулем), та однiєю одномiсною операцiєю (вона називається “знаходження протилежного елемента“. Додавання та множення асоцiативнi, додавання комутативне, мiж собою додавання та множення зв‘язанi двома (лiвим та правим) розподiльними (дистрибутивними) законами. Видiлений елемент 0 та операцiя знаходження протилежного елемента зв‘язанi тотожностями: для будь-якого елемента a кiльця a + (−a) = −a + a = 0, a + 0 = 0 + a = a. (18) Оскiльки кiльце має в своїй сигнатурi нульмiсну операцiю (нуль), то порожнiм кiльце i, вiдповiдно, пiдкiльце бути не може. А складатися виключно iз нуля може. Отже найменше 51 пiдкiльце в будь-якому кiльцi складається лише iз нуля. Якщо кiльце мiстить в собi елемент x, то це кiльце обов’язково мiстить x · x · x · . . . · x = xn , n x + x + x + . . . + x = nx n Тому найменше пiдкiльце, яке мiстить заданий елемент x всього кiльця, складається iз нуля i тих елементiв усього кiльця, якi можна записати у виглядi n1 x + n2 x2 + · · · + nk xk для деякого натурального k , i для n1 , n2 , . . . , nk ∈ N ∪ {0}. Поле має в своїй сигнатурi додавання, множення (бiнарнi операцiї, нуль та один (два рiзнi видiленi елементи), одну одномiсну операцiю знаходження протилежного елемента, та одну часткову одномiсну операцiю — знаходження для будьякого ненульового елемента оберненого. Як i в кiльцi, операцiї додавання та множення асоцiативнi, мiж собою зв’язанi дистибутивними законами, нуль та операцiя знаходження протилежного елемента зв’язанi сiввiдношеннями (18), множення в полi комутативне (некомутативнi поля називають тiлами). Часткова операцiя знаходження оберненого елемента (вона визначена на ненульових елементах поля) пiдкоряється умовам: для будь-якого елемента a ̸= 0 iз поля a · a−1 = a−1 · a = 1, a · 1 = 1 · a = a. (19) Оскiльки поле мiстить в собi два рiзнi вдiленi елементи, то нi порожнiм, нi одноелементним пiдполе бути не може. Двоелементним поле може бути — таким є поле лишкiв за модулем 52 2. Воно складається iз нуля та одиницi i сума двох одиниць дорiвнює нулю. Оскiльки поле замкнене вiдносно додавання, то в полi обов’язково для любого натурального n є 1 + 1 + 1 + ... + 1 n Цей елемент позначається також n. Але варто пам’ятати, що в полi сума одиниць може дорiвнювати нулю. Але якщо сума одиниць не нуль, то для цiєї суми є обернений елемент в полi. Iз сказаного випливає, що коли в полi сума будь-якої кiлькостi одиниць не дрiвнює нулю, то це поле мiстить в собi пiдполе, що iзоморфне полю рацiональних чисел. Поля, в яких сума натуральної кiлькостi одиниць не дорiвнює нулю, називають полями характеристики нуль. Отже поле характеристики нуль мiстить найменше пiдполе, яке iзоморфне полю рацiональних чисел. Найменшим пiдполем поля дiйсних чисел є поле рацiональних чисел. Найменшим пiдполем поля комплексних чисел є також поле рацiональних чисел. Все це поля харктеристики 0. Якщо сума кiлькох одиниць поля дорiвнює нулю, то найменша кiлькiсть одиниць, якi в сумi дають нуль, називається характеристикою цього поля. Теорема 3.3 Ненульова характеристика поля є простим числом 53 Доведення. Доводиться теорема методом вiд протилежного. Припустимо, що p ≥ 2 є характиристикою поля F i p є складеним числом, тобто p = m · n для деяких натуральних чисел m, n ≥ 2. Оскiльки (1 + 1 + 1 + . . . + 1)·(1 + 1 + 1 + . . . + 1) = (1 + 1 + 1 + . . . + 1 = 0, m n mn=p то m · n = 0 в полi F i при цьому m.n ̸= 0 (нагадаємо, що найменшою кiлькiстбю одиниць, якi в сумi дають нуль, є p.) Рiвнiсть mn = 0 для m.n ̸= 0 в полi неможлива, оскiльки в протилежному випадку було б 1 = n−1 m−1 mn = n−1 m−1 · 0 = 0. Теорема 3.4 В полi ненульової характеристики найменшим полем буде поле, яке iзоморфне полю класiв лишкiв за деяким простим модулем. Доведення. Нехай p — ненульова характеристика деякого поля F i F1 ⊆ F , F1 = {0, 1, 2, . . . , p − 1}. Елементи поля Zp позначимо 0, 1, 2, . . . , p − 2, p − 1. Перевiримо, що вiдображення f : F1 → Zp , що задане правилом x → x, є iзоморфiзмом. x ∈ F, 54 Виберемо два натуральнi числа 0 < m, n < p i нехай для деяких q1 , r1 , q2 , r2 ∈ N ∪ {0} в кiльцi цiлих чисел можна записати m + n = q1 p + r1 , тодi в полi Zp m ⊕ n = r1, , m ⋆ n = r2 0 ≤ r1 < p, m · n = q2 p + r2 , 0 ≤ r2 < p. — знаками ⊕, ⋆ позначенi операцiї додавання та множення в полi Zp . В полi F1 (1 + 1 + 1 + . . . + 1)+(1 + 1 + 1 + . . . + 1) = (1 + 1 + 1 + . . . + 1 = m n m +n (1 + 1 + 1 + . . . + 1)+(1 + 1 + 1 + . . . + 1) = (1 + 1 + 1 + . . . + 1 pq1 r1 r1 (1 + 1 + 1 + . . . + 1)·(1 + 1 + 1 + . . . + 1) = (1 + 1 + 1 + . . . + 1 = m n mn (1 + 1 + 1 + . . . + 1)+(1 + 1 + 1 + . . . + 1) = (1 + 1 + 1 + . . . + 1 . pq2 r2 r2 Наведенi рiвностi переконують в узгодженостi вiдображення f з операцiями додавання та множення в F1 та в Zp . Також вiдображення f узгоджене з нульмiсними операцiями — видiленi елемнети 0 та 1 переходять у видiленi елементи 0 та 1. Видно, що вiдображення f бiєктивне. В такому разi перевiряти узгодежнiсть вiдображення f з одномiсною операцiєю знаходження оберненого не потрiбно — це випливає iз решти узгодженостей. 55 Те, що вiдображення f є iзоморфiзмом, доведене. Отже i вся теорема доведена. Найменшим пiдполем поля Z2 (i) = {0, 1, i, 1 + i}, в якому додавання та множення заданi таблицями 3.1, є поле Z2 . x y x+y xy 0 0 0 0 0 1 1 0 0 0 i 1+i i 1+i 0 0 1 0 1 0 1 1 1 1 i 1+i 0 1+i i 1 i 1+i i i i i 1+i 1+i 1+i 1+i 0 1 i 1+i 0 1 i 1+i i 1+i 0 1 1+i i 1 0 0 i i+1 1 0 1+i 1+i i Табл. 4: Таблиця додавання та множення в полi Z2 (i) = {0, 1, i, 1 + i} Множення в полi Z2 (i) = {0, 1, i, 1 + i} визначається рiвнiстю i2 = i + 1, а додавання визначається тотожнiстю x + x = 0, — це поле характеристики 2. Також полем характеристики 2 буде поле Z2 (j ) = {0, 1, j, 1+ j, j 2 , 1 + j 2 , j + j 2 , 1 + j + j 2 .} В цьому полi j 3 = j + 1 i x + x = 0 для будь-якого x ∈ Z2 (j ). Найменшим пiдполем поля Z2 (j ) є поле Z2 . 3.2 Найменша пiднапiвгрупа Сигнатура напiвгрупи не мiстить видiлених елементiв, тому є порожня напiвгрупа. Звiдси випливає, що найменшою пiднапiвгрупою в будь-якiй напiвгрупi є порожня. 3.3 Найменша група Група мiстить видiлений елемент — одиницю, якщо операцiю названо множенням, тобто в мультиплiкативнiй групi, i нуль, 56 коли операцiю названо додаванням (в адитивнiй групi). В загальному випадку видiлений елемент називають нейтральним вiдносно бiнарної операцiї групи. Множина, яка складається лише iз видiленого елемента, замкнена вiдносно бiнарної операцiї. Тому найменшою пiдгрупою в будь–якй групi є одноелементна пiдгрупа — вона складається лише iз видiленого елемента. 3.4 Найменше пiдполе, що мiстить заданий елемент Нехай F — певне поле, F1 — його найменше пiдполе, i α ∈ F \ F1 . Найменше пiдполе F2 , F1 ⊆ F2 ⊆ F , що мiстить в собi α, називають розширенням поля F1 за допомогою елемента α. розрiзняють два випадки — коли α є коренем якогось ненульового многочлена з коефiцiєнтами iз F1 , i коли α не корiнь някого ненульового многочлена з коефiцiєнтами iз F1 . В першому випадку кажуть про алгебраїчне розширення поля, а в другому — про трансценентне розширення поля. В першому випадку поле F2 складається лише iз многочленiв вiд α з коефiцiєнтами iз найменшого пiдполя, а в другому F2 складається iз дробiв вигляду a0 + a1 α + . . . + an αn , b0 + b1 α + . . . + bm αm ai , bj ∈ F1 (0 ≤ i ≤ n, 0 ≤ j ≤ m), b0 +b1 α+. . .+bm αm При доведеннi сказаного використовують знання про найбiльший спiльний дiльник двох многочленiв. Проводити ретельне доведення не будемо. 57 3.5 Найменша пiднапiвгрупа, що мiстить заданий елемент Якщо мультиплiкативна напiвгрупа мiстить елемент α, то будьяка пiднапiвгрупа обов’язково мiстить всi натуральнi степенi цього елемента. А з другого боку, всi натуральнi стпенi заданого елемента замкненi вiдносно множення. Тому найменша пiднапiвгрупа, що мiстить заданий елемент, складається iз усiх натуральних степенiв цього елемента. Так елементи 2, 22 , 23 . . . , 2n , . . . утворюють найменшу пiднапiвгрупу, що мiстить в собi 2. Якщо операцiя в напiвгрупi називається додаванням, то кожна пiднапiвгрупа разом з елементом α мiстить в собi всi кратнi цьому елементу, тобто 2α, 3α, . . . , nα, . . . . Так в адитивнiй напiвгрупi цiлих чисел найменшою пiднапiвгрупою, що мiстить число 2, буде 2, 4, 6, . . . , 2k, . . . . 3.6 Найменша група, що мiстить заданий елемент Нехай операцiя групи G названа множенням i α ∈ G. Тодi з одного боку в будь-якiй пiдгрупi повиннi мiститися всi цiлi (як додатнi так i вiд’мнi) степенi елемента α, а з другої сторони, всi цiлi степенi одного елемента утворюють пiдгрупу. Отже найменша пiдгрупа, що мiстить заданий елемент α, складається iз усiх цiлих степенiв цього елемента. Ця пiдгрупа називається циклiчною. 58 3.7 Найменший пiдунар, що мiстить заданий елемент Нехай M — множина, f : M → M — вiдображення, ⟨M, f ⟩ — унар i α ∈ M. Вводимо позначення f n (α) = f (f (f (. . . f ( α)) . . .), n n ∈ N, f 0 (α) = α. Використовуючи введене позначення ми можемо сказати, що будь-який пiдунар який мiстить в собi α, мiстить в собi всi f n (α), n ∈ N, а з другого боку всi елементи„ якi можна записати у виглядi f n (α), n ∈ N ∪ {0}, замкненi вiдносно вiдображення f i, таким чином, утворюють пiдунар. Звiдси випливає, що найменшим пiдунаром, який мiстить заданий елемент α складається iз f n (α), n ∈ N ∪ {0}. 3.8 Алгоритм знахоження всiх пiдалгебр заданої унiверсальної алгебри Щоб знайти всi пiдалгебри унiверсальної алгебри, потрiбно для кожного її елемента знайти найменшу пiдалгебру, що мiстить цей елемент. Такi пiдалгебри в загальному випадку називають однопородженими. Однопородженi групи називають циклiчними. На наступному кроцi шукають точну верхню межу пiдмножини таких однопороджених пiдалгебр. Цими точними верхнiми межами вичерпуються всi пiдалгебри. Наведемо приклади унiверсальних алгебр та гратки всiх її пiдалгебр. Приклад 1 гратки L та гратки S (L) всiх її пiжграток Гратка L = {a, b, c, d} задана за допомогою часткового порядку a < b, a < c, b < d, c < d. 59 Ця гратка має дiаграму d b c a Гратка S (L) має дiаграму {a, b, c, d} {a, b, d} {a, b} {b} {b, d} {a} {a, d} {a, c, d} {a, c} { d} {c, d} {c} ∅ Приклад 2 гратки B(M ) всiх пiдмножин чотириелементної множини M = {a, b, c, d} 60 {a, b, c, d} {a, b, c} {a, b} {a, c} {a, b, d} {b, c} {a, c, d} {b, c, d} {a, d} {c} {b, d} {d } {c, d} {a} {b} ∅ Гратку всiх пiдмножин чотириелементної множини можна назвати чотиривимiрним кубом. Приклад 3 гратки L(U ) всiх пiдунарiв унара U = ⟨U, f ⟩, де U = {a1 , a2 , a3 , a4 , b1 , b2 , b3 , b4 }, а вiдображення f : U → U задане графiчно наступним чином. {a1 } {a4 }   U {a2 } {b1 } 6 - {b2 } ? {b4 } {a3 } {b3 }  Гратка L(U ) всiх пiдунарiв має вигляд 61 U U3 U1 U2 U4 ∅ де U1 = {b1 , b2 , b3 , b4 }, U2 = {a2 , a3 , a4 }, U3 = U1 ∪U2 = {a2 , a3 , a4 , b1 , b2 , b3 , b4 }, U4 = {a1 , a2 , a3 , a4 }. Приклад 4. Розглядаємо группу G, яка складається iз усiх обертань площини, що переводять правильний n−кутник в себе. Ця група називається циклiчною. Вона складається ·k iз усiх обертань правильнийа n−кутника на кути 2π n ,k = 0, 1, 2, . . . n − 1. Гратка пiдгруп цiєї групи iзоморфна гратцi всiх дiльникiв числа n — дiльнику d числа n ввiдповiдає пiд·d·k група обертань на кути 2πn , k = 0, 1, 2, . . . n d − 1. Коли n = 30 = 2 · 3 · 5, то гратка всiх пiдгруп зображена на рис. 8, А коли n = 175 = 7 · 52 , то гратка всiх пiдгруп iзоморфна гратцi пiдунарiв попереднього прикладу. Приклад 5 всiх пiдгруп групи S3 симетрiй правильного трикутника. Нехай правильний трикутник має вершини 1,2,3 62 3 1 2 Симетрiї переводять вершини у вершини i ми можемо цi симетрiї задати саме як вiдображення iз множини вершин у множину вершин. Таким чином ми можемо записати, що S3 = {e, a, b, c, x, y }, де ( ) ( ) ( ) ( ) 1 2 3 1 2 3 1 2 3 1 2 3 , a= , b= , c= , e= 1 2 3 1 3 2 3 2 1 2 1 3 ( ) ( ) 1 2 3 1 2 3 e= , e= , 2 3 1 3 1 2 Група S3 має 4 пiдгрупи. Двi з них — одинична {e} та вся група S3 , є тривiальними. I ще є три двоелементнi пiдгрупи: A = {e, a}, i одна триелементна D = {e, x, y }. Дiаграма чвм пiдгруп групи S3 має вигляд S3 A B C D B = {e, b}, C = {e, c}, {e} 63 1 b c a a 1 b c 0 Рис. 14: Гратка N5 0 Рис. 15: Гратка M3 3.9 Забороненi гратки Розгладаючи ту чи iншу гратку звертають увагу на те, чи є в нiй пiдгратки, що iзоморфнi N5 , або M3 (див рис. 14, 15) Справа в тому, що в роботi зручно користуватися розподiльним (дистрибутивним) законом, що з’єднує додавання та множення чисел x(y + z ) = xy + xz. (20) Якщо назвати операцiю знаходження точної верхньої межi додаванням, а операцiю знаходження точної нижньої межi множенням, то зручними в роботi виявляються тi гратки, в яких виконується розподiльний закон (20). В гратках N5 та M3 розподыльний закон не виконується. Так в гратцi N5 a+c = b+c = 1, b(a+c) = b·1 = b, b(a+c) = b·1 = b, 64 ba = a, bc = 0, ba+bc = a+0 = a ̸= b. ba+bc = 0+0 = 0 ̸= b. В гратцi N5 також a+c = b+c = 1, ba = 0, bc = 0, Звiдси робимо висновок, що коли гратка має в собi пiдгратку, що iзоморфна однiй iз граток N5 чи M3 , то операцiї знаходження точний верхньої та нижньої межi не зв’язанi мiж собою розподiльним законом. Можна довести, що i зворотне твердження правильне, якщо операцiї знаходження точний верхньої та нижньої межi не зв’язанi мiж собою розподiльним законом, то гратка має в собi пiдгратку, що iзоморфна однiй iз граток N5 чи M3 . 4 4.0.1 Ординальнi числа. Цiлком впорядкованi множини Коли мова йшла про математичну iндукцiю, ми згадували принцип найменшого числа, згiдно якого в будь-якiй непорожнiй пiдмножинi множини натуральних чисел iснує найменше число — число, що менше будь-якого iншого числа в цiй пiдмножинi. Цей принцип найменшого числа для натуральних чисел може бути узагальнений на iншi множини. Лiнiйно впорядкованi множини, в яких кожна непорожня пiдмножина має найменший елемент, називають цiлком впорядкованими множинами. Цiлком впорядкованi множини є — наприклад, множина натуральних чисел. Вiдмiтимо кiлька властивостей цiлком впорядкованих множин. Теорема 4.1 Якщо P — цiлком впорядкована множина i f : P → P є строго монотонним вiдображенням, то для будьякого x ∈ P буде f (x) ≥ x. 65 Доведення. Доведення методом вiд протилежного. Нехай A ⊆ P є пiдмножиною тих елементiв iз P , для яких f (x) < x. Якщо ця пiдмножина не порожня, то в нiй є найменший елемент — позначимо його a. Тодi f (a) < a i f (a) = b ∈ / A, f (b) ≥ b. А це суперечить тому, що функцiя f монотонна i b < a ⇒ f (b) < f (a) = b. Вiдтинком чвм A називають пiдмножину B ⊆ A, яку для деякого x ∈ A можна представити у виглядi B = Ax = {y ∈ A|y < x}. Теорема 4.2 Нехай P — цiлком впорядкована множина i Q = Px її вiдтинок для деякого x ∈ P . Стверджується, що не iснує строго монотонної функцiї f : P → Q. Доведення. Правильнiсть сказаного в теоремi 4.2 випливає з теореми 4.1 — для монотонної функцiї f за теоремою 4.1 буде f (x) ≥ x i f (x) ∈ / Q. Теорема 4.3 . Для будь-яких двох цiлком впорядкованих множин P, Q виконується одна i тiльки одна iз наступних трьох умов 1. Чвм P подiбна (iзоморфна) чвм Q. 2. Чвм P подiбна (iзоморфна) деякому вiдтинку Qy чвм Q. 3. Чвм Q подiбна (iзоморфна) деякому вiдтинку Px чвм P . 66 Доведення. Нехай маємо двi цiлком впорядкованi чвм — P та Q. Будуємо вiдповiднiсть f мiж елементами P та Q — (x, y ) ∈ f в тому i тiльки тому випадку, коли вiдтинки Px та Qy подiбнi (iзоморфнi). Перевiримо, що f є функцiональною вiдповiднiстю, точнiше, перевiримо, що (x, y1 ), (x, y2 ) ∈ f ⇒ y1 = y2 ; (x1 , y ), (x2 , y ) ∈ f ⇒ x1 = x2 . (21) Дiйсно, якщо (x, y1 ), (x, y2 ) ∈ f i y1 < y2 , то чвм Qy1 подiбна Qy2 i Qy1 є вiдтинком Qy2 . А таке неможливе згiдно теореми 2. Отже y1 = y2 . Подiбним чином перевiряється, що коли (x1 , y ), (x2 , y ) ∈ f то x1 = x2 . Перейдемо до бiльш звичного зi школи запису вiдображень. Функцiональне вiдношення f задає два взаємно обрененi вiдображення u : P → Q i v : Q → P : (x, u(x)) ∈ f, (v (y ), y ) ∈ f. Вiдображення u, v частковi. Вiдображення u i v монотоннi. Для перевiрки вiзьмемо a, b ∈ P , для яких a > b i визначенi елементи u(a) = c, u(b) = d. Iснування елементiв c, d ∈ Q означає iснування двох подiбностей α : Pa → Qc , δ : Qd → Qc , β : Pb → Qd . h(x) = α · β −1 (x). Оскiльки a > b, то Pb ⊂ Pb i визначена подiбнiсть За теоремою 4.2 подiбнiсть h може iснувати лише у випадку, коли d < c. Монотоннiсть доведена. Далi перевiримо, що виконуєтсья одна iз умов — або ∀x ∈ P ∃y ∈ Q((x, y ) ∈ f ), 67 (22) або ∀y ∈ Q∃x ∈ P ((x, y ) ∈ f ), (23) Перевiряємо методом вiд протилежного. Припустимо, що обидвi умови порушуються. Отже, припускаємо, що для деякого p ∈ P не iснує y ∈ Q такого, що (p, y ) ∈ f i для деякого q ∈ Q не iснує x ∈ P такого, що (x, q ) ∈ f . В множинi таких p виберемо найменший, i в множинi таких q виберемо найменший — знову позначаємо їх p та q . Отже p це найменший елемент у множинi {x ∈ P |∀y ∈ Q((x, y ) ∈ / f )} а елемент q найменший у множинi {y ∈ Q|∀x ∈ P ((x, y ) ∈ / f )}. Подiбнiсть мiж вiдтинками Pp та Qq (якої за припущенням не iснує) встановлюється вiдношенням f . Перевiркою цього i займемося. Спочатку перевiряємо, що коли x ∈ Pp i (x, y ) ∈ f, то y ∈ Qq . Справдi (метод вiд протилежного), якщо y ∈ / Qq , то y ≥ q . Подiбнiсть w : Qy → Px встановлює подiбнiсть мiж Qq i w(Qq ) — а такої подiбностi, за припущенням< не iснує. Одержана суперечнiсть доводить, що y < q, y ∈ Qq . Ми уже перевiрили, що вiдображення u : Pp → Qq є повним (не частковим), монотонним, iн’ктивним та сюр’ктивним (див. (21)). Таким чином ми перевiрили, що вiдображення u : Pp → Qq є подiбнiстю (iзоморфiзмом). А це суперечить припущенню, що вiдтинок Pp е подiбний нiякому вiдтинку Qy . Ми одержали суперечнiсть, яа доводить, що одна iз умов (22)(23) виконується. Тепер маємо три випадки 1. виконуєтсья умова (22) але не виконується умова (23) 68 2. виконується умова (23) але не вионується умова (22) 3. виконуються обидвi умови (22), (23). В першому випадку вiдобаження u встановлює подiбнiсть мiж P та вiдтинком Qq ; в другому випадку вiдображення v втановлює подiбнiсть мiж Q та вiдтинком Pp ; i в третьому випадку обидва вiдображення u, v встановлюють подiбнiсть мiж цiлком впорядкованими множинами P а Q. Теорема 4.3 доведена повнiстю. 4.0.2 Мотивацiя вивчення ординалiв В цьому мiсцi варто зупинитися i звернути увагу на те, що ми працюємо з речами, якi важко уявити у свiтi матерiальних речей. Тобто ми працюємо в свiтi абстрактного. Щоб тут працювати, потрiбен певний досвiд, певнi навички. На цю роботу можна мати досить негативну точку зору i, вiдповiдно, називати її схоластикою, на вiдмiну вiд роботи з графiками, фiзичними процесами, поверхнями та подiбним. На сьогоднi навички роботи з цiлком впорядкованими нескiнченними множинами є важливими в практичнiй роботi по перевiрцi дiєздатностi програм для ЕВМ — в так званiй верифiкацiї програм. Звичайно, для програми пiдбирається параметр, який знаходиться в цiлком впорядкованiй множинi, на кожному кроцi роботи цей параметр зменшується. А спадна послiдовнiсть елементiв цiком впорядкованої множини завжди скiнченна (кажуть, що цiлком впорядкована мноижна задовольняє умову обриву спадних послiдовностей - умова осп, або уосп). Тому програма з таким параметром за скiнченну кiлькiсть крокiв буде виконана. До 69 теперiшнiх часiв робота з цiлком впорядкованими множинами вiдносилась до вузькоспецiальних роздiлiв математики. 4.0.3 Ординали, ординальнi числа. Багато книг з математики в передмовi попереджають: для розумiння матерiалу спецiальнi знання не потрiбнi, вимагається лише певна культура — читай, досвiд. Будемо вважати, що читач уже придбав певну культуру. Отже можна ввести наступне поняття — ординальне число, або ординал. Нехай A цiком впорядкована множина. Розглянемо нову множину B = {Ax |x ∈ A} Вона природно подiбна множинi A, подiбнiсть встановлюється каноннiчним вiдображенням x → Ax . Далi вiдтинки Ax таким же чином замiнюємо на iзоморфну цiлком впорядковану множину вiдтинкв вiтинка. Оскiльки цiлком впорядкована множина задовольняє умов осп, то послiдовнiсть конкретних замiн завжди закiнчується порожньою множиною. Таки чином одержується канонiчна цiлком впорядкована множина, яку називають ординалом. Тепер дамо визначення ординалу. Ординал A визначається умовами • ординал є множиною, елементами якої є множини; • Ординал є цiлком впорядкованою множиною, причому порядок x ≤ y збiгається з вiдношенням x ⊆ y на множинах; • Ординал є транзитивною множиною в тому розумiннi, що коли x ∈ A i y ∈ x, то y ∈ A. 70 Множина ординалiв позначається On. Вона цiлком впорядкована вiдношенням включення це випливає iз теореми 3. Кожен ординал має найменший елемент множину ∅. Цей ординал позначається 0. цей ординал найменший. Наступний ординал має один елемент {∅}. Вiн позначається 1. Якщо ординали 0, 1, 2, . . . , n − 1 уже є, то ординал {0, 1, 2, . . . , n − 1} позначається через n. Є ординал, який складається iз усiх ординалiв, що п означенi натуральними числами та 0 — це так званий ординал ω . За ним iде ординал ω + 1 ω + 1 = {0, 1, 2, . . . , n, . . . , ω }. Над ординалами можна виконувати операцiї додавання, множення, пiднесення до степеня. Але цього вже торкатися не будемо. Про ординали можна прочитати в iнтернет-файлi t2_set.pdf М.М.Попова “Аксiоматична теорiя множин“ Цей файл використаний при пiдготовцi тексту. 71 Покажчик адреса елемент елемента у свиску, 26 масимальний, 11 алфавiт, 12 мiнiмальний, 12, 39 алгебра найбiльший, 11, 38 однопороджена, 59 найменший, 12, 39 унiверсальна, 47 елементи алгоритм непорiвнюванi, 11, 17 породження всiх пiдмножин, порiвнюванi, 11 14 гра сортування, 26 Пенi, 16 асоцiативнiсть, 51 камiнь-папiр-ножицi, 16 бази даних гратка iєрархiчнi, 22 пiдалгебр, 47 бiєкцiя, 23, 24 пiдграток, 59 буква, 12 пiдгруп, 62 число пiдунарiв, 61 ординальне, 65 група, 57 чвм, 11 адитивна, 58 пiдалгебр , 48 циклiчна, 58, 59, 62 подiбнi, 23 мiльтиплiкативна, 58 дистрибутивнiсть, 51 групоїд, 5 дiаграма характеристика чвм, 16 поля, 56 доповнення iєрархiя, 23 бiнарного вiдношення, 4 класiв безпеки, 23 доведення iнфiмум, 39 методом вiд протилежного, iзоморфiзм 54, 66 частково впорядковах мно72 жин, 38 чвм, 24 полiв, 56 кiльце, 51 ключ, 22 ключi в базах даних, 23 в шифруваннi, 23 комутативнiсть, 51 лiнiйний вибiр, 26 з обмiном, 26 з пiдрахунком, 26 магма, 5, 7 межа найбiльша нижня, 39 найменша верхня, 39 нижня, 38 точна нижна пiдалгебр, 49 точна нижня, 38 точна верхня, 38 пiдалгебр, 49 верхня, 38 мiркування з точнiстю до iзоморфiзму, 38 множення асоцiативне, 7 множина цiлком впорядкована, 65 частково впорядкована, 10 транзитивна, 71 унiверсальна, 4 замкнена вiдносно операцiї, 48 мова ЛIСП, 3 набiр ключiв, 22 напiвгрупа, 6, 58 напiвгупа, 7 носiй унiверсальної алгебри, 47 нуль напiвгрупи, 7 об’єднання бiнарних вiдношень, 4 елементiв чвм, 39 обмiн основний, 26 стандартний, 26 одиниця напiвгрупи, 7 ординал, 65, 70 осп, 70 перацiя, 42 перетин бiнарних вiдношень, 4 елементiв чвм, 39 пiдалгебра, 47, 72 найбiльша, 49 найменша, 49 пiдгрупа 73 циклiчна, 57, 58 найменша, 57 пiдмножина обмежена знизу, 38 обмежена зверху, 38 пiднапiвгрупа, 58 найменша, 58 порожня, 56 пiдполе найменше, 53 пiдунар, 59 найменший, 59 подiбнiсть чвм, 23 поле, 22 Q(2), 51 Q(3), 51 Z2 (i), 56 Z2 (j ), 56 Zp , 56 характеристики 0, 56 ненульової характеристики, 56 порядок алфавiтний, 12 частковий, 10 деревоподiбний, 22 лексикографiчний, 12 лiнiйний, 10 пошук в чвм, 14 принцип найменшого числа, 65 проблема пошуку, 22 просiювання, 26 рiзниця бiнарних вiдношень, 4 розширення поля, 57 розширення поля алгебраїчне, 57 трансцендентне, 57 сигнатура унiверсальної алгебри, 47 симетрична рiзниця бiнарних вiдношень, 4 слово, 12 список, 26 супремум, 39 шифрування, 23 тiло, 52 умова осп, 70 вiдношення, 3 антирефлексивне, 8 антисиметричне, 8 бiльше або дорiвнює, 10 бiнарнi, 3 часткоого строгого поряд- 74 ку, 9 3 часткового нестрогого поряд- префiксний, 3 ку, 9 префiксний польський, 3 лiнiйного нестрогого порядсуфiксний, 3 ку, 9 запис зворотний суфiксний, 3 лiнiйного строгого порядку, звуження 9 операцiї, 48 менше або дорiвнює, 10 не строгого порядку, 10 нетранзитивне, 15 обернене, 8 покривати, 16 рефлексивне, 8 симетричне, 8 сторого порядку, 10 строго бiльше, 10 строго менше, 10 транзитивне, 8 вiдтинок чвм, 66 властивостi нуля, 51 вставка, 26 закон розподiльний, 51 запис iнфiксний, 3 постфiксний, 3 постфiксний з дужками, 3 постфiксний кембрiджський, 75