# 2. Методичні вказівки

Цей розділ **самодостатній**: у ньому зібрано всю теорію, потрібну для теми —
бінарні відношення, їхні способи запису, область визначення й значень,
властивості, типи та функціональність, — разом із прийомами, якими виконують
завдання з [3task.md](3task.md). Наприкінці наведено **один повністю розв'язаний
демонстраційний приклад** на відношенні, якого немає серед варіантів: він показує
техніку, не розв'язуючи жодного з ваших завдань. Теоретичне підґрунтя — [Лекція 2.
Відношення](../../Lectures/ODM-L02.md) (яка, своєю чергою, спирається на алгебру
множин з [Лекції 1](../../Lectures/ODM-L01.md)).

## 2.1 Що таке відношення

Почнемо з будівельного матеріалу. **Упорядкована пара** $(x, y)$ — це два об'єкти,
взяті в певному порядку; на відміну від множини $\{x, y\}$, тут порядок суттєвий:
$(1, 2) \ne (2, 1)$. **Декартів добуток** двох множин — це множина всіх таких пар:

$$
A \times B = \{\, (x, y) \mid x \in A,\ y \in B \,\}.
$$

Якщо $|A| = m$ і $|B| = n$, то $|A \times B| = m \cdot n$.

> **Означення (бінарне відношення).** **Бінарне відношення** $R$ з множини $A$ у
> множину $B$ — це будь-яка **підмножина декартового добутку**:
> $$ R \subseteq A \times B. $$
> Якщо $(x, y) \in R$, кажуть «$x$ перебуває у відношенні $R$ до $y$» й пишуть
> $x\,R\,y$; якщо ж $(x, y) \notin R$, кажуть, що $x$ не перебуває у відношенні
> $R$ до $y$.

Найчастіше обидві множини збігаються — тоді говорять про **відношення на множині**
$A$, тобто підмножину $A \times A$. Саме такі відношення досліджують у цій роботі.
Оскільки $A \times A$ містить $|A|^2$ пар, а відношення — це будь-яка їх підмножина,
різних відношень на $A$ рівно стільки, скільки підмножин у $|A|^2$-елементної
множини.

> **Твердження 2.1.** На скінченній множині $A$ з $|A| = n$ елементів існує рівно
> $2^{\,n^{2}}$ різних бінарних відношень.
>
> *Доведення.* Відношення — це підмножина множини $A \times A$, а
> $|A \times A| = n^{2}$. Кількість підмножин $k$-елементної множини дорівнює
> $2^{k}$ (множина-ступінь, [Лекція 1](../../Lectures/ODM-L01.md)). Підставивши
> $k = n^{2}$, дістаємо $2^{\,n^{2}}$. $\blacksquare$

### Способи задання відношення

Як і будь-яку множину, відношення задають **переліком** його пар або
**характеристичною властивістю** (предикатом):

$$
R = \{\, (x, y) \mid x, y \in A,\ P(x, y) \,\},
$$

де $P(x, y)$ — умова, якій мають задовольняти пари. Наприклад,
$R = \{(x, y) \mid x, y \in A,\ x < y\}$ добирає всі пари, у яких перший елемент
менший за другий. Саме предикатом задано відношення у ваших варіантах.

> **Зауваження (подільність цілих чисел).** У кількох варіантах трапляється предикат
> «$x$ ділить $y$ націло», який позначають $x \mid y$. За означенням $x \mid y$
> істинне, якщо існує ціле $k$ таке, що $y = k \cdot x$. Пам'ятайте про межові
> випадки: будь-яке ненульове $x$ ділить $0$ (бо $0 = 0 \cdot x$), а $0$ ділить лише
> само $0$; знак не заважає подільності (наприклад, $-3 \mid 6$, бо $6 = (-2)\cdot(-3)$).
> Ці тонкощі важливі, коли множина містить $0$ та від'ємні числа.

### Три особливі відношення

На кожній множині $A$ виокремлюють три «крайні» відношення, з якими корисно
порівнювати своє:

| Назва | Означення | Матриця |
|---|---|---|
| **Повне** (універсальне) | $R = A \times A$ — пов'язані **всі** пари | уся матриця з одиниць |
| **Порожнє** | $R = \varnothing$ — не пов'язана **жодна** пара | уся матриця з нулів |
| **Тотожнє** (діагональ $\Delta$) | $R = \{(a, a) \mid a \in A\}$ — кожен елемент лише сам із собою | одиниці лише на головній діагоналі |

