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

Слово «порядок» часто застосовують у найрізноманітніших питаннях. Офіцер дає команду: «По порядку номерів розрахуйся», арифметичні дії виконуються в певному порядку, спортсмени стають по зростанню, всі провідні шахісти розташовуються в певному порядку за так званими коефіцієнтами Ело (американський професор, який розробив систему коефіцієнтів, що дозволяє враховувати всі успіхи та невдачі гравців), після першості всі футбольні команди розташовуються в певному порядку і т. д. Існує порядок виконання операцій при виготовленні деталі, порядок слів у реченні (спробуйте зрозуміти, що означає пропозиція «на він старого посадив осла не»!).

Маючи в своєму розпорядженні елементи деякої множини один за одним, ми тим самим упорядковуємо їх або встановлюємо між ними деяке відношення по-рядку.Найпростішим прикладом є природний порядок натуральних чисел. Його природність полягає в тому, що для будь-яких двох натуральних чисел ми знаємо, яке з них слідує за іншим або яке з них більше іншого, тому ми можемо розташувати натуральні числа в послідовності так, що більше буде розташовано, наприклад, правіше меншого: 1, 2, 3, ... . Зрозуміло, послідовність елементів можна виписувати в будь-якому напрямку, а не тільки зліва направо. Саме поняття натуральних чисел містить у собі ідею впорядкованості. Встановлюючи деяке відносне розташування елементів будь-якої множини, ми тим самим задаємо на ньому деяке бінарне відношення порядку, яке в кожному конкретному випадку може мати свою назву, наприклад, "бути менше", "бути старшими", "утримуватися в ", " слідувати за " і т. д. Символічні позначення порядку також можуть бути різноманітними, наприклад, І, і т. д.

Головною відмітною ознакою відношення порядку є наявність у нього транзитивності. Так, якщо ми маємо справу з послідовністю якихось об'єктів x 1, х 2, ..., х n,... , упорядкованих, наприклад, по відношенню , то з того, що виконується х 1х 2... х п..., повинно слідувати, що для будь-якої пари х i , х jелементів цієї послідовності також виконується x ix j:

Для пари елементів x ijу графі відносини ми проводимо стрілку від вершини x iдо вершини x j, тобто від меншого елемента до більшого.

Граф відносини порядку можна спростити, якщо скористатися методом так званих діаграм Хассе.Діаграма Хассе будується таким чином. Менші по порядку елементи мають у своєму розпорядженні нижче, а великі - вище. Оскільки одного такого правила недостатньо для зображення, проводять лінії, що показують, який із двох елементів більше, а який менше іншого. При цьому достатньо намалювати лише лінії для наступних один за одним елементів. Приклади діаграм Хассе показані малюнку:

У діаграмі Хасс можна не вказувати стрілки. Діаграму Хассе можна повертати у площині, але не довільно. При поворотах необхідно зберігати відносне положення (вище – нижче) вершин діаграми:

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

Безліч, у якому визначено відношення суворого порядку, називають упорядкованим.Наприклад, безліч натуральних чисел упорядковано ставленням «менше». Але це ж безліч упорядковано й іншим ставленням – «ділиться на» та «більше».

Граф відношення «менше» у безлічі натуральних чисел можна зобразити у вигляді променя:

Ставлення Rв Xназивається ставленням нестро-гого (часткового) порядку, якщо воно транзитивне та антисиметричне. Будь-яке ставлення нестрогого порядку рефлексивне.

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

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

Відношення включення між підмножинами деякої множини також є частковим порядком. Очевидно, що не будь-які два підмножини можна порівняти з цього відношення. Нижче на малюнку показаний частковий порядок за включенням на множині всіх підмножин множини (1,2,3). Стрілки на графі, які мають бути спрямовані нагору, не показані.

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

Елементи хі участково впорядкованої множини називаються порівнянними,якщо хуабо ух.В іншому випадку вони не можна порівняти.

Упорядкована множина, в якій будь-які два елементи можна порівняти, називається лінійно упорядкованим, А порядок - лінійним порядком. Лінійний порядок ще називають досконалим порядком.

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

Об'єкти різної природи можуть бути впорядковані ієрархічно.Ось кілька прикладів.

Приклад 1. Частини книги впорядковані так, що книга містить розділи, розділи містять розділи, а розділи складаються з підрозділів.

Приклад 2.Папки у файловій системі комп'ютера вкладені один в одного, утворюючи структуру, що гілкується.

Приклад 3.Ставлення батьки - діти може бути зображено у вигляді так званого генеалогічного дерева,яке показує, хто чиїм предком (чи сином) є.

