Бінарні відношення та їх властивості

📌 Про що ця тема

Бінарні відношення описують звʼязки між елементами множин: «менше», «ділиться на», «дружить з» тощо. На іспиті перевіряють уміння визначати властивості відношення (рефлексивність, симетричність, транзитивність) і впізнавати спеціальні типи — відношення еквівалентності та порядку. Ключове поняття — впорядкована пара.

📖 Головне

• Бінарне відношення R на множині A — це будь-яка підмножина декартового добутку A×A, тобто набір упорядкованих пар (a, b). Запис aRb означає «пара (a, b) належить R».

• Декартів добуток A×B — множина всіх пар (a, b), де a∈A, b∈B. Якщо |A|=n, то на A існує 2^(n²) різних відношень.

• Способи задання: перелік пар, матриця суміжності (клітина [i][j]=1, якщо aᵢRaⱼ), граф (вершини — елементи, дуги — пари), словесне правило.

• Рефлексивність: для кожного a виконується aRa. Усі пари (a, a) є в R. На матриці — уся головна діагональ = 1.

• Антирефлексивність: жодне aRa не виконується. Діагональ матриці вся = 0.

• Симетричність: якщо aRb, то й bRa. Матриця симетрична відносно діагоналі.

• Антисиметричність: якщо aRb і bRa одночасно, то a=b (різні елементи не повʼязані в обидва боки).

• Транзитивність: якщо aRb і bRc, то aRc. «Ланцюжок» замикається.

• Відношення еквівалентності — одночасно рефлексивне, симетричне і транзитивне. Воно розбиває множину на класи еквівалентності (приклад: рівність, «дає однаковий остачу при діленні»).

• Відношення часткового порядку — рефлексивне, антисиметричне і транзитивне (приклад: «≤», «ділиться на», «⊆»).

🔢 Як це працює на прикладі

Нехай A={1,2,3}, R — відношення «ділиться на» (aRb, якщо a ділиться на b).

Пари: (1,1),(2,2),(3,3),(2,1),(3,1). Перевіряємо:

• Рефлексивність: кожне число ділиться само на себе → (1,1),(2,2),(3,3) є → ТАК.

• Антисиметричність: немає різних a,b, де водночас aRb і bRa → ТАК.

• Транзитивність: якщо a ділиться на b і b на c, то a ділиться на c → ТАК.

Висновок: це відношення часткового порядку.

Другий приклад: R={(1,2),(2,1),(1,1),(2,2)} на A={1,2,3}.

Рефлексивність: немає (3,3) → НІ. Симетричність: (1,2) і (2,1) є → ТАК. Отже еквівалентністю бути не може без рефлексивності.

⚠️ Типові помилки

• Плутають симетричність і антисиметричність: антисиметричність НЕ означає «несиметричність», вона допускає пари (a, a).

• Вважають, що відсутність рефлексивності = антирефлексивність. Це різне: може не бути ні тим, ні іншим (одна діагональна пара є, інша ні).

• Перевіряють транзитивність лише на одній парі; треба перевірити ВСІ можливі ланцюжки aRb, bRc.

• Забувають, що для рефлексивності потрібні пари (a, a) для КОЖНОГО елемента множини, а не лише для деяких.

• Плутають A×A і саме відношення: добуток — усі пари, R — обрана підмножина.

🎯 Що завчити напамʼять

• Еквівалентність = рефлексивне + симетричне + транзитивне.

• Частковий порядок = рефлексивне + антисиметричне + транзитивне.

• Рефлексивність — уся діагональ матриці 1; симетричність — матриця симетрична.

• Кількість відношень на множині з n елементів: 2^(n²).

🧠 Перевір себе

1. Чи є відношення «<» на числах рефлексивним?

2. Якими трьома властивостями має володіти відношення еквівалентності?

3. Відношення «≤» — це еквівалентність чи порядок?

4. Скільки бінарних відношень можна задати на множині з 2 елементів?

Відповіді: 1 — ні (жодне a<a), це антирефлексивне; 2 — рефлексивність, симетричність, транзитивність; 3 — частковий порядок; 4 — 2^(2²)=2^4=16.