## 2.2 Область визначення й область значень

Дивлячись на відношення $R \subseteq A \times A$ як на набір «стрілок» $x \to y$,
природно запитати: з яких елементів стрілки **виходять** і в які **входять**.

> **Означення (область визначення та значень).**
> **Область визначення** $D(R)$ — множина перших координат усіх пар відношення:
> $$ D(R) = \{\, x \mid \exists\, y\ (x, y) \in R \,\}. $$
> **Область значень** $E(R)$ — множина других координат:
> $$ E(R) = \{\, y \mid \exists\, x\ (x, y) \in R \,\}. $$

Простими словами: $D(R)$ — це ті $x$, для яких знайдеться хоч один партнер $y$;
$E(R)$ — ті $y$, які є партнером хоч для якого $x$. Обидві множини — підмножини
$A$, і кожна може бути як усією множиною $A$, так і власною її частиною.

**Приклад 2.2 (обидві області — уся множина).** Нехай на $\mathbb{Z}$ відношення
задано умовою «$x$ і $y$ мають однакову парність». Кожне ціле $x$ має однакову
парність із собою, тому пара $(x, x)$ належить відношенню — отже, кожне $x$ бере
участь, і $D(R) = \mathbb{Z}$. З тієї самої причини кожне ціле є чиєюсь другою
координатою, тож $E(R) = \mathbb{Z}$.

**Приклад 2.3 (область значень — власна підмножина).** Нехай на $\mathbb{Z}$
відношення задано умовою $y = x^{2}$. Будь-яке ціле можна піднести до квадрата, тож
$D(R) = \mathbb{Z}$. Але другими координатами бувають лише повні квадрати, тому
$$ E(R) = \{\, 0, 1, 4, 9, 16, \dots \,\} \subsetneq \mathbb{Z}. $$
Знаходячи область значень, завжди питайте себе: *які значення $y$ взагалі
досяжні?* — а не просто переписуйте всю множину $A$.

## 2.3 Три способи запису відношення

Те саме відношення можна записати трьома рівносильними способами; завдання може
вимагати будь-якого з них, тож треба вміти переходити між ними.

- **Перелік упорядкованих пар** — просто виписують усі пари $R$, наприклад
  $R = \{(1, 2), (2, 3), (1, 3)\}$.
- **Булева (характеристична) матриця** $M_R$ — таблиця розміру $|A| \times |A|$, у
  якій рядки відповідають першому елементу пари («звідки»), стовпці — другому
  («куди»), а на перетині ставлять $M_{xy} = 1$, якщо $(x, y) \in R$, і $M_{xy} = 0$
  інакше. Рядки й стовпці впорядковують однаково (звичайно зростанням елементів).
- **Орієнтований граф (орграф)** — для кожного елемента $A$ малюють вершину, а для
  кожної пари $(x, y) \in R$ проводять **дугу** (стрілку) $x \to y$. Пара виду
  $(a, a)$ дає **петлю** — дугу з вершини в саму себе.

Перехід очевидний: рядок матриці з одиницями в стовпцях $y_1, y_2, \dots$ — це
вершина, з якої виходять дуги в $y_1, y_2, \dots$; симетрична матриця відповідає
орграфу, у якому кожна дуга має зворотну, і так далі. Конкретні матрицю та орграф
одного відношення побудовано в демонстраційному прикладі (§2.7).

## 2.4 Властивості відношень

Нехай $R$ — відношення на множині $A$. Нижче зібрано властивості, які треба вміти
перевіряти, разом із тим, як кожна з них **виглядає в орграфі та в матриці**.

