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

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

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

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 – множиною прибуття відповідності. Разом їх називають базовими множинами відповідності.