1.3.5. Відношення еквівалентності

Означення 1.3.11. Бінарне відношення R називають відношенням еквівалентності, коли воно рефлексивне, симетричне і транзитивне.

Отже, R є відношенням еквівалентності, якщо:

1. ;

2. ;

3. .

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

Наприклад, відношення є відношенням еквівалентності.

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

Важливу роль відіграє в математиці відношення “мають однакову остачу при діленні на k” або “конгруентні за модулем k”, яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого kN. Відношення конгруентності за модулем k часто позначають a  b (mod k). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k=5, тобто 17  22(mod 5), 1221  6 (mod 5), 42  57 (mod 5).

Нехай – відношення еквівалентності і .

Означення 1.3.12. Переріз відношення за елементом називають класом еквівалентності за відношенням і позначають або .

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

Наприклад, якщо – відношення паралельності у площині , а – деяка фіксована пряма у цій площині, то клас еквівалентності містить усі прямі площини , паралельні прямій .

Теорема 1.3.1. Будь-які два класи еквівалентності за відношенням або не мають спільних елементів, або збігаються.

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

Означення 1.3.13. Множину всіх класів еквівалентності за відношенням називають фактор-множиною множини за відношенням : або , де – сукупність таких елементів множини , яким відповідають різні класи еквівалентності.

Наприклад, якщо – сукупність всіх студентів певної групи, які отримали за іспит оцінку , а – відношення еквівалентності, що визначається умовою тоді і тільки тоді, коли і , то . Фактор-множина для відношення “конгруентні за модулем 3” на множині N натуральних чисел складається з трьох класів { 3k | kN }, { 3k-1 | kN } і { 3k-2 | kN}.

Потужність фактор-множини |А/R| називають індексом розбиття або індексом відношення еквівалентності R.

Нехай R відношення еквівалентності на множині А. Відображення множини А на фактор-множину А/R, яке кожному елементу aА ставить у відповідність клас еквівалентності , називають канонічним або природним відображенням множини А на фактор-множину А/R.

1.3.6. Відношення порядку

Означення 1.3.14. Бінарне відношення R називають відношенням строгого порядку, коли воно антисиметричне і транзитивне. Позначають: або .

Отже R – відношення строгого порядку, якщо:

1. ;

2. .

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

Означення 1.3.15. Якщо відношення порядку є рефлексивним (), то його називають відношенням часткового (нестрогого) або квазіпорядку. Позначають: або .

Наприклад, у числових множинах N, Q, R встановлено відношення строгого () і нестрогого () порядку.

Множину M, на якій задано відношення порядку, називають впорядкованою, а елементи a,bM – порівнюваними за відношенням R, якщо виконується або . Запис означає, що у множині відношення порядку .

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

Очевидно, відношення рівності є відношенням часткового порядку на будь-якій множині M, цей порядок називають тривіальним.

Теорема 1.3.3. Якщо – відношення строгого (нестрогого) порядку, то обернене відношення – теж відношення строгого (нестрогого) порядку.

Нехай M частково впорядкована множина і A деяка непорожня підмножина множини M.

Означення 1.3.16. Верхньою гранню підмножини AM в множині M називається елемент bM такий, що ab всіх aA. Елемент b називається найбільшим елементом множини M, якщо b – верхня грань множини M. Відповідно, елемент c частково впорядкованої множини M називається нижньою гранню підмножини AM, якщо ca для будь-якого aA. Елемент c – найменший в множині M, якщо c – нижня грань самої множини M.

Означення 1.3.17. Елемент xM називається максимальним в множині M, якщо не існує елемента aM такого, що x<a. Відповідно, елемент nM називається мінімальним у множині M, якщо не існує елемента aM такого, що a<n.

У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.