Класифікація бінарних відношень

Розглянуті властивості та їхній взаємозв’язок дозволяють виділити та досліджувати окремі класи відношень, що є корисними при моделюванні переваг.

Еквівалентність. Рефлексивне, симетричне та транзитивне бінарне відношення R називається відношенням еквівалентності. Це записується як .

Теорема 1.3. Якщо R – відношення еквівалентності (предикат істинний), то виконується .

Доведення. Нехай для деяких . Тоді , і за означенням нижнього перерізу. Оскільки , має місце . За , та знову за .

Нехай , тобто має місце . За , тобто .

Доведемо зворотне включення. Нехай . За , і . Остаточно .

Доведено.

Сімейство непорожніх підмножин множини Ω називається її розбиттям, якщо

1) ;

2) .

Самі підмножини називаються класами розбиття. За домовленістю для подальшого викладення будемо вважати, що .

Примітка 1.1 (до теореми 1.3). Для відношення еквівалентності сімейство його нижніх перерізів для кожного елементу множини є суть її розбиттям, тобто виконується .

Щодо існування розбиття для відношення еквівалентності має місце і зворотне твердження.

Теорема 1.4. Нехай на множині задано деяке розбиття . Введемо на відношення R виду

.
Тоді .

Доведення. . Перевіряємо кожну із властивостей R.

Нехай , тоді за означенням розбиття , тобто , звідки .

Нехай , тобто для деякого . Але порядок розгляду елементів множини не важливий, отже . Таким чином , а значить .

Нарешті, нехай , тобто та для деяких . Можливий лише один з двох випадків: або , оскільки – розбиття . Але перший випадок неможливий, оскільки. Отже , . Отримали , та істинність доведено.

Доведено.

Примітка 1.2 (до теореми 1.4). Множини називаються класами еквівалентності відношення R. Сімейство усіх класів еквівалентності відношення R називають фактор-множиною по еквівалентності R, та позначають . Вона визначається наступним чином

.

Із відношенням еквівалентності тісно пов’язане поняття факторизації.

Нехай задане деяке відношення . Нехай до того ж на задане деяке відношення еквівалентності (для цього достатньо задати деяке розбиття множини ). Побудуємо на фактор-множині відношення наступним чином:

.
Таким чином, пара класів еквівалентності знаходиться у відношенні тоді і тільки тоді, коли знайдуться такі представники цих класів, які знаходяться у відношенні R.

Операцію отримання називають факторизацією відношення R за еквівалентністю , а отримане відношення – фактор-відношенням. Подібним чином можна говорити про те, що відношення еквівалентності визначає факторизацію множини як операцію отримання по відповідної фактор-множини .

Розглянемо приклад факторизації. Нехай , і на цій множині задано відношення R, граф якого зображено на рис. 1.2. Також на задано розбиття

.

Рис. 1.2 – Графи відношення до прикладу здійснення операції факторизації та відповідного фактор-відношення

На рис. 1.2 класи еквівалентності відповідного відношення еквівалентності обведено пунктирною лінією. Також на цьому рисунку наведений граф фактор-відношення. При побудові фактор-відношення слід звернути уваги на можливі петлі, що виникають, коли у вихідному відношенні R існують пари, компоненти яких належать одному класу еквівалентності.

Тепер розглянемо питання про перехід спеціальних властивостей відношень на фактор-відношення. Будемо казати, що властивість зберігається при факторизації, якщо .

Теорема 1.5 (про інваріантність властивостей відношень відносно операції факторизації).

Для заданого бінарного відношення та відношення еквівалентності , виконується:

1) ; 2) ;

3) ; 4) ;

5) .

Доведення.

1) Нехай – клас еквівалентності відношення . Тоді . Оскільки , , і за визначенням фактор-відношення . Розглядаючи усі приходимо до висновку, що .

2) Нехай – класи еквівалентності відношення , та , . Якщо , то . , тобто справджується , звідки , і .

3) Нехай . Тоді , що протирічить .

4) Візьмемо такі класи еквівалентності відношення , що та . Тоді для деяких елементів , , виконується , . Оскільки y та знаходяться в одному класі еквівалентності, . Враховуючи те, що , маємо Отже , за отримуємо , що за визначенням фактор-відношення означає . Таким чином доведено .