Нехай на безлічі Азаданий частковий порядок. Елемент хназивається максимальним (мінімальним)елементом множини А, якщо з того, що ху(ух),слідує рівність х= у.Інакше кажучи, елемент хє максимальним (мінімальним), якщо для будь-якого елемента учи не так, що ху(ух), або виконується х=у.Таким чином, максимальний (мінімальний) елемент більше (менше) відмінних від нього елементів, з якими він знаходиться у відношенні .

Елемент хназивається найбільшим (найменшим),якщо для будь-кого уÎ Авиконується у< х (х< у).

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

У кінцевому частково впорядкованому множині завжди існують мінімальний і максимальний елементи.

Упорядковане безліч, у якого є найбільший і найменший елементи, називається обмеженим.На малюнку показаний приклад нескінченної обмеженої множини. Зрозуміло, зобразити безліч на кінцевій сторінці не можна, але можна показати принцип його побудови. Тут петлі біля вершин не показані спрощення малюнка. З тієї ж причини не показані дуги, що забезпечують відображення транзитивності властивості. Інакше кажучи, малюнку представлена ​​діаграма Хассе відносини порядку.

Нескінченні множини можуть не мати максимальних, або мінімальних, або тих та інших елементів. Наприклад, множина натуральних чисел (1,2, 3, ...) має найменший елемент 1, але не має максимальних. Безліч всіх дійсних чисел з природним порядком не має ні найменшого, ні найбільшого елемента. Однак його підмножина, що складається з усіх чисел х< 5 має найбільший елемент (число 5), але не має найменшого.

План лекції №14 Класифікація бінарних відносин

1. Класифікація антисиметричних відносин
2. Класифікація рефлексивних відносин
2.1. Відносини квазіпорядку
2.2. Відносини нестрогого часткового порядку
2.3. Відносини нестрого впорядкування
2.4. Несуворий якісний порядок
2.5. Нестрогий слабкий порядок
2.6. Нестрогий порядок
3. Подвійність відносин строгого та не суворого порядку
4. Огляд властивостей різних видів відносин

Класифікація антисиметричних відносин

Структура графів ациклічних відносин

Структура графів відносин якісного порядку

Структура графів відносин слабкого ладу

Відносини суворого порядку

Суворим порядком (суворою перевагою, сильним порядком, строгим лінійним порядком) називається антирефлексивне, транзитивне, слабозв'язне бінарне відношення (12).

Суворий порядок є окремим випадком слабкого порядку (суворої часткової переваги) з додатковою умовою слабозв'язності.

Приклад: Відношення "суворо менше" на множині цілих чисел.

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

Відносини квазіпорядку

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

Квазіпорядком (нестрогим частковим перевагою) називається рефлексивне та транзитивне бінарне відношення (3).

Приклад: "Бути братом" (Іван-Петро, ​​Андрій-Анна)

Властивості квазіпорядків

1. Перетин квазіпорядків залишається квазіпорядком.
2. Симетрична частина квазіпорядку має властивості рефлексивності, симетричності та транзитивності і тому є відношенням еквівалентності. R с = R / R інв
3. За допомогою цього перетину можна виділити групи еквівалентних між собою варіантів, тоді між виділеними групами може бути встановлене відношення нестрогого часткового порядку, породжене вихідним ставленням.
4. Асиметрична частина квазіпорядку є транзитивним та антирефлексивним ставленням = якісний порядок.

Відносини нестрогого часткового порядку

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

Нестрогий частковий порядок є антисиметричним квазіпорядком

Приклад: відношення "бути частиною", визначене для множин (та їх підмножини)

Властивості нестрогих часткових порядків

1. Перетин нестрогих часткових порядків залишається нестрогим частковим порядком.
2. Симетрична частина нестрогого часткового порядку є діагоналлю.
3. Асиметрична частина нестрогого часткового порядку є (суворим) якісним порядком.
4. Теоретично інтелектуальних систем важливу роль відіграють частково впорядковані множини – домени разом із певними ними відносинами нестрогого часткового порядку.
5. Частково впорядковані множини з додатковою властивістю існування у кожної пари елементів верхньої та нижньої граней називаються ґратами. Окремим випадком решіток є булеві алгебри.

Відносини не суворого впорядкування

Нестрогим упорядкуванням називається рефлексивне ставлення, що має властивість слабозв'язності (5).

Нестрого упорядкування можна визначити також як повнозв'язкове ставлення.

Ставлення суворого впорядкування можна як результат об'єднання деяких відносин толерантності і домінування.

Властивості відносин нестрогого часткового впорядкування

