Лекція 2. Декартів добуток множин. Відношення

 

Декартів добуток множин

 

Упорядкованою парою об’єктів х та y (позначається < x, y >) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у певному порядку. Поняття упорядкованої пари можна поширити й розглядати для будь-якого цілого додатного числа n ³2 упорядковану n -ку об’єктів х ₁,…, х_n (позначається < х ₁,…, х_n >). Об’єкт х_і називається і -м компонентом упорядкованої n -ки. Упорядковані n -ки називають також кортежами.

Декартовим добутком множин А та В (позначається А * В або А ´ В) називається множина

А ´ В ={< a, b >| a Î A, b Î B },

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

Наприклад, декартовим добутком множин А ={ a, b } та В ={1,2,3} є множина A ´ B ={< a,1>,< a,2>,< a,3>,< b,1>,< b,2>,< b,3>}. Побудуємо декартів добуток множин В та А. Маємо: В ´ А ={<1, a >,<2, a >,<3, a >,<1, b >, <2, b >,<3, b >}. Як бачимо, А ´ В ≠ В ´ А, отже, операція ´ не комутативна.

Декартовим добутком множин А ₁ ,…,А_n (позначається А ₁´…´ А_n або А ₁*…* А_n) називається множина

А ₁´…´ А_n ={< a ₁,…, a_n >| a ₁Î A ₁,…, a_n Î A_n },

тобто множина усіх упорядкованих n -ок, побудованих з елементів множин А ₁,…, А_n таким чином, що і -й компонент кожної n -ки належить множині А_і (і =1,…, n).

Наприклад, декартовим добутком множин А ₁={ a, b }, A₂={ b, c }, A ₃={ b, d } є множина А ₁´ А ₂´ А ₃={< a, b, b >,< a, b, d >,< a, c, b >,< a, c, d >,< b, b, b >, < b, b, d >,< b, c, b >,< b, c, d >}.

Якщо для деякого і (і =1,…, n) А_і =Æ, то А ₁´…´ А_n =Æ.

Якщо А ₁=…= А_n = А, то А ₁´…´ А_n позначається Аⁿ й називається n-м декартовим степенем множини А.

Наприклад, якщо А ={1,2}, то А ³={<1,1,1>,<1,1,2>,<1,2,1>,<1,2,2>, <2,1,1>,<2,1,2>,<2,2,1>,<2,2,2>}.

Між операцією декартова добутка та іншими операціями над множинами існують зв’язки. Доведемо, зокрема, що (А È В)´ С =(А ´ С)È(В ´ С).

Для цього покажемо спочатку, що (А È В)´ С Í(А ´ С)È(В ´ С). Множина (А È В)´ С є декартовим добутком двох множин ((А È В) та С), отже, елементи цієї множини – це упорядковані пари. Таким чином, маємо: < x,y>Î(А È В)´ С Þ x Î A È B, y Î C Þ x Î A або x Î B, y Î C Þ x Î A та y Î C або x Î B та y Î C Þ < x, y >Î A ´ C або < x, y >Î B ´ C, отже, доведено, що (А È В)´ С Í(А ´ С)È(В ´ С). Тепер покажемо, що (А ´ С)È(В ´ С)Í(А È В)´ С. < x, y >Î(А ´ С)È(В ´ С) Þ < x, y >Î(A ´ C) або < x, y >Î(B ´ C) Þ (x Î A та y Î C) або (х Î В та y Î C). Розглянемо випадок x Î A та y Î C. Маємо: x Î A та y Î C Þ х Î А È В, y Î C Þ < x, y >Î(A È B)´ C. Якщо х Î В та y Î C, то маємо: х Î В та y Î C Þ х Î(А È В), y Î C Þ < x, y >Î(A È B)´ C. Отже, у кожному випадку доведено, що (А ´ С)È(В ´ С)Í(А È В)´ С. Таким чином, рівність виконується.

 

Поняття відношення

 

Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декартова добутка А та В, тобто R Í А ´ В. Запис xRy означає < x, y >Î R. Іноді будемо задавати відношення на множинах А та В у вигляді xRy Û Р (х, у), де Р (х, у) – твердження, яке є необхідною й достатньою умовою того, що < x, y >Î R.

