Бінарне відношення на множині

Бінарним відношенням на множині називаємо бінарне відношення, означене між двома однаковими множинами.

Приклади

Бінарне відношення на множині — особливий тип бінарного відношення, коли обидва носії однакові. Отже, бінарне відношення на множині — це відношення R таке, що R ⊆ M × M.

Відношення «більше ніж» є бінарним відношенням на множині, бо з обох боків ми працюємо з числами. Тобто виконується > ⊆ ℝ × ℝ. Відношення «батько — кількість дітей» не є бінарним відношенням на множині, бо батька ми вибираємо з множини всіх людей, а кількість дітей — з якоїсь числової множини.

Властивості

Бінарне відношення R на множині M може мати деякі цікаві властивості. Кажемо, що відношення R…

• рефлексивне, якщо для всіх a ∈ M виконується (a; a) ∈ R.
• симетричне, якщо для всіх a, b ∈ M виконується: якщо (a; b) ∈ R, то й (b; a) ∈ R.
• антисиметричне, якщо для всіх a, b ∈ M виконується: якщо (a; b) ∈ R і водночас (b; a) ∈ R, то a = b.
• транзитивне, якщо для всіх a, b, c ∈ M виконується: якщо (a; b) ∈ R і водночас (b; c) ∈ R, то й (a; c) належить R.

Приклади рефлексивності

Рефлексивність означає, що елемент перебуває у відношенні сам із собою. Типовий приклад — рівність. Якщо рівність означено на множині натуральних чисел, то для будь-якого елемента a безперечно виконується a = a. Іншим прикладом може бути подільність. Там знову виконується, що число a ділиться на себе саме, тобто пара (a; a) належить відношенню подільності (сімка ділить сімку).

Відношення «менше ніж» уже не рефлексивне, бо не виконується a < a. Це неможливо, сімка не може бути меншою за сімку. Так само й відношення «бути батьком своєї дитини» — я не можу бути власним батьком. Такі відношення не рефлексивні.

Важливо, що рефлексивність має виконуватися для всіх елементів, недостатньо знайти лише деякі. Наприклад, відношення «любити когось». Я можу любити когось іншого, наприклад, контролера в автобусі, але можу любити й себе. Напевно, знайдеться людина, яка любить себе. Але так само знайдеться людина, яка сама себе не любить. Тоді таке відношення не рефлексивне — усі люди мали б любити самих себе.

Приклади симетричності

У симетричного відношення, якщо в ньому є якась пара, то є й обернена пара. Наприклад, відношення «бути братом чи сестрою». Якщо Іван — брат Яни, то й Яна — сестра Івана. З числових відношень це могло б бути відношення «бути протилежним числом». Маю на увазі пари 2 і −2 або −7 і 7. Це такі два числа, сума яких дорівнює нулю. Таке відношення симетричне, бо порядок просто не має значення: (2; −2) і (−2; 2) усе ще є парами взаємно протилежних чисел і в сумі дають нуль.

Відношення, що не є симетричним, — «менше ніж» (на множині дійсних чисел). Воно не має жодної симетричної пари, бо ніколи не може виконуватися a < b і водночас b < a. Якщо 5 < 15, то не може виконуватися 15 < 5. Не симетричне також відношення «бути батьком свого сина». Можна бути батьком свого сина, але тоді син уже не може бути батьком свого батька.

Ця властивість знову має виконуватися для всіх випадків. Якщо відношення «любити когось» (на множині всіх людей) має бути симетричним, то коли я люблю, скажімо, відому телеведучу Оксану, то водночас і Оксана мала б любити мене. А оскільки вона мене навіть не знає, не можу сказати, що вона мене любить, а це шкода, і відношення не симетричне. Що теж шкода.

Приклади антисиметричності

Класичний приклад антисиметричного відношення — «менше або дорівнює». Антисиметричність каже нам: якщо елементи (a; b) і (b; a) належать відношенню, то лише тоді, коли вони рівні, a = b. Відношення «менше або дорівнює» це задовольняє. Коли виконується a ≤ b і водночас b ≤ a? Лише тоді, коли a = b. Якщо підставимо: чи виконується 3 ≤ 5 і водночас 5 ≤ 3? Ні. Але виконується 4 ≤ 4 і водночас 4 ≤ 4.

Прикладом відношення, що не є антисиметричним, можуть бути пари слів однакової довжини, наприклад $(\text{субота}; \text{сокира})$. Таке відношення не антисиметричне, бо ми знаходимо пару слів, що перебувають у відношенні, їхня обернена пара теж у відношенні, а проте обидва слова різні. Отже, уже згадана пара $(\text{субота}; \text{сокира})$ та її обернена: $(\text{сокира}; \text{субота})$. Обидві, очевидно, у нашому відношенні, але водночас $\text{субота} \ne \text{сокира}$, тож відношення не антисиметричне.

Приклад транзитивності

Транзитивним є відношення «менше ніж». Транзитивність каже нам, що якщо 3 < 4 і водночас 4 < 5, то безперечно має виконуватися й 3 < 5. Для багатьох відношень це досить природна властивість. Подібно й для прикладу з однаковою довжиною слів. Якщо у відношенні перебувають пари $(\text{сокира}; \text{субота})$ і $(\text{субота}; \text{поліно})$, то у відношенні перебувають і слова $(\text{сокира}; \text{поліно})$.

Не є транзитивним відношення «бути батьком сина». Якщо Антон — батько Федора, а Федір — батько Мирона, то Антон не є батьком Мирона, він його дід. Так само не є транзитивним відношення «любити когось». Якщо я люблю Оксану, а Оксана любить свого чоловіка, то це не означає, що і я люблю Оксаниного чоловіка.

Транзитивність досліджують і для звичайних ігрових кубиків. Розгляньмо відношення «кубик A кращий за кубик B», якщо на кубику A частіше (з більшою ймовірністю) випадає більше число, ніж на кубику B. Чи транзитивне таке відношення? На це відповідає стаття про нетранзитивні кубики.

Еквівалентність і порядок

Деякі особливі типи бінарних відношень мають і власні назви:

• Еквівалентність — відношення, яке є рефлексивним, симетричним і транзитивним.
• Порядок — відношення, яке є рефлексивним, антисиметричним і транзитивним.