1. Перетин та об'єднання повнозв'язкових відносин залишається повнозв'язковим ставленням.
2. Симетрична частина нестрогого часткового впорядкування є толерантністю.
3. Асиметрична частина нестрогого часткового упорядкування є домінуванням.
4. Для повнозв'язкових відносин необхідною умовою транзитивності є негатранзитивність відносини.
5. Для повнозв'язкових відносин властивість транзитивності є достатньою умовою негатранзитивності відносини.

Відносини нестрого якісного порядку

Бінарне відношення R називається нестрогим якісним порядком, якщо воно негатразітивно і повнозв'язкове (6).

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

Ставлення нестрого якісного порядку можна як результат об'єднання деяких відносин толерантності і якісного порядку.

Властивості відносин нестрого якісного порядку

1. Симетрична частина нестрого якісного порядку є толерантністю. НТ?
2. Асиметрична частина нестрого якісного порядку транзитивна, тому є ставленням якісного порядку.
3. Отже, ставлення нестрогого якісного порядку можна як результат об'єднання відносин толерантності і якісного порядку, породжених вихідним ставленням.
4. Подвійне відношення має властивості асиметричності і транзитивності тому є ставленням якісного порядку.

Відносини не суворого слабкого порядку

Нестрогим слабким порядком називається повнозв'язне транзитивне та негатранзитивне відношення (7).

Нестрогим слабким порядком називається повнозв'язкове транзитивне ставлення.

Нестрогим слабким порядком називається транзитивне суворе впорядкування.

Властивості відносин не суворого слабкого порядку

1. Симетрична частина суворого слабкого порядку є еквівалентністю.
2. Асиметрична частина R ас нестрогого слабкого порядку транзитивна, тому є ставленням якісного порядку.
3. Отже, ставлення нестрогого слабкого порядку можна як результат об'єднання відносин еквівалентності і слабкого порядку, породжених вихідним ставленням.
4. Нестрогий слабкий порядок можна у вигляді безлічі частково упорядкованих верств, кожен із яких є класом еквівалентності.

Відносини не суворого (лінійного) порядку

Нестрогим порядком (нестрогим лінійним порядком) називається антисиметричне, транзитивне, повнозв'язкове бінарне ставлення (8).

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

Нестрогим порядком називається антисиметричне несуворе впорядкування.

Властивості відносин нестрогого лінійного порядку

1. Симетрична частина нестрогого порядку є діагоналлю.
2. Асиметрична частина R ас нестрогого порядку транзитивна і слабозв'язкова, тому є ставленням до строгого порядку.
3. Подвійне відношення має властивості асиметричності, негатранзитивності і слабозв'язності тому є ставленням суворого порядку. Крім того, воно збігається з R ас.
4. Отже, ставлення нестрогого порядку можна як результат об'єднання діагоналі і строгого порядку, породжених вихідним ставленням.

Подвійність відносин суворого та не суворого порядку

Огляд властивостей різних видів відносин

Слово «порядок» часто застосовують у різних питаннях. Офіцер дає команду: «По порядку номерів розрахуйся», арифметичні дії виконуються у порядку, спортсмени стають зростанням, існує порядок виконання операцій під час виготовлення деталі, порядок слів у пропозиції.

Що ж спільного у всіх випадках, коли йдеться про порядок? У тому, що в слово «порядок» вкладається такий зміст: воно означає, який елемент тієї чи іншої множини за яким слідує (або який елемент передує).

Відношення « хслід за у» транзитивно: якщо « хслід за у» та « услід за z», то « xслід за z». Крім того, це відношення має бути антисиметричним: для двох різних хі у, якщо хслід за у, то уне слід за х.

Визначення.Ставлення Rна безлічі Xназивають ставленням суворого порядку, якщо воно транзитивне та антисиметричне.

З'ясуємо особливості графа та графіка відносин строгого порядку.

Розглянемо приклад. На безлічі X= (5, 7, 10, 15, 12) ставлення R: « х < у». Задамо це відношення переліком пар
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Побудуємо його граф. Ми бачимо, що граф цього відношення не має петель. На графі немає подвійних стрілок. Якщо з хйде стрілка в у, а з у– у z, то з хйде стрілка в z(Рис. 8).

Побудований граф дозволяє розмістити елементи множини Xу такому порядку:

{5, 7, 10, 12, 15}.

На рис.6 (§ 6 цього розділу) графи VII, VIII – це графи відносин строгого порядку.

Відношення не суворого порядку

Відношенню «менше» у багатьох дійсних чисел протилежне відношення «не менше». Воно вже не є ставленням до суворого порядку. Справа в тому, що х = у, виконуються відносини х ³ уі у ³ х, тобто. відношення «не менше» має рефлексивність.

Визначення.Ставлення Rна безлічі Xназивають ставленням не суворого порядкуякщо воно рефлексивне, антисиметричне і транзитивне.

