Відношення

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

Загалом відношення означає деякий зв'язок між предметами або поняттями. Унарні (одномісні) відношення віддзеркалюють певну ознаку (властивість) елементів множини: всі елементи x множини X, які мають ознаку Р(x), утворюють підмножину АÍX, яку називають відношенням намножині X.

Відношення між парами об'єктів називаються бінарними (двомісними). Розглянемо дві множини X та Y, елементи яких складають упорядковані пари (x,y), побудовані за деяким законом. Якщо спосіб такого зіставлення упорядкованих пар визначений, то між множинами X і Y існує бінарне відношення. Елемент x називають першою координатою, а елемент y - другою координатою впорядкованої пари (x,y), або 2-мірного кортежа (x,y).

Відношення може бути n-арним, яким пов’язуються елементи n множин (приклад – множина-степінь Аⁿ). Як бінарне відношення породжує двомірні кортежи, так і n-арне породжує n-мірні кортежи (вектори). Наприклад, декартов добуток R³=R´R´R визначає 3-арне відношення, що породжує множину тримірних кортежей (векторів) виду (x,y,z), де x, y, z – дійсні числа, в тримірному лінійному (декартовому) просторі.

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

Означення 1.7. Відношенням Q множин А і В називається довільна підмножина QÍА´В декартова добутку цих множин.

Якщо впорядкована пара (a,b)ÎQ, то говорять, що a і b знаходяться у відношенні Q, з позначним записом aQb.

Якщо QÍА´А, то відношення Q називають бінарним відношенням на множині А. В подальшому замість терміну «бінарне відношення» будемо застосовувати термін «відношення».

Означення 1.8. Областю відправлення відношення QÍА´В називається множина А, елементи якої беруть участь у відношенні Q в якості перших елементів упорядкованих пар (a,b)ÎQ.

Означення 1.9. Областю прибуття відношення QÍА´В називається множина В, елементи якої беруть участь у відношенні Q в якості других елементів упорядкованих пар (a,b)ÎQ.

Означення 1.10. Відношенням, оберненим до відношення QÍА´В, називається відношення Q^-1ÍВ´А таке, що Q^-1={(b,a): (a,b)ÎQ}. Іншими словами, (b,a)ÎQ^-1 лише тоді, коли (a,b)ÎQ або, що рівносильно, bQ^-1a лише тоді, коли aQb.

Завдання відношення може бути здійснено наступними способами.

1. Перерахуванням упорядкованих пар, пов’язаних відношенням відповідності, як у прикладах 1.19 - 1.21.

2. Матрицею, кожен елемент a_ij якої дорівнює одиниці, якщо х_iQy_j, і нулю у протилежному випадку. Наприклад, відношення Q={(a₁,b₂), (a₁,b₃), (a₂,b₄), (a₃,b₅), (a₄,b₃)} на добутку А´В подається такою матрицею:

3. Стрілковою діаграмою (графом). Це робиться наступним чиним. Елементи x, y множин X, Y зображаються точками на площині. Якщо х_iQy_j, точки х_i і y_j з’єднаються лініями (не обов’язково прямими) зі стрілками, спрямованими від х_i до y_j. Зробивши таку операцію для всіх пар, що належать відношенню, одержимо його граф. Спрямовані лінії, що з’єднують пари точок, називають дугами, а точки, що зображують елементи множин, – вершинами графа. Як приклад, задання відношення Q={(a, 1), (a, 2), (b, 1), (с, 2), (с, 4), (с, 9), (d, 16)} на добутку X´Y у вигляді графа подано на рис. 1.4.

Якщо ми маємо два заданих відношення, то з них можна побудувати треттє, на підставі наступного озна-чення.

Означення 1.11. Нехай QÍА´В – від-ношення на А´В, а TÍВ´D – відношен-ня на В´D. Композицією відношень Q і T називається від-ношення МÍА´D, визначене таким чином: М={(a, d): існує такий елемент b із В, що (a,b)ÎQ і (b, d)ÎT}. Операцію композиції позначають так: М=T∘Q.

Теорема 1.1.Композиція відношень асоціативна, тобто якщо А, В, D, E – множини, QÍА´В, TÍВ´D і МÍD´E - відповідні відношення, то М∘(T∘Q)=(М∘T)∘Q.

