МНОЖИНИ І ВІДНОШЕННЯ

Зручним способом задання бінарного відношення R на скінченній множині M = {a1,a2,...,an} є задання за допомогою так званої матриці бінарного відношення. Це квадратна матриця C порядку n, в якій елемент cij, що стоїть на перетині i-го рядка і j-го стовпчика, визначається так

якщо aiRaj,

cij

в противному разі.

Приклад 1.14. Для скінченної множини M = {2,7,36,63,180} матриці наведених вище відношень R1, R2, R3 мають такий вигляд

Оскільки відношення на M є підмножинами множини M 2, то для них означeні всі відомі теоретико-множинні операції. Наприклад, перетином відношень "більше або дорівнює" і "менше або дорівнює" є відношення "дорівнює", об’єднанням відношень "менше" і "більше" є відношення "не дорівнює", доповненням відношення "ділиться на" є відношення "не ділиться на" тощо.

Аналогічно відповідностям для відношень можна означити поняття оберненого відношення і композиції відношень.

Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)-1=R. Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" - відношення "є дільником".

Композицією відношень R1 і R2 на множині M (позначається R1R2 ) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент cM, для якого виконується aR1c і cR2b. Наприклад, композицією відношень R1 - "є сином" і R2 - "є братом" на множині чоловіків є відношення R1R2 - "є небожем".

Наведемо список важливих властивостей, за якими класифікують відношення.

Нехай R - деяке відношення на множині M.

а). Відношення R називається рефлексивним, якщо для всіх aM має місце aRa.

Очевидно, що відношення R1,R2,R4,R5,R7 - рефлексивні.

б). Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного aM не виконується aRa.

Відношення "більше", "менше", "є сином" антирефлексивні. В той же час, відношення R6 не є ні рефлексивним, ні антирефлексивним.

Всі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.

в). Відношення R називається симетричним, якщо для всіх a,bM таких, що aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a,bM таких, що aRb і bRa маємо a = b.

Наприклад, відношення R3,R4,R5,R6,R8 - симетричні, а відношення R1,R2,R7 - антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді, коли R=R-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.Наприклад, відношення R1,R2,R4,R5,R7,R8,R9 - транзитивні, а відношення R3,R6 - не транзитивні.