Наприклад, множина R={<1,2>,<1,3>,<3,1>,<3,5>} є відношенням, заданим на множинах А ={1,2,3} та В ={1,2,3,4,5}, оскільки R Í А ´ В, а множина С ={<1,3>,<4,3>,<1,2>,<2,6>,<3,3>,<1,1>,<1,4>} не є відношенням, заданим на множинах А та В, тому що С Ë А ´ В. Прикладом відношення, заданого на множинах N та Z, є множина М ={< n, z >| n Î N, z Î Z, n =| z |}, що складається з упорядкованих пар чисел виду < n, n > або < n,- n >, де n Î N. Легко переконатися, що M Í N ´ Z.

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

Прикладом бінарного відношення, заданого на множині N, є множина {< n ₁, n ₂>| n ₁Î N, n ₂Î N, n ₁< n ₂}, яка складається з упорядкованих пар невід’ємних цілих чисел таких, що перше число пари менше за друге, тобто дане відношення описує той зв’язок між числами, який ми звикли називати «…менш, ніж…». Іншим прикладом бінарного відношення на множині N є множина {< n, m >| n Î N, m Î N, n та m – парні числа}. Прикладом бінарного відношення, заданого на множині людей, є множина {< l ₁ ,l ₂>| l ₁ ,l ₂ – люди, l ₁ – брат l ₂}, яка описує такий тип родинного зв’язку, як «бути братом». Наступний приклад бінарного відношення – відношення включення, задане на булеані деякої множини А. Позначимо це відношення символом Í, тоді Í ={< S, T >| S, T ÎP(A), S Í T }. Якщо, наприклад, А ={1,2,3,4}, то упорядкована пара множин <{2,4},{1,2,4}> належить відношенню включення, оскільки {2,4}Í{1,2,4}, а упорядкована пара <{1,2},{2,3,4}> – ні, тому що {1,2}Ë{2,3,4}.

Бінарне відношення на множині А виду {< x, x >| x Î A } називається відношенням тотожності на А, або діагоналлю множини А, й позначається i_A. Елементи відношення i_A назвемо діагональними елементами, або діагональними парами.

Прикладом відношення тотожності є відношення {< a, a >,< b, b >, < c, c >,< d, d >}, задане на множині А ={ a, b, c, d }. Відношення R ={< a, a >, < c, c >,< d, d >} не є діагоналлю множини А, оскільки містить не усі пари виду < x, x >, побудовані з елементів множини А (< b, b >Ï R).

Розглянемо узагальнення поняття відношення, заданого на двох множинах. Відношенням R, заданим на множинах А ₁ ,…,А_n, називається довільна підмножина декартова добутка множин А ₁,…, А_n, тобто R Í А ₁´…´ А_n.

Наприклад, множина R ={< a,2, f,>,< c,4, t >,< b,2, n >,< c,2, f >} є відношенням, заданим на множинах A ={ a, b, c }, B ={1,2,3,4}, C ={ f, g, n, m, t }, оскільки, як неважко переконатися, R Í А ´ В ´ С. Множина Х ={<1,2,3>, < a, b, c >} не є відношенням, заданим на множинах А, В, С, тому що Х не є підмножиною множини А ´ В ´ С.

У випадку, коли А ₁=…= А_n = А, відношення, задане на множинах А ₁,…, А_n, називають n-арним відношенням, заданим на множині А. Зрозуміло, що n -арне відношення, задане на множині А, – це довільна підмножина множини Аⁿ. Для значень n =1 та n =3 (як й для n =2) існують спеціальні назви відповідних відношень. Так, при n =1 відношення називається унарним, або властивістю на множині А; при n =3 відношення називається тернарним

Наприклад, множина S ={< n, m, k >| n, m, k Î N, k = n + m } є тернарним відношенням на множині N, оскільки S Í N ´ N ´ N (вираз n, m, k Î N використано для скорочення запису й означає n Î N, m Î N, k Î N). Дане відношення складається з тих упорядкованих трійок невід’ємних цілих чисел, у яких число, що є третім компонентом, – це сума чисел, що стоять на першому й другому місцях трійки. Таким чином, трійка <2,5,7> належить S, а трійка <3,4,5> – ні. Множина Р ={ x | х – людина, x – студент} є унарним відношенням, заданим на множині людей, й задає властивість «бути студентом».

 