5) ⇒ Нехай виконується , тобто . Нехай Це означає, що існує послідовність елементів з множини така, що . З означень класів еквівалентності та фактор-відношення це означає, що

.

З того, що слідує , а з – . За справедливе , тобто

.

Але тоді , тобто , і необхідність доведено.

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

.

Але , тобто , та , тобто . Разом із цим, , тобто в цьому разі обов’язково має виконуватись . Ми показали, що , з чого випливає , і достатність також доведено.

Доведено.

Примітка 1.3 (до теореми 1.5). В пункті 4 умова є суттєвою. В загальному випадку необхідною та достатньою умовою транзитивності фактор-відношення за довільною еквівалентністю буде умова 5. Умова 4 є частковим випадком умови 5. Так, зокрема якщо , та , маємо

.

Оскільки , отримаємо , тобто .

Зазначимо, що якщо відповідно відношенню еквівалентності , що задає розбиття на , визначити функціональне відображення наступним чином:

,

то очевидно виконується , а тому виконується також . Як буде видно далі, – рангова шкала еквівалентності R.

Строгий порядок. Антирефлексивне та транзитивне відношення називається відношенням строгого порядку. Інакше це означення можна записати як . Очевидно, що через залежність властивостей бінарних відношень (теорема 1.1) (граф строгого порядку ациклічний) та . Також слід зазначити, що оскільки , строгий порядок не може бути зв’язним. Для строгого порядку можлива лише слабка зв’язність.

Елемент такий, що виконується називається найбільшим елементом на множині по відношенню R. Має місце наступне твердження.

Лема 1.4. Нехай задано , і , та . Тоді існує єдиний найбільший по R елемент на .

Доведення. Виберемо деякий . Якщо цей елемент найбільший, то лема доведена. Інакше оскільки , то . Для повторимо наведені міркування.

Нехай описаним вище чином вибрано елементів, для яких . Маємо , . Через те, що скінченна, на деякому кроці t . Покажемо, що буде єдиним найбільшим елементом. Нехай . Тоді , що протирічить . Таким чином був знайдений єдиний на найбільший .

Доведено.

Теорема 1.6. Нехай задано , і , та . Тоді на можна вибрати таке функціональне відображення , що .

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

.

Якщо тепер покласти , U буде шуканим відображенням, оскільки за .

Доведено.

Примітка 1.4 (до теореми 1.6). Відображення U для строгого порядку не є єдиним. Нехай та – два різних функціональних відображення, що задовольняють умові теореми 1.6 для одного і того ж самого відношення строгого порядку. Тоді можна показати, що існує – монотонно зростаюча числова скалярна функція така, що , де позначає композицію функцій.

Примітка 1.5 (до теореми 1.6). Теорема залишається справедливою і у випадку, коли – нескінченна злічена множина. Але результат вже не має місця, коли – континуум. Покажемо це за допомогою контр-прикладу.

Нехай . З теорії множин відомо, що декартовий квадрат нескінченної множини рівнопотужний самій цій множині, зокрема має місце . Також очевидно, що , і , звідки. Задамо наступне відношення лексикографічного порядку :

.

Легко показати, що . Тепер нехай для R існує функціональне відображення U, що задовольняє умові теореми 1.6, тобто

.

Між двома різними дійсними числами та завжди можна обрати раціональне число таке, що . Виберемо для деяких таких, що

,

два , і

.

Отримали. Таким чином – бієкція між та , що неможливо, оскільки ці множини не рівнопотужні.

Примітка 1.6 (до теореми 1.6). Вимога слабкої зв’язності в умові теореми є суттєвою. Теорема не вірна для незв’язного строгого порядку.

Нестрогий порядок. Рефлексивне, транзитивне та антисиметричне відношення R називається відношенням нестрогого порядку. За допомогою предикатів це записується як . Через рефлексивність це відношення може бути лише зв'язним та не може бути слабко зв'язним. «Нестрогість» цього відношення виражає наступне твердження.

Лема 1.5. Нехай та . Тоді на для .

Доведення. можна отримати з та інваріантності рефлексивності відносно операції об’єднання (теорема 1.2).

