Відношення

Означення 2.3. Довільна підмножина множини А₁´А₂´...´А_n називається відношенням, заданим або визначеним на множинах А₁, А₂,...,А_n. Якщо А₁=А₂=...=А_n=А, тобто річ йде про декартовий добуток n-ої степені множини А, то відношення R, яке задано на множинах А₁=А₂=...=А_n, називається n-арним відношенням на множині А.

Коли (а₁,а₂,...,а_n)ÎR, то говорять, що елементи a_i (i=1,..,n) знаходяться між собою у відношенні R або відношення R істинне для а₁,а₂,...,а_n. Якщо (а₁,а₂,...,а_n)ÏR, то вважають, що R хибне для а₁,а₂,...,а_n. При n=1 відношення називається унарним, при n=2 – бінарним, при n=3 – тернарним.

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

Частіше за все бінарні відношення записуються у вигляді співвідношень aRb, де R – відношення, яке встановлює зв’язок між елементами aÎA та bÎB.

Наведемо ще декілька прикладів бінарних відношень.

1. Якщо А – множина дійсних чисел, то {(x,y) | xÎA, yÎA, x²+y²=4} є бінарне відношення на А.

2. Нехай А – множина товарів в магазині, а В – множина дійсних чисел. Тоді {(x,y) | xÎA, yÎB, y – ціна x} – відношення множин А та В.

3. Якщо А – множина людей, то {(x,y) | xÎA, yÎA, y є рідним x} є бінарне відношення на А.

Означення 2.4. Область визначення відношення R на A та В є множина всіх аÎА таких, що для деяких bÎB маємо (a,b)ÎR. Іншими словами, область визначення R є множина всіх перших координат впорядкованих пар із R. Множина значень відношення R на А та В є множина всіх bÎB таких, що (a,b)ÎR для деяких aÎA. Іншими словами, множина значень R є множина всіх других координат впорядкованих пар із R.

В наведених прикладах вище, у (1) область визначення і множина значень співпадають із множиною {t: tÎ[-2;2]}. В (2) область визначення є множина А, а множина значень є множина всіх дійсних чисел, кожне з яких співпадає із ціною деякого товару в магазині. В (3) область визначення і множина є множиною всіх людей, які мають рідних.

Цікавими є такі окремі випадки відношень на А.

1. Повне (універсальне) відношення U=А´А, яке справджується для будь-якої пари (а₁,а₂) елементів з А. Наприклад, U – відношення “вчитися в одній групі” у множині А, де А – множина студентів групи ІС-61.

2. Тотожне (діагональне) відношення І, що виконується тільки між елементом і ним самим. Наприклад, рівність на множині дійсних чисел.

3. Порожнє відношення, яке не задовольняє жодна пара елементів з А. Наприклад, R – відношення “бути братом” у множині А, де А – множина жінок.

Оскільки відношення, задані на А та В – підмножини А´В, то для них визначені операції об’єднання, перерізу, різниці і доповнення (наступне справедливо для загального випадку відношення):

§ (а,b)ÎR₁ÈR₂ Û (а,b)ÎR₁ або (а,b)ÎR₂

§ (а,b)ÎR₁ÇR₂ Û (а,b)ÎR₁ і (а,b)ÎR₂

§ (а,b)ÎR₁\R₂ Û (а,b)ÎR₁ або (а,b)ÏR₂

§ (а,b)ÎR’ Û (а,b)ÏR (заперечення)

Крім того, виділяються специфічні для відношень операції: обернення (симетризація) і композиція.

Означення 2.5. Нехай RÍA´B є відношення на A´B. Тоді відношення R^-1 на В´А визначається наступним чином

R^-1 = {(b,a) | (a,b)ÎR}.

Іншими словами, (b,a)ÎR^-1 тоді і тільки тоді, коли (a,b)ÎR, або, що рівнозначно, bR^-1a тоді і тільки тоді, коли aRb. Відношення R^-1 називається оберненим (симетричним) відношенням до даного відношення R.

Перехід від R до R^-1 здійснюється взаємною перестановкою координат кожної впорядкованої пари. Наприклад, відношення R - “х дільник y”, має обернене до нього R^-1 – “x кратне y”. А відношення R = {(1,2), (3,4), (5,6)} буде мати обернене відношення R^-1={(2,1), (4,3), (6,5)}. При переході від R до R^-1 область визначення стає областю значення і навпаки.

