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

Лекція 22. Відносини еквівалентності та порядку на множині

1. Відношення еквівалентності. Зв'язок відношення еквівалентності з розбиттям множини на класи.

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

3. Основні висновки

Розглянемо на безлічі дробів X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) відношення рівності. Це ставлення:

Рефлексивно, оскільки всяка дріб дорівнює сама собі;

Симетрично, тому що з того, що дріб m/nдорівнює дробу p/qслід, що дріб p/qдорівнює дробу m/n;

Транзитивно, тому що з того, що дріб m/nдорівнює дробу p/qі дріб p/qдорівнює дробу r/sслід, що дріб m/nдорівнює дробу r/s.

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

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

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

Чому в математиці виділили цей вид стосунків? Розглянемо ставлення рівності дробів, задане на множині X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) (Рис.106). Бачимо, що множина розбилася на три підмножини: (1/2, 2/4, 3/6), (1/3, 2/6), (1/4). Ці підмножини не перетинаються, які об'єднання збігається з безліччю Х,тобто. маємо розбиття множини Xна класи. Це не випадково.

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

Так, ми встановили, що відношенню рівності на множині дробів (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) відповідає розбиття цієї множини на класи еквівалентності, кожен з яких складається з рівних між собою дробів.

Правильне і зворотне твердження: якщо якесь відношення, задане на множині X, породжує розбиття цієї множини на класи, воно є ставленням еквівалентності.

Розглянемо, наприклад, на множині X =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) відношення «мати один і той же залишок при розподілі на 3». Воно породжує розбиття множини Xна класи: в один потраплять усі числа, при розподілі яких на 3 виходить у залишку 0 (це числа 3, 6, 9), у другому - числа, при розподілі яких на 3 у залишку виходить 1 (це числа 1, 4, 7) , 10), і в третій - усі числа, при розподілі яких на 3 у залишку виходить 2 (це числа 2, 5, 8). Справді, отримані підмножини не перетинаються і їхнє об'єднання збігається з безліччю X.Отже, відношення «мати той самий залишок при розподілі на 3», задане на безлічі X,є ставленням еквівалентності. Зауважимо, що твердження про взаємозв'язок відносини еквівалентності та розбиття множини на класи потребує доказу. Ми його опускаємо. Скажімо лише, якщо відношення еквівалентності має назву, то відповідна назва дається і класам. Наприклад, якщо на множині відрізків задається відношення рівності (а воно є ставленням еквівалентності), то множина відрізків розбивається на класи рівних відрізків (див. рис. 99). Відношенню подібності відповідає розбиття множини трикутників на класи подібних трикутників.

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

Принцип розбиття множини на класи за допомогою деякого відношення еквівалентності є важливим принципом математики. Чому?

По перше, Еквівалентний - це означає рівносильний, взаємозамінний. Тому елементи одного класу еквівалентності взаємозамінні. Так, дроби, що опинилися в одному класі еквівалентності (1/2, 2/4, 3/6) невиразні з точки зору відношення рівності, і дріб 3/6 може бути замінений на інший, наприклад 1/2. І ця заміна не змінить результату обчислень.

По-друге, оскільки у класі еквівалентності виявляються елементи, нерозрізняні з погляду деякого відношення, вважають, що клас еквівалентності визначається будь-яким своїм представником, тобто. довільним елементом цього. Так, будь-який клас рівних дробів можна задати, вказавши будь-який дріб, що належить цьому класу. Визначення класу еквівалентності по одному представнику дозволяє замість всіх елементів множини вивчати сукупність окремих представників із класів еквівалентності. Наприклад, відношення еквівалентності «мати однакове число вершин», задане на множині багатокутників, породжує розбиття цієї множини на класи трикутників, чотирикутників, п'ятикутників і т.д. Властивості, властиві деякому класу, розглядаються однією його представнику.

По-третє, Розбиття безлічі на класи за допомогою відношення еквівалентності використовується для введення нових понять. Наприклад, поняття «пучок прямих» можна визначити як загальне, що мають паралельні між собою прямі.

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