Далі, нехай для деяких . Це означає, що можливі наступні випадки: 1) ; 2) ; 3) ; 4) . Ці випадки взаємовиключні, оскільки , бо . У випадку 1 , і . У випадку 2 , і . Якщо справджується випадок 3, то , та . Нарешті, у випадку 4 відповідно до , і також , що доводить .

Тепер, , це означає, що . Оскільки та , знову маємо наступні взаємовиключні ситуації: 1) ; 2) ; 3) ; 4) . Варіант 2 неможливий, оскільки , але тоді . Варіант 3 неможливий з аналогічних причин. Неможливий також і варіант 4 – через . Варіант 1 виконується тільки якщо . Ми довели, що , тобто що .

Доведено.

Справедливе в деякому розумінні зворотне твердження, яке дозволяє виділяти строгий порядок із нестрогого.

Лема 1.6. Нехай та . Тоді та на .

Доведення. Оскільки , то . З , , і . Отже .

За означенням , а за теоремою 1.1 . , тобто

.

Оскільки , то в тому числі і при , а значить для таких елементів. Для , а для , тобто такі випадки неможливі, і доведено. Нарешті .

Доведено.

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

Лема 1.7. Нехай задано , і , та . Тоді існує єдиний найбільший по R елемент на .

Без доведення.

Теорема 1.7. Нехай задано , і , та – скінченна або злічена. Тоді на можна вибрати таке функціональне відображення , що .

Без доведення.

Примітка 1.7 (до теореми 1.7). В якості U на скінченній подібно до випадку строгого порядку можна взяти , , .

Квазіпорядок. Рефлексивне та транзитивне відношення називається відношенням квазіпорядку. Через предикати це записується як Воно одночасно є узагальненням відношення еквівалентності та нестрогого порядку. Покажемо деякі властивості, які має квазіпорядок.

Лема 1.8. Нехай , та . Тоді .

Доведення. За означенням . Доведення випливає з теореми 1.2 про інваріантність відповідних властивостей відношення R відносно операцій із ним (розглядаються операції перетину та обернення), тобто та . Остаточно

.

Доведено.

Для квазіпорядку R класи еквівалентності називаються областями рівня.

Теорема 1.8. Нехай , та . Тоді .

Доведення. Нехай – розбиття (сімейство класів еквівалентності), яке відповідає еквівалентності . Розглянемо деякий клас еквівалентності з цього розбиття. , тоді за означенням фактор-відношення .

Тепер нехай для деяких класів еквівалентності виконується . Це означає, що для деяких представників , виконано , а для деяких та виконано . Оскільки , маємо , а тим більше (оскільки ). Отримали , та за . Для фактор-відношення це означає, що . Ми показали, що , тобто що .

Те, що означає, що для деяких . Припустимо, що одночасно виконується , тобто що . Оскільки , , а значить (оскільки ця пара належить перетину R із іншим відношенням). Відповідно до . Далі, , маємо , тобто , і . Ми показали, що , що означає .

Остаточно .

Доведено.

Має місце наступний наслідок цієї теореми.

Лема 1.9 (наслідок теореми 1.8). Нехай , та . Тоді .

Доведення. В силу теореми 1.8 достатньо показати, що . Розглянемо два довільні класи та довільні два їхні представники , . Оскільки , то , що за означенням фактор-відношення означає , тобто дійсно .

Доведено.

Слід не плутати поняття асиметричної частини та фактор-відношення по симетричній частині. На рис. 1.3 представлені: граф квазипорядку R, графи його симетричної та асиметричної частин, а також граф фактор-відношення . Останній отримується стягуванням на окремих компонент зв’язності в єдину вершину, що відповідатиме деякому класу еквівалентності , який містить усі вершини цієї компоненти зв’язності.

Рис. 1.3 – Графи відношень, пов’язаних із квазіпорядком . На діаграмі б пунктирні дуги відносяться до симетричної частини , суцільні – до асиметричної

Знову розглянемо питання про існування спеціального виду функціонального відображення на числову пряму для відношення R. Тепер візьмемо в якості R зв’язний квазіпорядок.

Теорема 1.9. Нехай , , та . Тоді на існує таке функціональне відображення , що .