Доведення.Рівність множин М∘(T∘Q)=(М∘T)∘Q має місце, якщоМ∘(T∘Q)Í(М∘T)∘Qі (М∘T)∘QÍМ∘(T∘Q).Доведемо перше з цих нестрогих включень.Покажемо, що М∘(T∘Q)Í(М∘T)∘Q. Нехай (a, e)ÎМ∘(T∘Q). Тоді існує такий елемент d із D, що (a,d)ÎT∘Q i (d,e)ÎМ. Оскільки (a,d)ÎT∘Q, існує таке bÎB, що (a,b)ÎQ і (b,d)ÎT. Оскільки (b,d)ÎT і (d,e)ÎМ, то (b,e)ÎМ∘T. Оскільки (b,e)ÎМ∘T і (a,b)ÎQ, то (a,e)Î(М∘T)∘Q. Таким чином, М∘(T∘Q)Í(М∘T)∘Q. Включення (М∘T)∘QÍМ∘(T∘Q)доводиться аналогічно. Надамо таку можливість читачеві.

Відношення на множині, тобто виду QÍА², може володіти спеціальними властивостями, які слідують з наступних означень.

Означення 1.12. Відношення QÍА² називається рефлексивним, якщо (a,a)ÎQ (або aQa) для всіх aÎА, що беруть участь у відношенні.

Це означає, що кожний елемент aÎА знаходиться у відношенні до самого себе (і, можливо, до інших елеметнів). Матриця такого відношення буде мати діагональ, заповнену одиницями, а на графі кожний aÎА буде мати петлю, тобто дугу ((a,a).

Означення 1.13. Відношення QÍА² називається антирефлексивним, якщо для всіх (a,b)ÎQ має місце нерівність a≠b.

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

Означення 1.14. Відношення QÍА² називається симетричним, якщо для всіх пар (a,b)ÎQ існують пари (b,a)ÎQ.

Означення 1.15. Відношення QÍА² називається антисиметричним, якщо для всіх aÎА і bÎА із (a,b)ÎQ і (b,a)ÎQ слідує a=b.

Означення 1.16. Відношення QÍА² називається транзитивним, якщо для всіх aÎА, bÎА і cÎА з того що (a,b)ÎQ і (b,c)ÎQ слідує (а,c)ÎQ.

Можливі три часткові випадки бінарних відношень на множині: тотожне, повне і порожнє. Якщо відношення QÍА² містить тільки пари (a,а)ÎQ і ніяких інших, воно називається тотожним. Якщо Q=А², то відношення Q називається повним. Якщо Q=0, таке відношення називається порожнім. Надаємо читичеві можливість самостійно виявити особливості матриць і графів таких відношень.

Означення 1.17. Відношення QÍА² називається відношенням еквівалентності, якщо воно є рефлексивним, симетричним і транзитивним.

Відношення Q на множині А, тобто QÍА², формується за деяким зазначеним принципом (правилом). Тому відношення еквівалентності Q на А розбиває множину А на класи еквівалентності, тобто підмножини, елементи яких еквівалентні один одному за певною ознакою и не еквівалентні елементам інших підмножин.

Відношення QÍА² з прикладу 1.23 є відношенням еквівалентності на множині А, оскільки воно відповідає означенню 1.17. Класи еквівалентності по відношенню Q визначені як класи еквівалентності для кожного aÎА завданням відношення Q={{x: xQa_i, xÎА, a_iÎА}: i= }. Для елемента a₁=1 маємо клас еквівалентності [a₁] = {1, 2, 4}. Аналогічно для елементів a₂ – a₆: [a₂] = {2, 1, 4}, [a₃] = {3, 5}, [a₄] = {4, 1, 2}, [a₅] = {5, 3}, [a₆] = {6}. Кількість різних класів еквівалентності дорівнює 3, це класи {1, 2, 4}, {3, 5}, {6}.

Сукупність класів еквівалентності поділяє множину А на підмножини, які не не мають спільних елементів. Заданням відношення еквівалентності QÍА² на множині А здійснюється разбиття цієї множини на підмножини, елементи яких еквівалентни один одному за певною ознакою (див. п.1.2). Розбиття множин на класи еквівалентності використовується в задачах управління реляційними базами даних.

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

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