Іншим важливим видом відносин є відносини порядку.

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

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

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

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

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

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

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

Наприклад, безліч натуральних чисел можна впорядкувати і за допомогою відношення "менше", і за допомогою відношення "кратно" - обидва є відносинами порядку. Але ставлення «менше», на відміну від відносини «кратно», має ще й властивість пов'язаності. Отже, відношення «менше» впорядковує безліч натуральних чисел лінійно.

Не слід думати, що це стосунки поділяються на відносини еквівалентності і відносини порядку. Існує безліч відносин, які є ні відносинами еквівалентності, ні відносинами порядку.

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

Нехай X - кінцева чи нескінченна безліч. Відношенням на X називається правило, яким «порівнюються» його елементи. Це неформальне визначення, але його цілком достатньо для наших цілей. Зауважимо, що для визначення відношення ми повинні чітко задати саме безліч; інакше кажучи, нам має бути ясно, які елементи потрібно порівнювати.

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

Відношення еквівалентності – це відношення дуже специфічного виду. Повертаючись до загальних визначень, припустимо, що X - множина, в якій було визначено ставлення. Зручно зафіксувати якийсь символ для позначення еквівалентності зазвичай використовують значок «~». З цього моменту «~» буде відношенням еквівалентності,

якщо всім виконані такі характеристики:

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

Друга властивість називається симетричністю. Ставлення на багатьох цілих чисел не симетрично. Справді, тоді як нерівність помилкова. З іншого боку, ставлення на рефлексивне, але не симетричне.

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

Ми завбачливо навели приклади відносин, які не задовольняють цим властивостям, тому що це єдиний шлях до розуміння їхнього дійсного сенсу. Саме володіння прикладами та контрприкладами забезпечує успіх у засвоєнні нових понять. У прикладах відношення еквівалентності не бракує. Рівність цілих чисел, очевидно, задовольняє всі властивості, виписані вище. Ставлення «той самий колір» на безлічі кольорових м'ячів - ще один простий і, мабуть, найяскравіший приклад. Серед прикладів відношення еквівалентності на безлічі багатокутників є такі відносини, як «однакова кількість сторін» і «одна й та сама площа».

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

Наведемо найпростіший приклад. Позначимо символом М безліч кольорових м'ячів із ставленням еквівалентності «той самий колір». Клас еквівалентності червоного м'яча М складається з усіх червоних м'ячів, що містяться в М.

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

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

Доведемо це безпосередньо з визначальних властивостей відношення еквівалентності. Якщо те, за визначенням класу еквівалентності, Зважаючи на симетричність, Але якщо то і тоді властивість транзитивності тягне Ми довели включення: . Подібне міркування доводить зворотне включення: Ймовірно, це все може здатися дещо педантичним. Але основний принцип - таке джерело плутанини та помилок, що нам не варто шкодувати зусиль на прояснення його точного змісту. Крім того, корисно усвідомити, що він безпосередньо випливає із визначення відношення еквівалентності. До речі про педантичність: ви зрозуміли, що властивість випливає із рефлексивності?

Основний принцип призводить до найважливішої якості відношення еквівалентності. Як і раніше, нехай X - безліч із ставленням еквівалентності тоді

(1) X - об'єднання своїх класів еквівалентності щодо та

(2) два різні класи еквівалентності не можуть мати загального елемента.

Перше твердження випливає з факту, що часто згадується: клас еквівалентності елемента містить сам цей елемент. Для підтвердження другого припустимо, що елементи так як за основним принципом Аналогічно Так що у. Зауважимо, що властивості (1) і (2) означають, що безліч X розбито на підмножини, що не перетинаються, класи еквівалентності. Іншими словами, ми маємо справу з розбиттям множини

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

Закінчимо цей параграф прикладом, у якому проявляється нарешті справжня природа дробів. З чого складається дріб? Коли Ви дивитеся на неї, то бачите два числа, одне з яких (знаменник) має бути ненульовим. Звичайно, Ви її, мабуть, сприймаєте як приватне. Але якщо на Вас натиснути, Ви можете спробувати вибрати легший вихід і сказати, що дріб насправді - пара чисел, одне з яких не дорівнює нулю. Проте таке визначення некоректне.