Означення 2.6. Нехай RÍA´B – відношення на A´B, а SÍB´C – відношення на B´C. Композицією відношень R та S є відношення TÍA´С, визначене наступним чином:

T = {(a,c) | аÎА, сÎС та $bÎВ, (a,b)ÎR та (b,c)ÎS}.

Це відношення позначається T = R°S.

Наприклад, нехай R = {(1,2), (3,4), (5,6)} та S={(2,3),(2,7),(4,1),(6,9)}, тоді T₁ = R°S = {(1,3), (1,7), (3,1), (5,9)} та T₂ = S°R = {(2,4),(4,2)}. Інший приклад: R = {(x,x²) | xÎN} та S = {(x,x+2) | xÎN}, тоді T₁ = R°S = {(x,x²+2) | xÎN} та T₂ = S°R = {(x,(x+2)²) | xÎN}.

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

Означення 2.7. Нехай R – відношення на множині А. Ступенем відношення R на множині А є його композиція із самим собою. Позначається:

Rⁿ = R°…(n разів)…°R.

Відповідно, R⁰ = I, R¹ = R, R² = R°R і взагалі Rⁿ = R^n-1°R.

Теорема 2.1. Якщо R, R₁, R₂ – бінарні відношення, задані на множині А, то:

а) (R₁ÈR₂)°R = R₁°R È R₂°R; R₁ÍR₂ Þ R₁°R Í R₂°R.

б) (R^-1)^-1 = R; RÍR₁ Þ R^-1ÍR₁^-1.

в) (R₁°R₂)^-1 = (R₂^-1)° (R₁^-1).

г) (R₁ÇR₂)^-1 = (R₁^-1)Ç(R₂^-1).

д) (R°R₁)°R₂ = R°(R₁°R₂).

Доведення. а) Якщо (a,b)Î(R₁ÈR₂)°R, то існує елемент cÎA такий, що (a,с)ÎR₁ÈR₂ і (с,b)ÎR. Значить, (a,с)ÎR₁ або (a,с)ÎR₂ і (с,b)ÎR. Звідси маємо, що (a,b)ÎR₁°R або (a,b)ÎR₂°R, тобто (a,b)ÎR₁°R È R₂°R. Обернене включення доводиться аналогічно.

Друга частина твердження випливає з того, що коли R₁ÍR₂, то R₁ÈR₂= R₂, звідки маємо (в силу вище доведеного), що (R₁ÈR₂)°R = R₁°R È R₂°R = R₂°R, тобто R₁°R Í R₂°R.

б) (a,b)ÎR^-1 Û (b,а)Î(R^-1)^-1 Û (b,а)ÎR. Звідки випливає, що (R^-1)^-1 = R.

Для доведення другої частини зауважимо, що (a,b)ÎR Û (b,а)ÎR^-1, (a,b)ÎR Þ (a,b)ÎR₁ Þ (b,а)ÎR^-1 Þ (b,а)ÎR₁^-1, тобто R^-1ÍR₁^-1.

в) (a,b)Î(R₁°R₂)^-1 Û (b,а)Î(R₁°R₂) Þ ($сÎА | (b,c)ÎR₁ і (c,a)ÎR₂). Але тоді (c,b)ÎR₁^-1 і (a,c)ÎR₂^-1 Þ (a,b)Î(R₂^-1°R₁^-1), тобто (R₁°R₂)^-1 Í (R₂^-1)° (R₁^-1). Обернене включення доводиться аналогічно.

г) (a,b)Î(R₁ÇR₂)^-1 Û (b,a)ÎR₁ÇR₂ Û (b,a)ÎR₁ і (b,a)ÎR₂ Û (a,b)ÎR₁^-1 і (a,b)ÎR₂^-1, тобто (R₁ÇR₂)^-1 = (R₁^-1)Ç(R₂^-1).

д) Нехай (a,d)Î(R°R₁)°R₂, тоді існує cÎA такий, що (a,c)ÎR°R₁ і (c,d)ÎR₂. Отже існує такий b, що (a,b)ÎR, (b,c)ÎR₁ і (c,d)ÎR₂, а це означає, що (b,d)Î R₁°R₂ і (a,d)ÎR°(R₁°R₂), тобто (R°R₁)°R₂ Í R°(R₁°R₂). Обернене включення доводиться аналогічно. ►

Дата добавления: 2014-01-07