Операції над відношеннями

 

Нехай R ₁, R ₂ – відношення, задані на множинах A ₁,…, A_n. Об’єднанням відношень R₁ та R₂ (позначається R ₁È R ₂) називається множина R ₁È R ₂={< a ₁,…, a_n >| < a ₁,…, a_n >Î R ₁ або < a ₁,…, a_n >Î R ₂}. Перетином відношень R₁ та R₂ (позначається R ₁Ç R ₂) називається множина R ₁Ç R ₂={< a ₁,…, a_n >| < a ₁,…, a_n >Î R ₁, < a ₁,…, a_n >Î R ₂}. Різницею відношень R ₁ та R ₂ (позначається R ₁\ R ₂) називається множина R ₁\ R ₂={< a ₁,…, a_n >| < a ₁,…, a_n >Î R ₁, < a ₁,…, a_n >Ï R ₂}. Доповненням відношення R ₁ (позначається R ₁¢) називається множина R ₁¢= А ₁´…´ A_n \ R ₁, тобто R ₁¢={< a ₁,…, a_n >| < a ₁,…, a_n >Î А ₁´…´ A_n, < a ₁,…, a_n >Ï R ₁}. Вираз < a ₁,…, a_n >Î R ₁¢ означає, що < a ₁,…, a_n >Ï R ₁ (при цьому, звичайно, < a ₁,…, a_n >Î А ₁´…´ A_n, але для скорочення запису це твердження опускають).

Нехай, наприклад, A ₁={1,2,3}, A ₂={ a, b, c }, R ₁, R ₂ – відношення, задані на множинах А ₁ та А ₂, й R ₁={<1, a >,<1, b >,<2, b >,<3, c >}, R ₂={<1, b >, <3, c >,<3, a >}. Тоді:

R ₁È R ₂={<1, a >,<1, b >,<2, b >,<3, c >,<3, a >},

R ₁Ç R ₂={<1, b >,<3, c >},

R ₁\ R ₂={<1, a >,<2, b >},

R ₁¢={<1, c >,<2, a >,<2, c >,<3, a >,<3, b >}.

Розглянемо дві операції, визначені для відношень, заданих на двох множинах. Нехай відношення R задано на множинах А та В. Відношенням, оберненим до R (позначається R ^-1), називається відношення, задане на множинах В та А, виду R ^-1={< x, y >| < y, x >Î R }.

Нехай, наприклад, А ={ а, с, е }, В ={1,3,5}, R Í А ´ В й R ={< a,1>, < a,3>,< c,3>,< c,5>,< e,5>}. Тоді R ^-1={<1, a >,<3, a >,<3, c >,<5, c >,<5, e >}. Відношен-ням, оберненим до відношення Í, заданого на булеані деякої множини А, є відношення, задане на булеані множини А, виду {< S, T >| < T, S >ÎÍ}, тобто множина упорядкованих пар < S, T > підмножин множини А таких, що Т Í S, або S Ê Т. Отже, відношенням, оберненим до Í, є відношення Ê.

Нехай R ₁ – відношення, задане на множинах А та В, а R ₂ – відношення, задане на множинах В та С. Добутком (або композицією) відношень R ₁ та R ₁ (позначається R ₁* R ₂ або R ₁○ R ₂) називається відношення, задане на множинах А та С, виду R ₁* R ₂={< x, y >| для деякого z з B < x, z >Î R ₁, < z, y >Î R ₂}. Іншими словами, добуток відношень R ₁ та R ₂ складається з таких упорядкованих пар < x, y >, які «побудовані» з пар виду < x, z > та < z, y >, що належaть відповідно відношенням R ₁ та R ₂.

