Упорядковані множини. Бінарне відношення порядку

Визначення 5.1. Упорядкованою називається множина із заданим відношенням порядку : .

Символ означає порівнянність елементів множини : .

Визначення 5.2. Бінарним відношенням порядку (упорядкованості) називається рефлексивне, антисиметричне й транзитивне відношення:

1) рефлексивність означає, що кожний елемент порівняний сам із собою:

; (5.1)

2) антисиметричність означає, що якщо елемент порівняний з елементом , а порівняний з , то та співпадають: ;

, тобто ; (5.2)

3) транзитивність: якщо елемент порівняний із елементом , а порівняний із , то порівняний із :

,

тобто . (5.3)

5.2 Типи порядку (лінійний, частковий, передпорядок)

Визначення 5.3. Бінарне відношення, що має властивості анти­рефлексивності, антисиметричності й транзитивності, називається відношенням строгої впорядкованості й позначається .

Визначення 5.4. Бінарне відношення, що має властивості рефлексивності й транзитивності, називається відношенням передпорядку.

Визначення 5.5. Множина називається лінійно (повністю) упорядкованою, якщо будь-які два його елементи порівнянні, тобто, або , інакше – множина є частково впорядкованою (існують непорівняні між собою елементи).

Приклад 5.1. На множині дійсних чисел відношення порядку встановлюється за принципом порівнянності ”менше або дорівнює” (рис. 5.1): . Виконання аксіом 1 – 3 очевидно.

Рисунок 5.1 – Відношення лінійного порядку на множині дійсних чисел

Приклад 5.2. Для множини елементи булеану упорядковуються за включенням та утворюють частково впорядковану множину , що зображено діаграмою (рис. 5.2).

Рисунок 5.2 – Частково впорядкована множина із прикладу 5.2

Частково впорядковані множини зображуються у вигляді графів – діаграм Хасе , – у яких вилучені всі петлі та всі транзитивно замикаючі дуги, і позначаються . Діаграма Хасе відома у генеалогії з XIX ст. і використовувалася при заданні споріднення.

Таким чином, діаграма Хасе є графом, вершини якого є елементи множини (домену або класу), а з'єднуючі їх лінії (ребра або дуги) установлюють зв'язки між елементами безлічі (домена або класу), що інтерпретуються як відношення часткового порядку.

Дана теоретична концепція реалізується в мовах об’єктно-орієнтованого програмування, зокрема, C#.

Приклад 5.3. Видалення з діаграми (див. рис. 5.2), що ілюструє включення елементів булеана триелементної множини один до одного, всіх петель і всіх транзитивно замикаючих дуг дає діаграму Хасе, що також зображує частково впорядковану множину (рис. 5.3).

Рисунок 5.3 – Діаграма Хасе для множини із прикладу 5.2

Приклад 5.4. Коди можна розглядати як деякі геометричні просторові фігури. Тріаду можна зобразити у вигляді одиничного куба, що має координати вершин, які відповідають двійковим символам (рис. 5.4). Вершини одиничного куба відповідають уявленню чисел 0 – 8 у двійковій системі числення.

Рисунок 5.4 – Геометричне зображення кодів у вигляді діаграми Хасе

Визначення 5.6. Елемент покриває елемент , якщо

та

При цьому називається старшим елементом.

Можна розглядати відношення покриття в упорядкованій множині.

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

Визначення 5.8. Нехай . Мінімальний (максимальний) елемент із множини мажорант (мінорант) називається верхньою (нижньою) гранню.

Визначення 5.9. Нехай . Найменший (найбільший) елемент множини всіх верхніх (нижніх) граней називається точною верхньою (нижньою) гранню множини й позначається ().

В упорядкованому сімействі множини порожня множина є нульовим елементом, тобто ; універсум – одиничним елементом, тобто .

Приклад 5.5. Нехай множина частково впорядкована відношенням включення : (рис. 5.5). Елемент покриває елемент , тобто , отже, є старшим у порівнянні з .
На множині розглядаються дві підмножини: ; . Множина верхніх граней для визначається
як сукупність , нижня грань – . Супремум є найменша
з верхніх граней: , інфімум , при цьому жодна
із зазначених граней не належить до B1. Mножина верхніх граней – , а множина нижніх граней є сукупність елементів . Тоді , , тобто обидві точні грані належать множині .

Рисунок 5.5 – Частково впорядкована множина

Теорема 5.1. Упорядкована множина М містить не більше одного найбільшого (найменшого) елемента.

Доведення. Якщо припустити, що існує більше одного найбільшого (найменшого) елемента, тобто й – два найбільших (найменших) елементи, тоді або ( або ), отже, в силу антисиметричності одержуємо – єдиний найбільший (найменший) елемент. Що й було потрібно довести.

Визначення 5.10. Відношення (або ) називається зворотним до бінарного відношення , якщо виконується умова:

.

Принцип подвійності: відношення, зворотне відношенню впорядкованості, є відношенням упорядкованості. Упорядковані множини й двоїсті, якщо визначено на тому самому носії за допомогою зворотного відношення .

Відношення, зворотне до відношення впорядкованості, ілюструється діаграмою, двоїстою до діаграми Хасе.

Приклад 5.6. На триелементній множині із прикладу 5.5 задане зворотне відношення , яке можна проілюструвати діаграмою (рис. 5.6).

Рисунок 5.6 – Діаграма, зворотна до діаграми Хасе із прикладу 5.5

Визначення 5.11. Ланцюгом називається підмножина впорядкованої множини. Довжина ланцюга визначається як , де – потужність носія.

Приклад 5.7. Підмножина із прикладу 5.5 є ланцюгом у множині . Довжина обчислюється відповідно до визначення 5.11 і дорівнює: .

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

Приклад 5.8. Висота елемента в множині (див. приклад 5.5, рис. 5.5) визначається максимумом довжин ланцюгів і . Оскільки обидві ланцюги мають довжину 2, то висота елемента також дорівнює 2: .

Визначення 5.13. Довжиною впорядкованої множини називається максимум довжин ланцюгів у або максимум висот його елементів:

.

Приклад 5.9. Довжина множини із прикладу 5.5, за визначенням 5.13 дорівнює:

.

5.3 Контрольні запитання

1. Яке відношення називається відношенням порядку?

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

3. Яка множина називається впорядкованою?

4. Чим відрізняється лінійний порядок від часткового?

5. Чим відрізняється строгий порядок від нестрогого?

6. Як формулюється аксіома антисиметричності бінарного відношення?

7. Що таке діаграма Хасе?

8. Як визначається покривальність елементів у частково впорядкованій множині?

9. Які елементи називаються порівнянними в частково впорядкованій множині?

10. Що таке верхня (нижня) грань?

11. Який елемент в упорядкованій множині називається найбільшим (найменшим)?

12. Як визначається супремум та інфімум у частково впорядкованій множині?

13. Яка множина називається ланцюгом?

14. Як визначається довжина ланцюга?

15. Як визначається висота елемента?

16. Як визначається висота частково впорядкованої множини?

17. Який елемент називається старшим?

6 Структури. Алгебраїчні системи. Ізоморфізм

Структура – від латинського: розташування, будова. Щоб визначити структуру, задають відношення, у яких перебувають елементи множини, та аксіоми структури.

Поняття структури відноситься до середини XIX ст. Уперше його ввів німецький математик Дедекинд Рихард Юліус Вільгельм. Термін “структура” належить американському вченому Гаррету Біркгофу із Принстонського університету.