Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням 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.
У випадку рівних множин А та В відношення, задане на А та В, називають бінарним відношенням, заданим на множині А (або бінарним відношенням на множині А). Таким чином, бінарне відношення, задане на деякій множині А, – це довільна підмножина множини А2.
Прикладом бінарного відношення, заданого на множині N, є множина {<n1,n2>| n1ÎN, n2ÎN, n1<n2}, яка складається з упорядкованих пар невід’ємних цілих чисел таких, що перше число пари менше за друге, тобто дане відношення описує той зв’язок між числами, який ми звикли називати «…менш, ніж…». Іншим прикладом бінарного відношення на множині N є множина {<n,m>| nÎN, mÎN, n та m – парні числа}. Прикладом бінарного відношення, заданого на множині людей, є множина {<l1,l2>| l1,l2 – люди, l1 – брат l2}, яка описує такий тип родинного зв’язку, як «бути братом». Наступний приклад бінарного відношення – відношення включення, задане на булеані деякої множини А. Позначимо це відношення символом Í, тоді Í ={<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} називається відношенням тотожності на А, або діагоналлю множини А, й позначається iA. Елементи відношення iA назвемо діагональними елементами, або діагональними парами.
Прикладом відношення тотожності є відношення {<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, заданим на множинах А1,…,Аn, називається довільна підмножина декартова добутка множин А1,…,Аn, тобто RÍА1´…´А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>} не є відношенням, заданим на множинах А, В, С, тому що Х не є підмножиною множини А´В´С.
У випадку, коли А1=…=Аn=А, відношення, задане на множинах А1,…,А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 – студент} є унарним відношенням, заданим на множині людей, й задає властивість «бути студентом».