Наприклад, нехай А ={ a, b, c, d }, B ={1,2,3}, C ={2,4,6}, R ₁Í A ´ B, R ₂Í B ´ C, R ₁={< a,3>,< a,2>,< b,1>,< c,2>}, R ₂={<2,2>,<3,6>}. Тоді добуток R ₁ та R ₂ – це відношення, задане на множинах А та С, виду R ₁* R ₂={< a,6>,< a,2>,< c,2>}. Розглянемо тепер відношення R ₃={< a,1>, < b,1>,< d,1>}, задане на множинах А та В, й обчислимо R ₃* R ₂. Оскільки відношення R ₃ та R ₂ не містять пар виду < x, z > та < z, y >, тобто таких пар, що другий компонент першої пари (тієї, що належить відношенню R ₃) збігається з першим компонентом другої пари (тієї, що належить відношенню R ₂), пар виду < x, y > утворити не можна, отже, R ₃* R ₂=Æ.

Теорема 5. Нехай R, R ₁, R ₂, R ₃ – бінарні відношення на множині А. Тоді:

1) (R ^-1)^-1= R, 2) (R ₁È R ₂)^-1= R ₁^-1È R ₂^-1,

3) (R ₁Ç R ₂)^-1= R ₁^-1Ç R ₂^-1, 4) (R ^-1)¢=(R ¢)^-1,

5) (R ₁\ R ₂)^-1= R ₁^-1\ R ₂^-1, 6) R È R = R Ç R = R,

7) R ₁*(R ₂È R ₃)=(R ₁* R ₂)È(R ₁* R ₃), 8) (R ₁È R ₂)* R ₃=(R ₁* R ₃)È(R ₂* R ₃).

9) (R ₁* R ₂)* R ₃= R ₁*(R ₂* R ₃), 10) (R ₁*R₂)^-1= R ₂^-1* R ₁^-1.

Доведемо рівність 4. Використовуючи означення доповнення відно-шення та означення відношення, оберненого до даного, маємо: < x, y >Î(R ^-1)¢ Þ < x, y >Ï R ^-1 Þ < y, x >Ï R Þ < y, x >Î R ¢ Þ < x, y >Î(R ¢)^-1. Отже, (R ^-1)¢Í(R ¢)^-1. Покажемо, що (R ¢)^-1Í(R ^-1)¢. < x, y >Î(R ¢)^-1 Þ < y, x >Î R ¢ Þ < y, x >Ï R Þ < x, y >Ï R ^-1 Þ < x, y >Î(R ^-1)¢. Отже, показали, що (R ^-1)¢=(R ¢)^-1.

Доведемо останню рівність. Використовуючи означення відношення, оберненого до даного, та означення добутку відношень, маємо: < x, y >Î(R ₁* R ₂)^-1 Þ < y, x >Î(R ₁* R ₂) Þ існує такий елемент z з множини A, що < y, z >Î R ₁ тa < z, x >Î R ₂ Þ < x,z>Î R ₂^-1, < z, y >Î R ₁^-1 Þ < x, y >Î R ₂^-1* R ₁^-1. Отже, (R ₁* R ₂)^-1 Í R ₂^-1* R ₁^-1. Покажемо, що R ₂^-1* R ₁^-1 Í (R ₁* R ₂)^-1. < x, y >Î R ₂^-1* R ₁^-1 Þ існує такий елемент z з множини A, що < x, z >Î R ₂^-1 та < z, y >Î R ₁^-1 Þ < z, x >Î R ₂, < y, z >Î R ₁ Þ < y, x >Î R ₁* R ₂ Þ < x, y >Î(R ₁* R ₂)^-1. Таким чином, доведено, що R ₂^-1* R ₁^-1 Í (R ₁* R ₂)^-1, отже, рівність 10 доведено.

 

Види бінарних відношень

 

Бінарне відношення R на множині А називається симетричним, якщо < x, y >Î R Þ < y, x >Î R. Пару виду < y, x > назвемо оберненою до пари виду < x, y >.