Доведення. Оскільки (теорема 1.8), за теоремою 1.7 існує таке функціональне відображення , що . Покладемо . По представникам різних класів еквівалентності умова теореми для U виконується, оскільки вона виконується для . Розглянемо деякі . Для них , тобто і в цьому випадку умови теореми виконані, і ми отримали шукане відображення.

Доведено.

Примітка 1.8 (до теореми 1.9). Теорема справедлива також і для нескінченної зліченої .

Примітка 1.9 (до теореми 1.9). Як і зазвичай, вимога є суттєвою, і без неї теорема не має місця.

Слабке упорядкування. Асиметричне та від’ємно транзитивне відношення називається слабким упорядкуванням (впорядкуванням), або . Із взаємозв’язку властивостей бінарних відношень видно, що це частковий випадок строгого порядку, тобто .

Поставимо у відповідність слабкому впорядкуванню R відношення непорівнянності , що визначається як , або, що те ж саме, .

Введемо додаткове поняття. Нехай задані бінарні відношення та . Кажуть, що виконується узагальнена транзитивність відносно , або що є транзитивним відносно відношення , якщо має місце

.

Це позначається як . Зрозуміло, що в загальному випадку .

Для відношення непорівнянності , де , справедливе наступне твердження.

Лема 1.10. Нехай та . Тоді .

Доведення. Нехай . Оскільки за лемою 1.3 . Оскільки , то , тобто може виконуватись лише . Отже ми показали, що .

Тепер нехай . Знову відповідно до . Оскільки , то , тобто може виконуватись лише . Ми довели, що , отже остаточно .

Доведено.

Доведемо важливу теорему щодо зв’язного впорядкування, з якої його природа як частковий випадок строгого порядку стає більш зрозумілою.

Теорема 1.10. Нехай задано та . Тоді .

Доведення. ⇒ З означення одразу випливає . Оскільки , то , а значить , отже , а також (лема 1.1). За теоремою 1.2 має місце , тобто .

Припустимо, що для деяких , але всупереч . Тоді за означенням відношення непорівнянності. Оскільки , за лемою 1.3 . Підставляючи отримаємо , а роблячи підстановку отримаємо . Іншими словами, можливі наступні випадки: . Кожен з них протирічить за означенням , і необхідність доведено.

⇐ За теоремою 1.1 . Доведемо, що . Нехай навпаки для деяких , але . З означення , . Можливі наступні випадки: 1) ; 2) ; 3) ; 4) . Розглянемо кожний з цих випадків.

У випадку 1 через , що протирічить . У випадку 2 з маємо , що протирічить нашому припущенню . У випадку 3 за має виконуватись , що знову протирічить припущенню .

Розглянемо випадок 4. Оскільки за лемою 1.10 , то , що протирічить . Отже вихідне припущення невірне, тобто можливо лише , звідки отримаємо .

Остаточно , і таким чином достатність доведена.

Доведено.

Оскільки для слабкого впорядкування R , ми можемо виконати факторизацію R за відношенням непорівнянності. Результати викладемо у вигляді наступної теореми.

Теорема 1.11. Нехай , та . Тоді на .

Доведення.

Доведено.

Як і для усіх інших класів бінарних відношень розглянемо питання про існування спеціального виду функціонального відображення на числову пряму, але тепер R буде слабко зв’язним слабким упорядкуванням.

Теорема 1.12. Нехай , , та – скінченна або злічена. Тоді на існує таке функціональне відображення , що .

Доведення.

Доведено.

На цьому завершується огляд основних класів бінарних відношень. Зведемо в табл. 1.2 відомості про класи відповідно до властивостей, які повинні виконуватись для відношення, якщо воно належить до того чи іншого класу. Стовпцям таблиці відповідають окремі властивості відношень, а рядкам – класи. Відношень. Символом × у комірці таблиці відмічається та властивість, що присутня у означенні відповідного класу. Символом ⨂ натомість відмічається та властивість, що випливає з властивостей, помічених символом × для відповідного класу відношення.

Таблиця 1.2. –Відомості про класи бінарних відношень відповідно до властивостей, виконання яких вимагається
Клас
	×		×			×
		×		⨂		×		⨂
	×				×	×
	×					×
		⨂		×		⨂	×	⨂

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

Рис. 1.4 – Взаємозв’язок класів бінарних відношень

Дата добавления: 2013-12-14