| Властивість | Означення | В орграфі | У матриці $M_R$ |
|---|---|---|---|
| **Рефлексивність** | $(a, a) \in R$ для **кожного** $a \in A$ | петля в **кожній** вершині | уся головна діагональ — одиниці |
| **Антирефлексивність** | $(a, a) \notin R$ для **кожного** $a \in A$ | **жодної** петлі | уся діагональ — нулі |
| **Симетричність** | $(a, b) \in R \Rightarrow (b, a) \in R$ | кожна дуга має зворотну | матриця симетрична: $M_{ab} = M_{ba}$ |
| **Антисиметричність** | $(a, b) \in R$ і $(b, a) \in R \Rightarrow a = b$ | немає двох **різних** вершин, з'єднаних в обидва боки | немає $a \ne b$ з $M_{ab} = M_{ba} = 1$ |
| **Асиметричність** | $(a, b) \in R \Rightarrow (b, a) \notin R$ | немає зворотних дуг **і** немає петель | нульова діагональ **і** немає дзеркальних одиниць |
| **Транзитивність** | $(a, b), (b, c) \in R \Rightarrow (a, c) \in R$ | кожен шлях $a \to b \to c$ має скорочення $a \to c$ | одиниці булевого $M_R^{2}$ уже стоять і в $M_R$ |
| **Антитранзитивність** | $(a, b), (b, c) \in R \Rightarrow (a, c) \notin R$ | **жоден** шлях $a \to b \to c$ не має скорочення | де $M_R^{2}$ має одиницю, там $M_R$ має нуль |

![Чотири властивості на маленьких орграфах: рефлексивність (петлі), симетричність (зворотні дуги), антисиметричність (без зустрічних дуг), транзитивність (скорочення шляху)](img/p2_properties.png)

Три застереження, які вирішують більшість помилок:

> **Типова помилка (рефлексивність проти антирефлексивності).** Це **не**
> протилежні властивості. Відношення може бути **ні рефлексивним, ні
> антирефлексивним** — досить, щоб петля була в однієї вершини й не було в іншої.
> Скажімо, на $\{1, 2\}$ відношення $\{(1, 1)\}$ має петлю в $1$ (тож не
> антирефлексивне), але не має петлі в $2$ (тож не рефлексивне).

> **Типова помилка (антисиметричність — це не «несиметричність»).** Це різні умови.
> Тотожнє відношення $\Delta$ водночас **симетричне й антисиметричне**; багато
> відношень — **ні те, ні те**. Антисиметричність забороняє лише **двобічний
> зв'язок між різними елементами**; петля $(a, a)$ її ніколи не порушує. Сильніший
> родич — **асиметричність**.

> **Твердження 2.4 (асиметричність = антирефлексивність + антисиметричність).**
> Відношення $R$ асиметричне тоді й лише тоді, коли воно одночасно
> антирефлексивне й антисиметричне.
>
> *Доведення.* ($\Rightarrow$) Нехай $R$ асиметричне. Якби $(a, a) \in R$, то з
> означення $(a, a) \notin R$ — суперечність; отже, петель немає, тобто $R$
> антирефлексивне. Далі, ситуація «$(a, b) \in R$ і водночас $(b, a) \in R$»
> неможлива: перша належність за асиметричністю дає $(b, a) \notin R$, що суперечить
> другій. Отже, передумова антисиметричності ніколи не справджується, і сама
> антисиметричність виконана порожньо-істинно. ($\Leftarrow$) Нехай $R$
> антирефлексивне й
> антисиметричне, і хай $(a, b) \in R$. Якби ще й $(b, a) \in R$, то з
> антисиметричності $a = b$, а тоді $(a, a) \in R$ суперечить антирефлексивності.
> Отже, $(b, a) \notin R$, тобто $R$ асиметричне. $\blacksquare$

> **Порада (як спростувати властивість).** Щоб довести, що властивості **немає**,
> достатньо одного конкретного **свідка**. Наприклад: «не транзитивне, бо
> $(1, 2), (2, 3) \in R$, але $(1, 3) \notin R$». Одна така пара вагоміша за будь-які
> загальні міркування.

## 2.5 Типи відношень

Певні поєднання властивостей настільки важливі, що дістали власні назви. У курсі
розглядають три типи:

| Тип | Означальні властивості | Що моделює |
|---|---|---|
| **Еквівалентності** | рефлексивне + симетричне + **транзитивне** | «однаковість»; розбиває $A$ на класи |
| **Часткового порядку** | рефлексивне + **антисиметричне** + транзитивне | узгоджене «$\le$»; деякі елементи непорівнянні |
| **Толерантності** | рефлексивне + симетричне (**без** транзитивності) | «схожість, близькість» |