Наприклад, нехай на множині А ={ a, b, c, d } задано відношення R ={< b, c >,< d, d >,< a, d >,< c, b >,< d, a >}. Неважко перевірити безпосередньо, що з кожною парою виду < x, y > відношення R містить пару виду < y, x > (дo пари < b, c > у відношенні є обернена пара < c, b > й навпаки, дo пари < a, d > – пара < d, a >, пара < d, d > збігається з оберненою до неї), отже, R симетричне. Симетричним є відношення B ={< x, y >| x, y – брати}, задане на множині людей. Дійсно, < x, y >Î B Þ x, y – брати Þ y, x – брати Þ < y,x>Î В, тобто умова симетричності для відношення В виконується. Відношення R ={< x, y >| x – брат y }, задане на множині людей, не є симетричним, оскільки з того, що < x, y >Î R, не випливає, що < y, x >Î R, адже не обов’язково у є братом х, коли х є братом у (у може виявитися сестрою х). Не є симетричним й відношення {< b, c >,< a, b >,< b, a >}, задане на множині А, тому що воно не містить пари, оберненої до пари < b, c >.

Бінарне відношення R на множині А назвемо антисиметричним, якщо < x, y >Î R, < y, x >Î R Þ x = y, тобто якщо R містить пару виду < x, y >, яка складається з різних елементів, то R не містить обернену до неї пару виду < y, x >.

Наприклад, відношення R ={< c, d >,< a, a >,< c, c >,< b, a >}, задане на множині A ={ a, b, c, d }, антисиметричне, оскільки кожна пара, що належить відношенню разом з оберненою до неї парою, складається з однакових елементів (< a, a >Î R, < а, а >Î R Þ а = а; < с, с >Î R, < с, с >Î R Þ с = с). Антисиметричним є також відношення Q ={< a, b >,< c, d >,< b, c >} на множині А, тому що Q не містить жодної пари виду < x, y > такої, що х та у різні й < у, х > належить Q (тобто умова антисиметричності не порушується для Q). Відношення R ={< a, b >,< b, b >, < b, a >} на А не антисиметричне, тому що < a, b >Î R, < b, a >Î R, але a ¹ b. Антисиметричним є відношення ³ на множині N, оскільки n ³ m, m ³ n Þ n = m. Відношення > теж є антисиметричним на N, тому що коли n > m, то m не може бути більше, ніж n, отже, умова антисиметричності не порушується для відношення > (адже якщо пари виду < n, m > та < m, n > не можуть одночасно належати відношенню >, то й вимагати виконання умови n = m не потрібно). Відношення В ={< x, y >| x, y – брати} на множині людей не є антисиметричним, оскільки з того, що < x, y >Î B та < y, x >Î B не випливає, що x = y (адже коли x, y – брати та у, х – брати, то це не означає, що х та у – одна й та сама людина).

Відношення R на множині А називається асиметричним, якщо < x, y >Î R Þ < y, x >Ï R, тобто для жодної пари, що належить асиметричному відношенню, у цьому відношенні не існує оберненої пари.

Наприклад, відношення {< b, d >,< c, a >} на множині А асиметричне (містить пару < b, d >, але не містить обернену до неї пару, тобто < d, b >; містить пару < c, a >, але не містить обернену до неї пару < a, c >). Відношення {< b, d >,< a, c >,< c, a >} на A не асиметричне, тому що разом з парою < a, c > містить обернену до неї пару < c, a >. Відношення {< a, b >,< c, c >} на А також не асиметричне, бо разом з парою < c, c > містить обернену до неї пару < c, c >.

Відношення R на множині А називається рефлексивним, якщо для будь-якого х Î А < x, x >Î R, тобто і_А Í R.

Наприклад, відношення R ={<1,2>,<2,2>,<2,1>,<1,1>,<3,3>,<3,2>}, задане на множині А ={1,2,3}, є рефлексивним, оскільки містить усі діагональні пари множини А. Рефлексивним є відношення R ={< x, y >| x та y – однолітки}, задане на множині людей, тому що твердження «х та х – однолітки» істинне для будь-якого х з множини людей, отже, R містить усі пари виду < x, x >. Прикладом нерефлексивного відношення на множині А є {<2,1>,<3,3>,<2,3>,<1,1>}, оскільки воно містить не усі діагональні пари множини А (у відношенні немає пари <2,2>). Відношення {< x, y >| x та y – студенти} на множині людей не рефлексивне, оскільки твердження «х та х – студенти» істинне не для кожного х з множини людей, а тільки для тих х, які є студентами (адже не усі люди є студентами).