У математиці дві пари рівні, якщо вони мають однакові перший та другий елементи. Так, пари (2,4) та (1,2) нерівні. Але дроби 2/4 та 1/2 рівні; так що дроби – не пари чисел.

Що таке дроби? Це елементи фактор безлічі! Розглянемо безліч пар цілих На стандартному жаргоні Дві пари і цілих чисел можна тепер називати еквівалентними, якщо легко перевірити, що це відношення еквівалентності, а дріб - клас еквівалентності множини щодо цього відношення. Отже, означає не пару а безліч всіх пар з еквівалентних Отже, безліч раціональних чисел - це фактор безлічі по тільки що певному відношенню еквівалентності.

Уявіть собі на хвилину, що Ви досі нічого про дріб не чули і Вам доведеться виходити з опису, зробленого вище. Якщо Вам тепер скажуть, що потрібно обчислювати з дробами, Ви відчуєте, що маєте вагому причину для паніки: Ви ж щойно вивчили, що дріб - це безліч. Думка про додаток до однієї нескінченної множини іншої нескінченної множини вселяє легке занепокоєння. Саме в цей момент приходить основний принцип. Вам не потрібно піклуватися про тягар усієї нескінченної множини; потрібно знати лише один елемент із нього. Цей елемент розповість вам про все, що

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

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

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

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

П р і м е р 1. Нехай на множині всіх негативних чисел N 0 = (0, 1, 2, 3, …) поставлено відношення Р: «числа хі умають той самий залишок при розподілі на 3». Доведемо, що Р- Відношення еквівалентності та визначимо класи еквівалентності, що визначаються цим ставленням.

Справді:

а) відношення Р– рефлексивно, оскільки будь-яке х Î N 0 має при розподілі на 3 той же залишок, що х;

б) Р– симетрично, оскільки для будь-яких х, у Î N 0 , якщо числа хі у уі хмають один і той же залишок при розподілі на 3;

в) Р– транзитивно, оскільки для будь-яких трьох чисел x, y, z Î N 0, якщо хі умають один і той же залишок при розподілі на 3 і уі zмають один і той же залишок при розподілі на 3, то числа хі zмають той самий залишок при розподілі на 3.

Отже, відношення Р: «числа хі умають один і той же залишок при розподілі на 3» є ставленням еквівалентності, і тому воно розбиває безліч N 0 на класи. Ці класи називаються класами відрахувань за модулем 3.

– так позначається клас чисел, дають при розподілі на 3 залишок 0, тобто. = (0, 3, 6, 9, 12 …), або = (3 k), де k Î N 0 .

– так позначається клас чисел, дають при розподілі на 3 залишок 1, тобто. = (1, 4, 7, 10, 13 …), або = (3 k + 1};

– так позначається клас чисел, дають при розподілі на 3 залишок 2, тобто. = (2, 5, 8, 11, 14 …), або = (3 k+ 2}.

Отже, ставлення Ррозбиває безліч N 0 на 3 класи, і взагалі, можна довести, що відношення «числа хі умають один і той же залишок при розподілі на m» розбиває це безліч на mкласів.

П р і м е р 2. На множині N– натуральних чисел поставлено ставлення Рнаступним чином: ( х 1 , у 1) Р (х 2 , у 2) .

Встановимо, що Рє ставленням еквівалентності та визначимо класи еквівалентності, що визначаються цим ставленням.

Справді, це ставлення:

а) рефлексивно, оскільки для будь-яких пар ( х, у) має місце
ху = ух;

б) симетрично, оскільки для будь-яких двох пар натуральних чисел ( х 1 , у 1) та ( х 2 , у 2), якщо х 1 у 2 = у 1 х 2 , то х 2 у 1 = у 2 х 1 ;

в) транзитивно, оскільки для будь-яких трьох пар ( х 1 , у 1), (х 2 , у 2), (х 3 , у 3), якщо х 1 у 2 = у 1 х 2 та х 2 у 3 = у 2 х 3 , то х 1 у 2 х 2 у 3 =у 1 х 2 у 2 х 3, тобто. х 1 у 3 = у 1 х 3 .

