Властивості бінарних відношень
Розглянемо спеціальні властивості бінарних відношень, що широко використовуються при побудові та дослідженні відношень переваги.
Рефлексивність. Бінарне відношення R називається рефлексивним, якщо справедливо . Очевидно, що в цьому разі також . Таким чином, рефлексивне відношення виконується для однакових елементів, тобто Введемо предикат від бінарного відношення, який істинний тоді і лише тоді, коли R – рефлексивне.
Антирефлексивність. Ця властивість є протилежною до рефлексивності. Відношення R називається антирефлексивним, якщо жодний елемент не знаходиться в цьому відношенні сам із собою, тобто . Через операцію перетину це можна записати як , а через включення – як Також подібно до попередньої властивості введемо предикат антирефлексивності .
Симетричність. Відношення R є симетричним, якщо разом із кожною впорядкованою парою, що належить відношенню, воно містить і пару із переставленими компонентами, тобто . Інакше це можна виразити як . Відповідний предикат будемо позначати . Легко показати, що .
Асиметричність. Для асиметричного відношення R виконується , тобто щонайбільше одна пара з та належить такому відношенню. Через операцію перетину це можна записати як . Предикат асиметричності позначатимемо .
Антисиметричність. Відношення R називається антисиметричним, якщо , тобто такому відношенню належать щонайбільше одна пара із різними компонентами з та , та, можливо, пари однакових елементів. За допомогою операцій над відношеннями це можна записати як . Предикат антисиметричності отримує позначення .
Відношення називається симетричною частиною вихідного відношення R, якщо . Це симетричне відношення .
Відношення називається асиметричною частиною вихідного відношення R, якщо . Можна легко показати, що , тобто
.
Відмітимо, що це означає, що та . в загальному випадку асиметричне відношення.
Транзитивність. Відношення R буде транзитивним, якщо кожний направлений шлях довжиною 2 в його графі замикається дугою, тобто . Можна легко показати, що в графі транзитивного відношення дугою замикається направлений шлях будь-якої довжини, тобто
.
Для транзитивного відношення виконується
,
тобто нижній переріз кожного елементу множини є максимальним за включенням серед нижніх перерізів елементів, яких він містить. Через операцію включення властивість транзитивності можна записати як . Предикат транзитивності – це .
Лема 1.2. Для того, щоб R було транзитивним відношенням (щоб виконувалось ) необхідно і достатньо справедливості .
Доведення. ⇒ Доведемо за індукцією включення .
База: n = 2. виконується за .
Припущення: виконується для деякого .
Перехід: , і включення доведено .
За означенням транзитивного замикання
,
тобто . Але зворотне включення також тривіально виконується, тобто і необхідність доведена.
⇐ З означення транзитивного замикання очевидно . Оскільки , то , тобто – достатність доведена.
Доведено.
Від’ємна транзитивність. Відношення R називається від’ємно транзитивним, якщо транзитивним є його доповнення , тобто якщо . Для від’ємної транзитивності введемо предикат .
Лема 1.3.Для необхідно і достатньо справедливості твердження
.
Доведення. ⇒ Нехай , тобто при виконується та . Але з . Отримали протиріччя, яке доводить необхідність.
⇐ Нехай , тобто при та виконується . Але, поклавши в , маємо . Кожний з цих варіантів протирічить вихідному припущенню, і таким чином достатність твердження для від’ємної транзитивності також доведена.
Доведено.
Зв’язність. Відношення R називається зв’язним, якщо виконується . Предикат, введений для властивості зв’язності, позначається . Інша назва цієї властивості – лінійність. Зрозуміло, що зв’язне відношення обов’язково має бути рефлексивним. Граф зв’язного відношення містить єдину компоненту зв’язності та петлі у кожній вершині.
Слабка зв’язність. Будемо називати бінарне відношення R слабкозв’язним (відповідний предикат - ), якщо . Граф такого відношення, подібно до зв’язного, містить єдину компоненту зв’язності. Слабкозв’язне відношення не обов’язково має бути рефлексивним, тобто його граф може мати вершини, у яких відсутні петлі.
Не будь-який зв’язний граф відповідає слабкозв’язному відношенню, прикладом чому може слугувати дерево.
Теорема 1.1 (про взаємозв’язок властивостей бінарних відношень).
Мають місце наступні залежності між властивостями деякого бінарного відношення :
1) ; 2) ; 3) ;
4) ; 5) ; 6) .
Доведення.
1) Нехай , тоді . Припустимо, що , тобто , тоді
2) Нехай . Якщо при цьому , то , тобто граф відношення R містить цикл довжини 2. Якщо ж виконується лише коли , то граф відношення містить петлю. Обидва ці випадки протирічать .
3) Нехай для деяких . За для виконується . За , тобто можливий лише випадок . Отримали , звідки .
4) Нехай , але всупереч для деяких . Через те, що , та . Тобто , , що протирічить .
5) Нехай , але , тобто . За , що неможливо через .
6) Нехай знову , але всупереч
,
тоді за , чого не може бути згідно з .
Доведено.
Для теореми 1.1 можна навести ряд наслідків, наприклад:
· ;
· .
Відомості про взаємозв’язок властивостей бінарних відношень зручно представляти в табличному вигляді, рядок якої відповідає одному такому твердженню, стовпчик – окремій властивості. У комірці таблиці ставляться символи: ×, якщо антецедент твердження вимагає виконання відповідної властивості, та , який відмічає консеквент твердження. Викладені вище відомості зведені у табл. 1.1.
Таблиця 1.1. –Відомості про взаємозв’язок властивостей бінарних відношень | ||||||
№ | ||||||
⇒ | × | |||||
⇒ | × | |||||
× | ⇒ | × | ||||
⇒ | × | × | ||||
× | ⇒ | × | ||||
× | × | ⇒ | ||||
Н1 | × | × | ⇒ | × | ||
Н2 | ⇒ | × | × |
Розглянемо питання про інваріантність деяких властивостей бінарних відношень відносно операцій над ними. Наведемо відповідну теорему.
Теорема 1.2(про інваріантність властивостей відношень відносно операцій між ними).
Для заданих бінарних відношень , та будь-якого справедливі наступні твердження:
1) якщо , то , , , , ;
2) якщо , то , , ;
3) якщо , то , , , ;
4) якщо , то , ;
5) якщо , то та ;
6) якщо , то , , .
Доведення.
1) , . З властивостей включення множин
,
.
З тривіальним чином випливає . Доведемо . З означення композиції відношень . В якості z також можна взяти елемент x. Тепер, беручи до уваги те, що , вже доведене , та поклавши маємо
.
2) Оскільки , то за властивістю операції включення та . Далі, з випливає . За лемою 1.1 отримаємо
.
3) , . Тоді за
,
.
Подібним чином з інволютивності обернення . З
.
За індукцією . Знову використавши отримаємо
.
4) Відомо, що . . За лемою 1.1 маємо . Також тобто
.
Тепер нехай для деяких . Це зокрема означає, що . Оскільки , має місце
.
Візьмемо , використавши правило де Моргана отримаємо
.
Звідси .
5) , . Тоді
,
отже Подібним чином
,
і .
6) Нехай справедливі співвідношення та для деяких . Тоді також вірні , , , . За отримаємо , ідоведено. Якщо справджується та для деяких , то за визначенням оберненого відношення маємо та . За отримаємо що доводить . Далі, за лемою 1.2. Тоді , звідки .
Доведено.