Відношення R на множині А називається антирефлексивним (або іррефлексивним), якщо для усіх х з А < x, x >Ï R, тобто R не містить жодної діагональної пари множини А.

Наприклад, відношення {<1,2>,<3,1>,<2,3>} на множині {1,2,3} антирефлексивне, оскільки не містить жодної діагональної пари. Антирефлексивним є відношення {< x, y >| x та y – брати} на множині людей, оскільки твердження «х та х – брати» хибне для будь-якого х (адже жодна людина не може бути братом самої себе), отже, дане відношення не містить жодної діагональної пари. Прикладом не антирефлексивного відношення є відношення R ={< x, y >| x ділиться на y } на множині N ⁺. Зрозуміло, що R містить діагональні пари (твердження «х ділиться на х» істинне для будь-якого х Î N ⁺). Відношення {<1,1>,<2,1>,<1,2>} на множині {1,2} не антирефлексивне, бо містить діагональну пару <1,1>.

Відношення R на множині А називається транзитивним, якщо < x, y >Î R, < y, z >Î R Þ < x, z >Î R. Зрозуміло, що відношення R не транзитивне тоді й тільки тоді, коли для деяких x, у, z з множини А одночасно виконуються умови: < x, y >Î R, < y, z >Î R, < x, z >Ï R.

Наприклад, відношення {<2,3>,<2,2>,<3,2>,<3,3>}, задане на множині А ={1,2,3}, транзитивне, оскільки разом з парами <2,3> та <3,2> містить пару <2,2>, разом з парами <2,3> та <3,3> містить пару <2,3>, разом з парами <2,2> та <2,3> містить пару <2,3>, разом з парами <2,2> та <2,2> містить пару <2,2>, разом з парами <3,2> та <2,3> містить пару <3,3>, разом з парами <3,2> та <2,2> містить пару <3,2>, разом з парами <3,3> та <3,2> містить пару <3,2>, разом з парами <3,3> та <3,3> містить пару <3,3>. Таким чином, для кожного набору пар виду < x, y >, < y, z >, що належать даному відношенню, існує пара виду < x, z >, яка теж належить цьому відношенню. Відношення {<1,2>,<1,3>} на множині А також транзитивне, оскільки не існує такого набору пар виду < x, y >, < y, z >, що < x, y >Î R й < y, z >Î R, а < x, z >Ï R. Транзитивним є й відношення R ={< x, y >| x, y – парні числа} на множині N. Дійсно, нехай < x, y >Î R й < y, z >Î R, тобто х, у – парні числа та у, z – парні числа. Зрозуміло, що тоді х, z – парні числа, тобто < x, z >Î R. Прикладом не транзитивного відношення на множині А є R ={<2,1>,<1,2>,<2,2>}, оскільки R містить пари <1,2> та <2,1>, але не містить пари <1,1>. Відношення {< x, y >| x – дідусь y } на множині людей не транзитивне, оскільки з того, що х є дідусем у, а у є дідусем z не випливає, що х є дідусем z.

Теорема 6. Нехай R – бінарне відношення на множині А. Тоді:

а) якщо R симетричне, то R = R ^-1;

б) якщо R рефлексивне та транзитивне, то R * R = R.

Доведемо твердження а). Покажемо спочатку, що коли R симетричне, то R Í R ^-1. Нехай < x, y >Î R. Оскільки R симетричне, то < у, х >Î R. Використовуючи визначення відношення, оберненого до даного, маємо < x, y >Î R ^-1, що й треба було довести. Покажемо тепер, що R ^-1Í R. Нехай < x, y >Î R ^-1. Тоді < у, х >Î R. З симетричності R випливає, що < x, y >Î R. Таким чином, R ^-1Í R. Отже, R ^-1= R.

Доведемо твердження б). Нехай < x, y >Î R * R. Це означає, що у множині А існує такий елемент z, що < x, z >Î R та < z, y >Î R. Але R транзитивне, тому < x, у >Î R, тобто R * R Í R. Покажемо, що R Í R * R. Нехай < x, y >Î R. Оскільки R рефлексивне, то < у, у >Î R, отже, < х, у >Î R * R, тобто R Í R * R. Таким чином, R = R * R.