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

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