Таким чином, ставлення Ррозбиває безліч Nна класи еквівалентності. Кожен із цих класів називається раціональним числом.

Наприклад, пари (1, 2), (2, 4), (3, 6) належать одному класу ((1, 2), (2, 4), (3, 6), …). Можна цей клас визначити в такий спосіб, тобто. як безліч пар, еквівалентних парі (1, 2). Зазвичай, ці пари записують так: і називають дробами, а еквівалентність пар називають рівністю дробів. Для спрощення замінюють клас еквівалентності яким-небудь його елементом (представником), найчастіше найпростішим (нескоротним дробом), називаючи його раціональним числом. Таке спрощення припустимо, тому що раціональне число, як клас еквівалентності, однозначно визначається будь-яким елементом цього класу, а операції над раціональними числами, як над класами пар, визначаються через операції над представниками цих класів таким чином, що результати цих операцій не залежать від вибору представників .

Як видно, дріб – форма виразу числа, при цьому безліч дробів, що становлять один клас еквівалентності по відношенню Pна N , Виражає одне число, яке може виявитися цілим або дрібним позитивним числом, тобто. одне раціональне число.

Найчастіше застосовують інфіксну форму записи: .

Якщо відношення визначено на множині, то можливе таке визначення:

Прикладами множин із введеними на них бінарними відносинами є графита частково впорядковані множини.

Для певних властивостей:

Рефлексивність(англ. reflexivity): ;

Ставлення Rна безлічі Хназивається рефлексивним,якщо про кожен елемент множини Хможна сказати, що він знаходиться у відношенні Rз самим собою: хRх.Якщо ставлення рефлексивне, то кожній вершині графа є петля. І назад, граф, кожна вершина якого містить петлю, є графом рефлексивного відношення.

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

Антирефлексивність(англ. irreflexivity): ;

Ставлення Rна безлічі Хназивається антирефлексивнимякщо для будь-якого елемента з безлічі Хзавжди хибно хRх:.

Симетричність(англ. symmetry): ;

Ставлення Rна безлічі Хназивається симетричним, якщо виконується умова: з того, що елемент хзнаходиться у відношенні з елементом yслід, як і елемент yзнаходиться у відношенні Rз елементом х: xRyyRx.

Прикладами симетричних відносин можуть бути такі: відношення «паралельності» відрізків, відношення «перпендикулярності» відрізків, відношення «рівності» відрізків, відношення подібності до трикутників, відношення «рівності» дробів та ін.

Антисиметричність(англ. antisymmetry): ;

Ставлення Rназивають антисиметричним, якщо для будь-яких елементів хі yз істинності xRyслід помилковість yRx: : xRyyRx.

Транзитивність(англ. transitivity): ;

Відношення R на множині Хназивають транзитивним,якщо з того, що елемент хзнаходиться у відношенні Rз елементом y,а елемент yзнаходиться у відношенні Rз елементом zслід, що елемент хзнаходиться у відношенні Rз елементом z: xRyі yRzxRz.

Властивістю транзитивності має і відношення «довше» на безлічі відрізків: якщо відрізок адовше відрізка b, відрізок bдовше відрізка з, то відрізок адовше відрізка с.Відношення «рівності» на безлічі відрізків також має властивість транзитивності: (а = b, b = с) (а = с).

Зв'язок (англ. connectivity): ;

Ставлення Rна безлічі Хназивається пов'язаним,якщо для будь-яких елементів хі yз даної множини виконується умова: якщо хі yрізні, те чи хзнаходиться у відношенні Rз елементом y, або елемент yзнаходиться у відношенні Rз елементом х. За допомогою символів це визначенняможна записати так: xyxRyабо yRx.

Наприклад, властивість зв'язаності має відношення «більше» для натуральних чисел: для будь-яких різних чисел х і y можна стверджувати, або x> y, або y> x.

Асиметричність(англ. assymetric relation): .

Виділяються такі види відносин:

квазіпорядку (англ. quasiorder) - рефлексивне транзитивне;

