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

Бінарне відношення 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.