- **Відношення еквівалентності** моделює поняття «бути таким самим» і розбиває
  множину $A$ на неперетинні **класи еквівалентності** (**розбиття**): кожен елемент
  потрапляє рівно в один клас пов'язаних із ним елементів. Приклади: рівність,
  «однакова парність», «однакова остача при діленні на $n$».
- **Відношення часткового порядку** моделює несуперечливе «менше або дорівнює», у
  якому деякі пари елементів можуть бути **непорівнянними**. Приклади: $\le$ на
  числах, включення $\subseteq$ на множинах, подільність на натуральних числах.
- **Відношення толерантності** моделює «схожість»: воно рефлексивне й симетричне,
  але транзитивності не вимагає (близьке до близького не конче близьке до
  далекого). Приклад: «$|x - y| \le 1$» на цілих числах.

> **Зауваження (толерантність і транзитивність).** У слайдах курсу відношення
> толерантності характеризують як рефлексивне, симетричне та **антитранзитивне**.
> Класичне означення вимагає лише рефлексивності й симетричності; головне —
> **відсутність обов'язкової транзитивності**, і саме це відрізняє толерантність від
> еквівалентності. Тому, визначаючи тип, спершу перевірте транзитивність: є вона
> (разом із рефлексивністю й симетричністю) — маєте еквівалентність; немає — це радше
> толерантність.

Розпізнати тип — означає просто перевірити три означальні властивості й назвати
результат. Одне відношення може не належати до жодного з типів.

## 2.6 Функціональні відношення

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

> **Означення (функціональне відношення).** Відношення $R \subseteq A \times B$
> називають **функціональним**, якщо кожному $x$ відповідає **не більш ніж один**
> $y$ такий, що $(x, y) \in R$: з $(x, y_1) \in R$ і $(x, y_2) \in R$ випливає
> $y_1 = y_2$.

Ознака у двох записах читається миттєво:

- **у матриці** — у кожному рядку **не більше однієї одиниці**;
- **в орграфі** — з кожної вершини виходить **не більше однієї дуги**.

![Ліворуч функціональне відношення (з кожного x — не більше однієї стрілки), праворуч не функціональне (з x1 виходять дві стрілки)](img/p2_functional.png)

Функціональне відношення задає (частково визначену) **функцію**: для кожного
$x \in D(R)$ існує єдине значення, яке позначають $y = f(x)$. Якщо до того ж область
визначення — уся множина $A$ (тобто кожному $x \in A$ відповідає **рівно один** $y$),
маємо **всюди визначену функцію**, або **відображення** $f\colon A \to B$.

**Приклад 2.5.** Відношення «$y = x^{2}$» на $\mathbb{Z}$ (Приклад 2.3) —
функціональне: кожному $x$ відповідає єдиний квадрат $x^{2}$. Натомість
відношення «однакова парність» (Приклад 2.2) **не** функціональне: наприклад,
з $1$ пов'язані і $1$, і $3$ (та й усі непарні), тобто $x = 1$ має багато партнерів.

> **Зауваження (відображення: сюр'єкція, ін'єкція, бієкція).** Для відображення
> $f\colon A \to B$ розрізняють: **сюр'єктивне** — коли область значень збігається з
> усім $B$ (кожен $y$ досяжний); **ін'єктивне** — коли різним $x$ відповідають різні
> $y$; **бієктивне** — коли воно водночас сюр'єктивне й ін'єктивне (взаємно однозначна
> відповідність). Детальніше — у [Лекції 2](../../Lectures/ODM-L02.md); для цієї
> роботи достатньо вміти відрізняти функціональне відношення від нефункціонального.

## 2.7 Демонстраційний приклад (з повним розв'язанням)

> **Увага.** Це відношення **не збігається** з жодним варіантом — воно лише показує
> послідовність дій. Своє відношення досліджуйте самостійно за тією самою схемою.

**Умова.** Розгляньмо відношення $S$ на множині $A = \{1, 2, 3, 4\}$, задане
предикатом
$$ x\,S\,y \iff x \text{ і } y \text{ мають однакову парність} \quad (x \equiv y \ (\mathrm{mod}\ 2)). $$
Запишемо $S$ трьома способами, знайдемо його області, властивості й тип та
перевіримо функціональність. (Для ілюстрації першого завдання окремо розгляньмо
$S$ ще й на всій множині $\mathbb{Z}$.)

