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

4. Як можна було б згрупувати різні за змістом відношення? – навколо певних наборів властивостей. У математиці відношення між елементами однієї множини поділяють принаймні на три групи: 1) відношення еквівалентності; 2) відношення порядку; 3) функціональні відношення. Розглянемо перші дві групи.

Означення: будь-яке рефлексивне, симетричне та транзитивне відношення f, визначене у множині Х, називається відношенням еквівалентності.

Прикладами відношень еквівалентності є відношення подібності на множині трикутників, паралельності на множині площин, «бути однокурсником» на множині студентів тощо. Як визначити, чи є задане відношення відношенням еквівалентності? – перевірити наявність у нього властивостей, які повинні бути у відношення такого типу. Покажемо це на конкретному прикладі.

Вправа: з’ясувати, чи є відношенням еквівалентності відношення «проживати на одній вулиці», задане на множині людей.

1) оскільки кожна людина проживає на одній вулиці сама з собою, то це відношення рефлексивне;

2) якщо людина А проживає на одній вулиці з людиною В, то і людина В проживає на одній вулиці з людиною А, тобто із (АαВ)→(ВαА);

3) якщо людина А проживає на одній вулиці з людиною В, а людина В проживає на одній вулиці з людиною С, то і людина А проживає на одній вулиці з людиною С, тобто із ((АαВ)^(ВαС))→(АαC).

Отже, відношення α:«проживати на одній вулиці», задане на множині людей, є рефлексивним, симетричним і транзитивним, а тому відноситься до відношень типу еквівалентності.

Розглядаючи поняття розбиття множини на підмножини, що попарно не перетинаються, ми з’ясували, що відношення «бути однокурсником» на множині студентів, розбило множину всіх студентів на п’ять підмножин. З’ясуємо властивості цього відношення. Легко бачити, що воно має властивості рефлексивності, симетричності і транзитивності (Чому?), а тому є відношенням типу еквівалентності. Сказане дає підстави припустити, що між розбиттям множини на класи, що попарно не перетинаються, і відношеннями типу еквівалентності існує певний зв'язок. Сутність цього зв’язку розкривається такою теоремою.

Теорема: для того, щоб відношення α дозволяло розбити множину Х на класи, що попарно не перетинаються, необхідно і достатньо, щоб відношення α було відношенням еквівалентності.

Оскільки у формулюванні цієї теореми є слова необхідно і достатньо, то доведення теореми складається із двох частин: 1) із доведення необхідності; 2) із доведення достатності. Цю теорему приймемо без доведення.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням строгого порядку, якщо воно антирефлексивне, антисиметричне і транзитивне.

Прикладами відношень строгого порядку є: відношення «менше» у множині цілих чисел; відношення «бути старшим» на множині людей; відношення «бути вищим» на множині дерев тощо.

Означення: бінарне відношення α, визначене у множині Х, називається відношенням нестрогого порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

Прикладами відношень нестрогого порядку є: відношення «більше або дорівнює» у множині раціональних чисел; відношення подільності на множині натуральних чисел тощо.

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

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

Означення: якщо відношення α в множині Х є відношенням часткового порядку, то множину Х називають частково впорядкованою множиною.

Означення: якщо відношення α в множині Х є відношенням лінійного порядку, то множину Х називають лінійно впорядкованою множиною.

Лінійно впорядковані множини мають ряд властивостей. Нехай а,в,сєХ і множина Х лінійно впорядкована відношенням α. Якщо відомо, що аαв^вαс, то говорять, що елемент в лежить між елементами а і с.

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

Прикладом дискретних множин є множини натуральних і цілих чисел.

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

Прикладом щільних в собі множин є множина дійсних чисел.