еквівалентності (англ. equivalence) - рефлексивне симетричне транзитивне;

Ставлення Rна безлічі Хназивається ставленням еквівалентності,якщо воно одночасно має властивість рефлексивності, симетричності та транзитивності.

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

У розглянутому вище відношенні «рівності дробів», безліч Хрозбилося на три підмножини: ( ; ; }, {; } , (). Ці підмножини не перетинаються, які об'єднання збігається з безліччю Х, тобто. маємо розбиття множини на класи.

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

часткового порядку (англ. partial order) - рефлексивне антисиметричне транзитивне;

Бінарне відношенняна безлічі називається ставленням часткового порядку(англ. partial order relation

Рефлексивність(англ. reflexivity): .

Антисиметричність(англ. antisymmetry): якщо, то.

Транзитивність(англ. transitivity): якщо, то.

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

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

строгого порядку (англ. strict order) - антирефлексивне антисиметричне транзитивне;

Бінарне відношенняна безлічі називається суворим ставленням часткового порядку(англ. strict order relation), якщо воно має такі властивості:

Антирефлексивність(англ. irreflexivity): - не виконується.

Антисиметричність(англ. antisymmetry): якщо, то.

Транзитивність: (англ. transitivity) якщо, то.

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

лінійного порядку (англ. total order) - повне антисиметричне транзитивне;

Якщо відношення порядку має ще й властивість зв'язаності, то кажуть, що воно є відношенням лінійного порядку. Наприклад, відношення «менше» на множині натуральних чисел.

Бінарне відношенняна безлічі називається ставленням лінійного порядку(англ. total order relation), якщо воно є ставленням часткового порядку і має наступну властивість: або, або.

домінування (англ. dominance) - антирефлексивне антисиметричне.

толерантності

Відношенням толерантності (або просто толерантністю) на множині X називається бінарне відношення, що задовольняє властивостям рефлексивностіі симетричностіале не обов'язково є транзитивним. Таким чином, відношення еквівалентності є окремим випадком толерантності.

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

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

Ставлення толерантності часто використовується для опису відносини подібності між реальними об'єктами, відносин знайомства чи дружби для людей. У всіх цих випадках властивість транзитивності не передбачається обов'язково бути виконаною. Справді, Іванов може бути знайомий з Петровим, Петров - з Сидоровим, але заодно Іванов і Сидоров може бути незнайомі між собою.

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

Приклади відносин

Приклади рефлексивних відносин: рівність, одночасність, схожість

Приклади нерефлексивних відносин: «піклуватися про», «розважати», «нервувати»

Приклади транзитивних відносин: «більше», «менше», «рівно», «подібно», «вище», «північніше»

Приклади симетричних відносин: рівність (=), нерівність, відношення еквівалентності, подоби, одночасності, деякі відносини спорідненості (наприклад, відношення братства).

Приклади антисиметричних відносин: більше, менше, більше або одно.

Приклади асиметричних відносин: відношення «більше» (>) і «менше» (<).

Бінарне відношенняна безлічі називається ставленням еквівалентності(англ. equivalence binary relation), якщо воно має такі властивості:

Рефлексивність: .

Симетричність: якщо то.

Транзитивність: якщо, то

Відношення еквівалентності позначають символом. Запис вичитають як "еквівалентно"

Ставлення рівності() є тривіальним прикладом відношення еквівалентності на будь-якій множині.

Ставлення рівності за модулем: на безлічі цілих чисел

Ставлення паралельностіпрямі на площині.

Ставлення подобифігур на площині.

Ставлення рівносильностіна безлічі рівнянь.

Ставлення зв'язностівершин у графі.

Ставлення бути одного зростанняна багатьох людей.

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

Множини називаються класамиданого розбиття.

Якщо на безлічі M задано відношення еквівалентності, то воно породжує розбиття цієї множини на класи еквівалентностітаке, що:

будь-які два елементи одного класу знаходяться у відношенні

будь-які два елементи різних класів не знаходяться у відношенні

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

Рівність- Класичний приклад відношення еквівалентності на будь-якій множині.