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

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

Виконаємо таке завдання: побудуємо графи заданих відношень.

1) граф відношення «бути паралельним», за умови, що а || b || с, k || d || e, f || h.

Які властивості має дане відношення?

Властивості рефлективності, симетричності і транзитивності.

2) граф відношення «бути рівними» на множині відрізків, якщо a = b = c, d = e, відрізок h не дорівнює жодному з даних відрізків.

Це відношення також має властивості рефлективності, симетричності і транзитивності.

3) На множині А = {1/2,1/3,1/4,2/4,2/6,3/6} встановлено відношення «бути рівним». Побудуємо граф даного відношення.

Усі ці відношення мають властивості рефлективності, симетричності і транзитивності.

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

Дане відношення розбило задані множини на підмножини:

1) {a, b, c}, {d, e}, {f, h} – підмножини паралельних між собою прямих;

2) {a, b, c}, {e, d}, {h}; - підмножини рівних між собою відрізків;

3) {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4} підмножини рівних між собою дробів.

Ці множини не перетинаються, а їх об’єднання співпадає з множиною X.

Отже, якщо у множині Х задано відношення еквівалентності, то воно розбиває цю множину на підмножини, які попарно не перетинаються (класи еквівалентності).

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

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

1) кожен елемент множини належить одному і тільки одному класу;

2) будь-які два елементи одного класу перебувають у даному відношенні еквівалентності;

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

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

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

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

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

Як слово «порядок» використовується в повсякденному житті?

Приклад: викликається 5 студентів різного зросту. Завдання: стати так, щоб на даній множині студентів встановити відношення порядку: «бути вищим».

Які властивості має дане відношення?

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

Виділяють певні види відношень порядку. Відношення порядку на множині називається:

– відношенням нестрогого порядку, якщо воно рефлексивне;

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

Множина із заданим на ній відношенням порядку називається впорядкованою множиною. Залежно від видів відношення порядку розрізняють і види впорядкованих множин.

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

– відношення «ділиться на» є відношенням нестрогого порядку;

– відношення «менше» є відношенням строгого порядку;

– відношення «менше або дорівнює» є відношенням нестрогого порядку.

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

Поняття відповідності

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

Наприклад, нумерація класів в школі: 1а, 1б, 1в, 2а, 2б, 2в і т.п. - це встановлення відповідності між множиною чисел {1,2,3,4} і множиною букв {а,б,в}. При вимірюванні довжини відрізків встановлюється відповідність між множиною відрізків і множиною дійсних чисел.

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

Нехай, наприклад, перший і другий гравці послідовно назвали такі міста: Запоріжжя, Ялта, Алчевськ, Кіровоград, Донецьк, Київ, Вінниця. Названі міста утворюють дві множини:

А ={Запоріжжя,Алчевськ,Донецьк,Вінниця};

В = {Ялта, Кіровоград, Київ}.

Зобразимо залежність між даними множинами схематично, або за допомогою графа. Множини А і В позначимо різними кругами.

На даних прикладах видно, що відповідність встановлюється між елементами двох множин. Такі відповідності називаються бінарними відповідностями.

Означення.Відповідністю між елементами двох множин (бінарною відповідністю) називається підмножина декартового добутку Х×У.

Множина Х називається множиною відправлення, а множина Y – множиною прибуття відповідності. Разом їх називають базовими множинами відповідності.