**Крок 1. Перелік пар.** Непарні елементи $A$ — це $\{1, 3\}$, парні — $\{2, 4\}$.
Пов'язані рівно ті пари, обидва елементи яких з одного класу:
$$
S = \{(1,1),\ (1,3),\ (3,1),\ (3,3),\ (2,2),\ (2,4),\ (4,2),\ (4,4)\}, \qquad |S| = 8.
$$

**Крок 2. Матриця.** Упорядкувавши рядки й стовпці як $1, 2, 3, 4$, ставимо одиницю
там, де пара належить $S$:

![Булева матриця відношення S: одиниці на перетинах елементів однакової парності](img/p2_matrix.png)

**Крок 3. Орграф.** Кожна вершина має петлю (бо всі пари $(a, a)$ належать $S$), а
між $1$ і $3$ та між $2$ і $4$ проведено дуги в обидва боки:

![Орграф відношення S: петлі в усіх вершинах, двобічні дуги 1–3 та 2–4](img/p2_digraph.png)

**Крок 4. Області.** На множині $A$ у переліку трапляються всі елементи як перші й
як другі координати, тож $D(S) = E(S) = \{1, 2, 3, 4\}$. На множині $\mathbb{Z}$
кожне ціле однакової парності із собою, тому $D(S) = E(S) = \mathbb{Z}$ (пор.
Приклад 2.2).

**Крок 5. Властивості** (кожен висновок — з обґрунтуванням):

- **Рефлексивність** — так: для кожного $a$ пара $(a, a) \in S$, бо $a$ однакової
  парності із собою (діагональ матриці — самі одиниці).
- **Антирефлексивність** — ні: петлі є (наприклад, $(1, 1) \in S$).
- **Симетричність** — так: якщо $x$ і $y$ однакової парності, то й $y$ та $x$;
  матриця симетрична.
- **Антисиметричність** — ні: свідок — $(1, 3) \in S$ і $(3, 1) \in S$, але
  $1 \ne 3$.
- **Асиметричність** — ні: уже наявність петель (або пари $(1,3)$ разом із $(3,1)$)
  її виключає.
- **Транзитивність** — так: якщо $x, y$ однакової парності й $y, z$ однакової
  парності, то $x, z$ теж однакової парності.
- **Антитранзитивність** — ні: свідок — $(1, 3), (3, 1) \in S$, і скорочення
  $(1, 1) \in S$ існує.

**Крок 6. Тип.** Відношення рефлексивне, симетричне й транзитивне — отже, це
**відношення еквівалентності**. Його класи еквівалентності —
$\{1, 3\}$ (непарні) і $\{2, 4\}$ (парні); вони утворюють розбиття множини $A$.

**Крок 7. Функціональність.** Відношення $S$ **не є функціональним**: у рядку
$x = 1$ матриці стоять дві одиниці — пари $(1, 1)$ і $(1, 3)$, — тобто елементу
$x = 1$ відповідають два різні $y$ ($1$ і $3$). В орграфі це видно як дві дуги, що
виходять із вершини $1$. (Для порівняння: відношення «$y = x^2$» з Прикладу 2.5
було б функціональним.)

## 2.8 Робочий алгоритм

Виконуючи своє завдання, дотримуйтесь тієї самої послідовності:

1. **Область визначення й значень (на $\mathbb{Z}$).** З'ясуйте, які $x$ мають хоч
   одного партнера ($D(R)$) і які $y$ є партнером хоч для якого $x$ ($E(R)$).
   Перевірте, чи не є котрась із областей **власною** підмножиною $\mathbb{Z}$.
2. **Перелік пар (на $A = \{-5, \dots, 5\}$).** Акуратно переберіть усі пари, що
   задовольняють предикат; не забудьте про $0$ та від'ємні числа.
3. **Матриця** $11 \times 11$ і **орграф** — побудуйте обидва й звірте з переліком.
4. **Властивості** — перевіряйте **по одній**; кожне «так» доведіть для всіх пар,
   кожне «ні» — конкретним свідком.
5. **Тип** — назвіть його за трьома означальними властивостями (або поясніть, чому
   відношення не належить до жодного типу).
6. **Функціональність** — подивіться, чи немає рядка матриці (вершини орграфа) з
   більш ніж однією одиницею (вихідною дугою); поясніть висновок.