Такі відносини є об'єднаннями відносини суворого порядку із ставленням тотожності.

Розглянемо ставлення «не більше» (£) для множини

X= (5, 7, 10, 15, 12). Побудуємо його граф (рис. 9).

Граф відносини нестрогого порядку, на відміну графа відносини строгого порядку, у кожному вершині має петлі.

На рис. 6 (§ 6 цього розділу) графи V, VI – це графи відносин нестрогого порядку.

Упорядковані множини

Безліч може виявитися упорядкованим (говорять також повністю упорядкованим) деяким ставленням порядку, інше ж неупорядкованим чи частково впорядкованим таким ставленням.

Визначення.Безліч Xназивають упорядкованимдеяким ставленням порядку R, якщо для будь-яких двох елементів х, уз Х:

(х, у) Î Rабо ( у, х) Î R.

Якщо R- Відношення суворого порядку, то безліч Хупорядковано цим ставленням за умови: якщо х, убудь-які два нерівні елементи множини Х, то ( х, у) Î Rабо ( у, х) Î R, або будь-які два елементи х, убезлічі Хрівні.

Зі шкільного курсу математики відомо, що числові множини N , Z , Q , R упорядковані ставленням «менше» (<).

Безліч підмножин певної множини не впорядковане введенням відношення включення (Í), або суворого включення (Ì) у зазначеному вище сенсі, т.к. існують підмножини жодне з яких не включається до іншого. У цьому випадку кажуть, що ця множина частково впорядкована ставленням Í (або Ì).

Розглянемо безліч X= (1, 2, 3, 4, 5, 6) і в ньому два відносини "менше" і "ділиться на". Легко перевірити, що ці відносини є відносинами порядку. Граф відношення «менше» можна зобразити у вигляді променя.

Граф відносини «ділиться на» можна зобразити лише з площині.

Крім того, на графі другого відношення є вершини, які не з'єднані стрілкою. Наприклад, немає стрілки, що з'єднує числа 4 та 5 (рис. 10).

Перше ставлення « х < у»називається лінійним. Взагалі, якщо відношення порядку R(суворого та не суворого) на безлічі Xмає властивість: для будь-яких х, уÎ Хабо хRy, або yRx, то його називають ставленням лінійного порядку, а безліч X- Лінійно впорядкованим безліччю.

Якщо безліч Xзвичайно, і складається з nелементів, то лінійне впорядкування Хзводиться до нумерації його елементів числами 1,2,3, ..., n.

Лінійно впорядковані множини мають ряд властивостей:

1°. Нехай а, в, з- Елементи множини X, упорядкованого ставленням R. Якщо відомо, що aRві вRс, то кажуть, що елемент влежить між елементами аі з.

2 °. Безліч X, лінійно упорядковане ставленням R, називається дискретним, якщо між будь-якими двома його елементами лежить лише кінцева множина елементів цієї множини.

3 °. Лінійно впорядкована множина називається щільною, якщо для будь-яких двох різних елементів цієї множини існує елемент множини, що лежить між ними.

Нехай R - бінарне відношення на множині А.

ВИЗНАЧЕННЯ. Бінарне відношення R на множині А називається ставленням порядку на А або порядком на А, якщо воно є транзитивним і антисиметричним.

ВИЗНАЧЕННЯ. Відношення порядку R на множині А називається нестрогим, якщо воно рефлексивне на А, тобто для кожного з А.

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

ВИЗНАЧЕННЯ. Бінарне відношення R на множині А називається строгим порядком на А, якщо воно транзитивно та антирефлексивно на А.

приклади. 1. Нехай - безліч всіх підмножин множини М. Відношення включення на множині є відношення нестрогого порядку.

2. Відносини на безлічі дійсних чисел є відповідно ставленням суворого та не суворого порядку.

3. Відношення ділимості в багатьох натуральних чисел є відношення нестрогого порядку.

ВИЗНАЧЕННЯ. Бінарне відношення R на множині А називається ставленням передпорядку або передпорядком на А, якщо воно рефлексивно і транзитивно.

приклади. 1. Відношення ділимості в багатьох цілих чисел не є порядком. Однак воно рефлексивне і транзитивне, отже, є передпорядком.

2. Відношення логічного прямування є передпорядком на безлічі формул логіки висловлювань.

Лінійний порядок. Важливим окремим випадком порядку є лінійний порядок.

ВИЗНАЧЕННЯ. Відношення порядку на множині називається ставленням лінійного порядку або лінійним порядком на , якщо воно пов'язане на , тобто для будь-яких х, у з А

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

приклади. 1. Відношення «менше» на множині дійсних чисел є відношення лінійного порядку.

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