Лекція 4. Ускладнення математичних об’єктів. Розширення уявлень про відношення
У даній лекції будуть розглянуті частковий випадок відношення часткового порядку, що призводить до важливого поняття решітки, і замикання відношень.
1. Решітки. Розпочнемо з фундаментального поняття решітки.
Визначення. Решіткоюназвемо частково впорядковану множину, кожні два элементи a,b якої мають нижню (позначимо через a È b) і верхню (позначимо через a Ç b) грані.
а) б) в) г)
Рис.11. Приклади діаграм частково впорядкованих множин.
На рис. 11 зображені діаграми чотирьох частково впорядкованих множин. Перші два з них становлять важливі приклади решіток; четверте – також решітка. Третя множина не є решіткою.
Замикання відношень. Поняття замикання є фундаментальним математичним поняттям і використовується в більшості розділів математики. Щоб продемонструвати це поняття, розглянемо наступний приклад.
Візьмемо об’єкт x0 і процес p, який породжує множину і визначає послідовність x1, x2, ...,xn,... таку, що
x1 Î p(x0),
x2 Î p(x1),
...
xn Î p(xn-1),
...
Множина, що містить всі елементи всіх послідовностей, які можуть бути виділені за допомогою р, і що починаються з x0, називається замиканням процесу р відносно x0. Тому “відповідь” буде міститись в р(xn) при певному n. Однак ми не знаємо завчасно значення n. Більш того, якщо ми візьмемо випадковий елемент y з цього замикання і виконаємо процес р,починаючи з y, то не отримаємо нічого нового. Результат вже міститься в замиканні. Множина не може бути розширеною таким шляхом (вона замкнена).
Приклад. Візьмемо квадрат S, розмічений, як це показано на рис.12, і визначимо процес r наступним чином. З заданого положения S процес r породжує множину всіх положень, що отримаються в результаті повороту квадрата за годинниковою стрілкою на прямий кут.
А В D A
![]() | |||
![]() | |||
D C C B
Рис. 12 Рис. 13
Таким чином, r(S) дає кофігурацію, зображену на рис.13. Після застосування r чотири рази, ми повернемося до положення, з котрого розпочали процес, і, отже, замикання в даному випадку є множина з чотирьох позицій.
A B D A C D B C
, , , .
D C C B B A A D
Розглянемо тепер, що відбудеться, якщо процес визначити за допомогою відношення. (В дійсності, це завжди можливо, що ми можемо визначити потрібне відношення за допомогою множини {(x, y): y Î p(x), де р – досліджуваний процес}).
Для побудови замикання відношення a на множині R попередньо введемо поняття n-го ступеня відношення a. Саме шляхом звичайного теоретико-множинного комбінування ступенів відношення a можна отримати замикання відношення a на множині R.
Визначення. n-им ступінь відношення a на множині R (позначається an) визначається наступним чином:
1) ri a1 rj тоді і тільки тоді, коли ri a rj;
2) ri an rj для n > 1 тоді і тільки тоді, коли існує такий елемент rt множини R, що ri a rt і rt an-1 rj.
Визначення. Транзетивним замиканням (чи просто замиканням) відношення a на множині R називається нескінченне об’єднання
Транзитивне замикання відношення a на множині R позначають a+.
![]() |
Можна також визначити транзитивне замикання таким чином: ri a+ rj тоді і тільки тоді, коли ri an rj для деякого n ³ 1. Або ri a+ rj , якщо існує така послідовність r1, r2,...,rk із нуля і більше елементів множини R, що ri a r1, r1 a r2, ..., rk-1 a rk , rk a rj.
Транзитивність замикання відношення a на множині R є наслідком, очевидно, означення замикання.
Приклад. 1. Нехай a – відношення на множині N таке, що a = {(x, y): y = x + 1}. Тоді a+ = {(x, y): x < y}.
2. Нехай L – множина станцій Київского метро і a, b та c – послідовно розташовані його станції. Якщо відношення a1 на L визначене як a1 = {(x, y): x є наступною за у станцією}, то (a, b) і (b, c) Î a1 і (a,a), (b,b), (c,c) і (a,c) Î a12. Отже, a1+ = L´L.
На цих прикладах видно, що замикання відношення в загальному випадку не є рефлексивним. Однак іноді зручно зробити його таким. Це можна легко зробити. Приймемо, що еквівалентне відношення I = {(x, x) | x Î R} на множині R, є нульовим ступенем будь-якого відношення на множині R. Таким чином, a0 = I для будь-якого a на множині R.
Визначення. Рефлексивним замиканням відношення a множині R (позначається a*) називається множина
![]() |
Можна також визначити рефлексивне замикання таким чином:
1) ri a* ri для всіх ri Î R;
2) ri a* rj , якщо ri a+ rj;
3) в a* немає нічого іншого, крім того, що міститься там згідно з 1) і 2).
Замикання відношень пов’язані між собою очевидним співвідношенням a* = a+ È I.
Приклад. Використовуючи відношення a, визначене в попередньому прикладі, отримуємо a* = {(x,y): x £ y).