Бінарне відношення

Бінарне відношення — це особливий тип відношення з арністю два. До типових бінарних відношень належать, наприклад, «менше ніж», рівність, подільність, «більше ніж» тощо.

Приклади

Бінарне відношення — одне з типових і найпоширеніших відношень. Водночас воно має деякі цікаві властивості, які ми тут опишемо.

Прикладом бінарного відношення може бути зв'язок «батько — син», пара «транспортний засіб — кількість коліс» або загальніше «об'єкт — властивість об'єкта». Об'єктом може бути тварина, а властивістю — кількість ніг, середня тривалість життя, кількість волосин на голові тощо.

Бінарне відношення R між множинами M₁ і M₂ можна означити так: R ⊆ M₁ × M₂. Бінарне відношення — це множина пар, причому ця множина є підмножиною декартового добутку двох множин, між якими відношення запроваджуємо. Отже, відношення «батько — син» може бути відношенням між множинами всіх людей, між множинами всіх людей у Європі чи в Києві. Множину можна обмежити й іншим способом: можемо сказати, що відношення означаємо між множинами всіх чоловіків, а не людей загалом.

Для бінарних відношень зазвичай використовуємо спеціальне позначення. Замість того щоб писати (a; b) ∈ R, можемо написати aRb. Наприклад, замість (3; 1) ∈ > можемо написати 3 > 1. Подібно для інших відношень. Отже, запис aSb рівносильний запису (a; b) ∈ S.

Обернене відношення

Обернене відношення — це відношення, протилежне до поточного. (Увага, не плутай із доповненням відношення.) Яке відношення протилежне до відношення «менше ніж»? «Більше ніж». Якщо відношення «менше ніж» містить елемент (4; 7), тобто 4 < 7, то обернений елемент буде протилежним: 7 > 4, в оберненому відношенні буде обернена пара (7; 4).

Якщо маємо відношення R ⊆ M₁ × M₂, то обернене відношення R⁻¹ будуємо так: беремо всі елементи (a; b) ∈ R і вносимо в R⁻¹ їхню обернену пару. Тобто якщо відношення R містить елемент (a; b), то відношення R⁻¹ має містити елемент (b; a). Це виконується й навпаки: якщо R⁻¹ містить елемент (b; a), то відношення R має містити елемент (a; b).

Якщо записати це формально, то відношення R⁻¹ обернене до R тоді й лише тоді, коли виконується:

$$\forall a\in M_1,\forall b\in M_2:\quad (a; b)\in R \Leftrightarrow (b; a)\in R^{-1}$$

Отже, 6 < 8 тоді й лише тоді, коли 8 > 6. Подібно для інших пар.

Композиція відношень

Бінарні відношення можна поєднувати в композицію. Нехай маємо два відношення: перше, R, — «бути батьком свого сина», і друге, S, — «бути братом своєї сестри». Отже, відношення R містить пари $(\text{батько}; \text{син})$, друге відношення містить пари $(\text{брат}; \text{сестра})$.

Спробуймо тепер утворити композицію відношень. Утвориться нове відношення, позначимо його $R \circ S$, і це відношення містить елемент (a; c) тоді й лише тоді, коли (a; b) ∈ R і водночас (b; c) ∈ S. Зверни увагу, що в обох елементах трапляється b: один раз на другому місці, а потім на першому місці пари. Це свого роду сполучний елемент композиції.

Приклад: $R={(\text{Антон}; \text{Марко}), (\text{Петро}; \text{Яків})}$ і $S={(\text{Марко}; \text{Яна}), (\text{Марко}; \text{Леся}), (\text{Яків}; \text{Люба})}$. Антон — батько Марка, Петро — батько Якова. Марко має сестер Яну й Лесю, а Яків має сестру Любу.

Тепер утворімо композицію відношень: $R \circ S$. Шукаємо таку пару з R, у якої на місці сина стоїть той, хто у відношенні S значиться як брат. Наприклад, ці дві пари: $(\text{Антон}; \text{Марко})$ і $(\text{Марко}; \text{Яна})$. Марко — сполучний елемент, він нам далі не потрібен, а з решти імен створюємо нову пару: $(\text{Антон}; \text{Яна})$. Отже, відношення $R \circ S$ містить пару $(\text{Антон}; \text{Яна})$. Марко має ще одну сестру, Лесю, її теж додамо до композиції: $(\text{Антон}; \text{Леся})$. Нарешті лишився син Яків. Він має сестру Любу. Тож маємо дві пари: $(\text{Петро}; \text{Яків})$ і $(\text{Яків}; \text{Люба})$. З них створюємо ще один елемент: $(\text{Петро}; \text{Люба})$.

Результат — відношення: $R \circ S = {(\text{Антон}; \text{Яна}), (\text{Антон}; \text{Леся}), (\text{Петро}; \text{Люба})}$. Як можна було б назвати це відношення? Найімовірніше, «бути батьком своєї доньки».

Ще раз повне означення:

$$(a; c) \in (R \circ S) \Leftrightarrow \exists b\quad (a; b) \in R \wedge (b; c) \in S$$

Примітка: іноді використовують зворотний запис, тобто для того самого означення замість $R \circ S$ писали б $S \circ R$.