# Лекція 2. Алгебра відношень

## Огляд

Множини, які ми вивчали в [Лекції 1](ODM-L01.md), описують *сукупності* об'єктів. Проте
майже кожне змістовне твердження математики чи інформатики стосується не окремих
об'єктів, а **зв'язків** між ними: «$x$ менше за $y$», «студент $s$ отримав оцінку $m$
з предмета $j$», «шрифт містить гліф $g$», «сторінка $u$ посилається на сторінку $v$»,
«операцію $p$ треба виконати перед операцією $q$». Математичний об'єкт, що вловлює саме
ідею *зв'язку* між елементами, — це **відношення** (англ. *relation*). Не більше й не
менше.

Уся тема виростає з одного скромного поняття з попередньої лекції — **упорядкованої
пари** $(a, b)$. На відміну від множини $\{a, b\}$, пара пам'ятає не лише *які* два
об'єкти беруть участь, а й *котрий іде першим*. Відношення — це просто *множина таких
пар*, вибрана з декартового добутку. Усе інше в цьому розділі — матриці, орграфи, класи
еквівалентності, порядки, таблиці баз даних — випливає з того, що ми серйозно
поставимося до цього означення.

Три наскрізні мотиви проходять крізь усю лекцію:

- **Один об'єкт — три обличчя.** Одне й те саме відношення можна подати як *множину
  пар*, як *булеву матрицю* і як *орієнтований граф*. Кожне з облич робить певні
  запитання очевидними: матриця перетворює «чи є двокроковий шлях?» на арифметику,
  граф робить досяжність видимою, а перелік пар робить прозорими операції над
  множинами.
- **Структура через властивості.** Жменька властивостей (рефлексивність,
  симетричність, транзитивність, …) виокремлює два найважливіші види відношень:
  **еквівалентності**, що формалізують «однакове для наших потреб», і **часткові
  порядки**, що формалізують «упорядкування, у якому дещо може лишатися непорівнянним».
- **Від теорії до систем.** Узагальнення до $n$-арних відношень — не забаганка: це
  буквально модель даних кожної реляційної бази даних, а операції над множинами з
  Лекції 1 знову з'являються як ядро реляційної алгебри й, отже, мови SQL.

> **Про позначення й строгість.** Кілька результатів нижче оформлені як **леми**,
> **твердження** чи **теореми** й супроводжуються доведенням між позначками
> *Доведення.* … $\blacksquare$. Читайте доведення активно: більшість із них — це
> акуратний перебір випадків або застосування логічної форми означення. **Означення**
> ми виділяємо жирним терміном, а нумеровані приклади й твердження нумеруємо наскрізно
> в межах лекції (Приклад 2.$m$, Теорема 2.$m$).

---

## 2.1 Кортежі та декартів добуток

### Мотивація: коли порядок має значення

Множина «сліпа» до порядку й повторень: $\{1, 2\} = \{2, 1\}$ і $\{a, a\} = \{a\}$. Але
щоб записати, що *«Косач склав Дизайн прототипів на A»*, нам потрібен об'єкт, у якому
порядок компонент **істотний**: перша компонента — студент, друга — предмет, третя —
оцінка, і їх не можна переставляти. Таким об'єктом є кортеж.

> **Означення (кортеж, упорядкована пара).** **Кортеж** (упорядкований набір) довжини
> $n$ — це послідовність $(a_1, a_2, \dots, a_n)$ з $n$ компонент, у якій **порядок
> істотний**, а **повторення дозволені**. Кортеж довжини $2$ називають
> **упорядкованою парою** $(a, b)$, довжини $3$ — **трійкою** тощо. Два кортежі рівні
> тоді й лише тоді, коли рівні їхні відповідні компоненти:
> $$ (a_1, \dots, a_n) = (b_1, \dots, b_n) \;\iff\; a_1 = b_1,\ \dots,\ a_n = b_n. $$

Саме критерій рівності відрізняє кортеж від множини. Для пари він означає:
$$ (a, b) = (c, d) \;\iff\; a = c \ \text{і}\ b = d. $$

> **Історична довідка.** Хоч упорядковану пару зручно вважати первісним поняттям, її
> можна означити *суто через множини* формулою Куратовського
> $(a, b) := \{\{a\}, \{a, b\}\}$. З цього означення критерій рівності пар доводять як
> теорему. Отже, відношення (а з ними — функції, графи, бази даних) остаточно зводяться
> до мови множин Лекції 1.

### Декартів добуток

> **Означення (декартів добуток).** **Декартів (прямий) добуток** множин $A$ і $B$ —
> це множина **всіх** упорядкованих пар, перша компонента яких належить $A$, а друга —
> $B$:
> $$ A \times B = \{\, (a, b) \mid a \in A,\ b \in B \,\}. $$
> Аналогічно для кількох множників $A \times B \times C = \{\, (a, b, c) \mid a \in A,\
> b \in B,\ c \in C \,\}$, і взагалі $A_1 \times \dots \times A_n$. Добуток $A \times A$
> скорочено позначають $A^2$.

Для скінченних множин розмір добутку дає **правило добутку**:
$$ |A \times B \times C| = |A| \cdot |B| \cdot |C|. $$
Це елементарний, але наріжний факт комбінаторики (докладніше — у відповідній лекції про
комбінаторику).

**Приклад 2.1 (декартів добуток трьох множин).** Нехай $A = \{1, 2, 3\}$, $B = \{4, 5\}$,
$C = \{6, 7\}$. Тоді $|A \times B \times C| = 3 \cdot 2 \cdot 2 = 12$, і повний перелік
трійок такий:
$$
\begin{aligned}
A \times B \times C = \{\ &(1,4,6),(1,4,7),(1,5,6),(1,5,7),\\
&(2,4,6),(2,4,7),(2,5,6),(2,5,7),\\
&(3,4,6),(3,4,7),(3,5,6),(3,5,7)\ \}.
\end{aligned}
$$
Зручно уявляти це як систематичний перебір: фіксуємо першу компоненту, потім другу,
потім третю. Декартів добуток — це «всесвіт» усіх мислимих кортежів; відношення (§2.2)
вибирає з нього лише ті, що нас справді цікавлять.

> **Зауваження (порядок і повторення істотні).** Пара $(2, 5)$ — це *не* пара $(5, 2)$,
> а $(3, 3)$ — цілком законна пара, хоча множина $\{3, 3\} = \{3\}$ «злипається». Саме
> тому відношення здатні виражати несиметричні зв'язки на кшталт «$x$ є батьком $y$»,
> яких симетрична двоелементна множина ніколи не змогла б записати. Загалом
> $A \times B \ne B \times A$ (якщо $A \ne B$).

> **Типова помилка (кортеж проти множини).** Не плутайте $(a, b)$ з $\{a, b\}$.
> По-перше, $(a, b) = (b, a)$ **лише** коли $a = b$, тоді як $\{a, b\} = \{b, a\}$
> завжди. По-друге, дужки різні: круглі — для кортежів, фігурні — для множин. Порожньої
> «пари» не буває, а порожня множина $\varnothing$ — буває.

---

## 2.2 Відношення як підмножина декартового добутку

Тепер головне означення лекції.

> **Означення (бінарне відношення).** **Бінарним відношенням** $R$ *з* множини $A$ *у*
> множину $B$ називають будь-яку підмножину декартового добутку: $R \subseteq A \times
> B$. Якщо $A = B$, кажуть, що $R$ — **відношення на** $A$ (тоді $R \subseteq A \times
> A$). Елементи $R$ — це впорядковані пари $(a, b)$.

Два записи означають абсолютно те саме:
$$ (a, b) \in R \qquad\Longleftrightarrow\qquad a\,R\,b, $$
і читають їх «$a$ перебуває у відношенні $R$ з $b$». Вони взаємозамінні, бо $R$ *і є*
своєю множиною пар: інфіксний запис $a\,R\,b$ — лише зручне скорочення для належності
$(a, b) \in R$. Інфіксна форма наслідує звичні $a \le b$ чи $a = b$ і зазвичай читабельніша.

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

Як і множину (Лекція 1), відношення задають двома стандартними способами:

1. **Переліком** пар (екстенсіонально) — коли пар небагато;
2. **Предикатом** (інтенсіонально) — характеристичною властивістю $P(x, y)$, якій мають
   задовольняти пари: $R = \{\, (x, y) \mid P(x, y) \,\}$.

**Приклад 2.2 (одне відношення — два записи).** Нехай $A = B = \{1, 2, 3, 4\}$, а $R$ —
відношення «строго менше». Переліком:
$$ R = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}; $$
предикатом:
$$ R = \{\, (x, y) \mid x \in A,\ y \in B,\ x < y \,\}. $$
Обидва записи описують ті самі шість пар. Перевага предикатної форми — вона працює й
для нескінченних множин (відношення $<$ на $\mathbb{Z}$), де перелік неможливий.

**Приклад 2.3 ($n$-арне відношення: навчальні записи).** Відношення бувають не лише
бінарними. Нехай
$$
\text{СТУДЕНТИ} = \{\text{Шевченко}, \text{Франко}, \text{Косач}\},
$$
$$
\text{ПРЕДМЕТИ} = \{\text{Основи дискретної математики}, \text{Інформатика}, \text{Дизайн прототипів}\},
$$
$$
\text{ОЦІНКИ} = \{A, B, C, D, E, F, Fx\}.
$$
Екзаменаційний протокол — це **тернарне** (тримісне) відношення
$R \subseteq \text{СТУДЕНТИ} \times \text{ПРЕДМЕТИ} \times \text{ОЦІНКИ}$, наприклад
$$
R = \{\ (\text{Шевченко}, \text{Інформатика}, B),\ (\text{Косач}, \text{Дизайн прототипів}, A),\ (\text{Франко}, \text{ОДМ}, E)\ \}.
$$
До цього прикладу ми повернемося в §2.9: це і є **таблиця бази даних**. Загальне
означення таке: **$n$-арним** (або **$n$-місним**) **відношенням** називають підмножину
$R \subseteq A_1 \times A_2 \times \dots \times A_n$.

> **Типова помилка (відношення — не обов'язково «формула»).** Відношення не мусить
> задаватися жодною акуратною формулою. На множині $\{1, 2, 3\}$ набір
> $\{(1,3),(3,1),(2,2)\}$ — цілком законне відношення, хоча жодна арифметична умова не
> виокремлює саме ці три пари. І навпаки: два *різні* предикати можуть задавати те саме
> відношення (наприклад, «$x < y$» і «$y - x$ — додатне ціле» на $\mathbb{Z}$).

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

> **Означення (область визначення й значень).** Для відношення $R \subseteq A \times B$
> **областю визначення** називають множину тих перших компонент, що справді
> зустрічаються:
> $$ \operatorname{dom}(R) = \{\, a \in A \mid \exists\, b \in B\ (a, b) \in R \,\}, $$
> а **областю значень** (образом) — множину других компонент:
> $$ \operatorname{ran}(R) = \{\, b \in B \mid \exists\, a \in A\ (a, b) \in R \,\}. $$

**Приклад 2.4.** Для відношення «строго менше» з Прикладу 2.2 маємо
$\operatorname{dom}(R) = \{1, 2, 3\}$ (число $4$ не менше за жодне в $A$) і
$\operatorname{ran}(R) = \{2, 3, 4\}$ (ніщо не менше за $1$). Обидві множини — підмножини
$A$; жодна не мусить збігатися з усім $A$.

---

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

Одне й те саме відношення на скінченній множині можна записати трьома взаємозамінними
способами; вдалий вибір часто перетворює складне на вигляд запитання на просте.

### Перелік пар

Найпряміший спосіб — виписати пари: $R = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$. Він
компактний для **розріджених** відношень (мало пар) і робить прозорими операції над
множинами ($\cup, \cap, \setminus$).

### Матриця відношення

> **Означення (матриця відношення).** Для відношення $R$ на скінченній множині
> $A = \{a_1, \dots, a_n\}$ **матрицею відношення** називають булеву (нуль-одиничну)
> таблицю $M_R = [m_{ij}]$ розміру $n \times n$, де
> $$ m_{ij} = \begin{cases} 1, & \text{якщо } a_i\,R\,a_j,\\ 0, & \text{інакше.} \end{cases} $$

Рядок індексовано першою компонентою, стовпець — другою. Для відношення «строго менше»
на $\{1, 2, 3, 4\}$ матриця така:

| $x \backslash y$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| **1** | 0 | 1 | 1 | 1 |
| **2** | 0 | 0 | 1 | 1 |
| **3** | 0 | 0 | 0 | 1 |
| **4** | 0 | 0 | 0 | 0 |

![Матриця відношення «строго менше» на множині {1,2,3,4}: у клітинці рядка i, стовпця j стоїть 1 саме тоді, коли i менше за j](img/l02_matrix.png)

Матрична форма ідеальна для перевірки структурних властивостей «на око» (§2.5): уся
інформація про відношення — це $n^2$ бітів, незалежно від того, скільки пар присутньо,
тож вона найзручніша для **щільних** відношень.

### Орієнтований граф (орграф)

> **Означення (орграф відношення).** Відношення $R$ на $A$ зображують **орієнтованим
> графом**: кожному елементу $A$ відповідає **вершина**, а кожній парі $(a, b) \in R$ —
> **дуга** (стрілка) $a \to b$. Пара $(a, a)$ дає **петлю** при вершині $a$.

![Відношення як орграф: по одній вершині на елемент, стрілка a→b для кожної пари (a,b) ∈ R і петля для пари (a,a)](img/l02_digraph.png)

Орграф робить *видимою* досяжність: щоб дізнатися, чи пов'язані елементи ланцюжком, ми
просто йдемо стрілками. Матриця відношення — це і є матриця суміжності цього орграфа.

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

**Приклад 2.5 (одне відношення — три обличчя).** Відношення
$R = \{(1,2),(1,4),(2,3),(3,3),(4,2)\}$ на $\{1, 2, 3, 4\}$ (саме його зображено орграфом
вище) має такі три записи. **Переліком** — як щойно виписано. **Матрицею:**

| $x \backslash y$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| **1** | 0 | 1 | 0 | 1 |
| **2** | 0 | 0 | 1 | 0 |
| **3** | 0 | 0 | 1 | 0 |
| **4** | 0 | 1 | 0 | 0 |

**Орграфом** — із петлею при вершині $3$ (бо $(3, 3) \in R$) та стрілками для решти
чотирьох пар. Усі три записи несуть однакову інформацію; переходити між ними треба вміти
вільно, бо кожен зручний для свого класу задач.

---

## 2.4 Особливі відношення

Три відношення трапляються так часто, що заслуговують на власні назви; усі три миттєво
впізнавані за матрицею.

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

![Три особливі відношення на {1,2,3,4} у матричній формі: повне (усі одиниці), пусте (усі нулі) й тотожне (одинична матриця)](img/l02_special.png)

Тотожне відношення $\Delta_A$ (його ще звуть **відношенням рівності**) стане в нагоді
постійно: саме через нього найкоротше формулюють рефлексивність і антисиметричність
(§2.5).

---

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

Далі всюди $R$ — відношення *на* одній множині $A$ (тобто $R \subseteq A \times A$).
Наведені властивості класифікують «поведінку» $R$; у кожної є чітке логічне означення й
**матрична ознака**, за якою її видно з таблиці.

> **Означення (властивості відношення).** Відношення $R$ на $A$ називають:
>
> - **рефлексивним**, якщо $\forall a \in A:\ a\,R\,a$. *Матрична ознака:* уся головна
>   діагональ складається з одиниць.
> - **антирефлексивним** (іррефлексивним), якщо $\forall a \in A:\ \neg(a\,R\,a)$.
>   *Матрична ознака:* уся головна діагональ складається з нулів.
> - **арефлексивним** (нерефлексивним), якщо воно не є ні рефлексивним, ні
>   антирефлексивним. *Матрична ознака:* діагональ **мішана** — є принаймні одна одиниця
>   ($\exists a:\ a\,R\,a$) і принаймні один нуль ($\exists b:\ \neg(b\,R\,b)$).
> - **симетричним**, якщо $\forall a, b:\ a\,R\,b \Rightarrow b\,R\,a$. *Матрична ознака:*
>   матриця симетрична, $M_R = M_R^{\mathsf{T}}$ (дзеркальна відносно діагоналі).
> - **антисиметричним**, якщо $\forall a, b:\ (a\,R\,b \wedge b\,R\,a) \Rightarrow a = b$.
>   *Матрична ознака:* немає жодної симетричної пари одиниць поза діагоналлю (тобто
>   $m_{ij} = m_{ji} = 1$ при $i \ne j$ неможливо).
> - **асиметричним**, якщо $\forall a, b:\ a\,R\,b \Rightarrow \neg(b\,R\,a)$. *Матрична
>   ознака:* нульова діагональ **і** немає симетричних пар одиниць.
> - **транзитивним**, якщо $\forall a, b, c:\ (a\,R\,b \wedge b\,R\,c) \Rightarrow a\,R\,c$.
>   *Матрична ознака:* усюди, де існує двокроковий шлях $a \to b \to c$, присутня й
>   пряма одиниця $a \to c$.
> - **антитранзитивним**, якщо $\forall a, b, c:\ (a\,R\,b \wedge b\,R\,c) \Rightarrow
>   \neg(a\,R\,c)$. *Матрична ознака:* там, де є двокроковий шлях $a \to b \to c$, прямої
>   одиниці $a \to c$ **немає** (напр. відношення «бути батьком»: дід не є батьком онука).

Щоб компактно записати ці ознаки алгебраїчно, введемо ще одне природне поняття.

> **Означення (обернене відношення).** **Оберненим** до $R \subseteq A \times A$
> називають відношення
> $$ R^{-1} = \{\, (b, a) \mid (a, b) \in R \,\}, $$
> тобто $b\,R^{-1}a \iff a\,R\,b$. У матричній формі $M_{R^{-1}} = M_R^{\mathsf{T}}$
> (транспонування), в орграфі — розворот кожної стрілки.

### Рефлексивність, симетричність, антисиметричність алгебраїчно

> **Теорема 2.6 (алгебраїчні характеризації).** Для відношення $R$ на $A$:
> 1. $R$ рефлексивне $\iff \Delta_A \subseteq R$;
> 2. $R$ симетричне $\iff R = R^{-1}$ (рівносильно $M_R = M_R^{\mathsf{T}}$);
> 3. $R$ антисиметричне $\iff R \cap R^{-1} \subseteq \Delta_A$.
>
> *Доведення.* **(1)** Включення $\Delta_A \subseteq R$ означає «$(a, a) \in R$ для
> кожного $a$», тобто $a\,R\,a$ для всіх $a$, — це рівно означення рефлексивності.
>
> **(2)** ($\Rightarrow$) Нехай $R$ симетричне й $(a, b) \in R^{-1}$. Тоді $(b, a) \in R$,
> звідки за симетричністю $(a, b) \in R$; отже, $R^{-1} \subseteq R$. Обернене включення
> $R \subseteq R^{-1}$ доводиться симетрично (міняємо ролі $a$ й $b$), тож $R = R^{-1}$.
> ($\Leftarrow$) Нехай $R = R^{-1}$ і $a\,R\,b$. Тоді $(a, b) \in R = R^{-1}$, а це за
> означенням оберненого означає $(b, a) \in R$, тобто $b\,R\,a$; отже, $R$ симетричне.
>
> **(3)** ($\Rightarrow$) Нехай $R$ антисиметричне й $(a, b) \in R \cap R^{-1}$. Тоді
> $(a, b) \in R$ (тобто $a\,R\,b$) і $(a, b) \in R^{-1}$ (тобто $b\,R\,a$); за
> антисиметричністю $a = b$, отже $(a, b) \in \Delta_A$. ($\Leftarrow$) Нехай
> $R \cap R^{-1} \subseteq \Delta_A$ і водночас $a\,R\,b$ та $b\,R\,a$. Тоді
> $(a, b) \in R$ і $(a, b) \in R^{-1}$, звідки $(a, b) \in R \cap R^{-1} \subseteq
> \Delta_A$, а це й означає $a = b$. $\blacksquare$

### Асиметричність = антирефлексивність + антисиметричність

Асиметричність на перший погляд схожа на антисиметричність, але вона строго сильніша.
Наступне твердження показує, як саме.

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

Класичний асиметричний приклад — строгий порядок $<$ на $\mathbb{Z}$: якщо $a < b$, то
неодмінно $\neg(b < a)$.

### Приклади перевірки властивостей за матрицею

**Приклад 2.8 (перевіряємо властивості за матрицею).** Розгляньмо $R$ на $\{1,2,3,4\}$:

| $x \backslash y$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| **1** | 0 | 0 | 1 | 1 |
| **2** | 1 | 0 | 1 | 1 |
| **3** | 0 | 0 | 0 | 0 |
| **4** | 0 | 0 | 0 | 0 |

тобто $R = \{(1,3),(1,4),(2,1),(2,3),(2,4)\}$.

- *Рефлексивне?* Ні — діагональ суцільно нульова (насправді $R$ **антирефлексивне**).
- *Симетричне?* Ні — $(2, 1) \in R$, але $(1, 2) \notin R$.
- *Антисиметричне?* Так — немає жодної дзеркальної пари одиниць поза діагоналлю.
- *Транзитивне?* Так. Єдині двокрокові ланцюжки починаються у вершині $2$: з $2\,R\,1$ і
  $1\,R\,3$ потрібне $2\,R\,3$ — присутнє; з $2\,R\,1$ і $1\,R\,4$ потрібне $2\,R\,4$ —
  теж присутнє. Усі інші ланцюжки обриваються одразу, бо рядки $3$ і $4$ порожні. Оскільки
  всі потрібні «прямі стрілки» на місці, $R$ транзитивне.

![Транзитивне відношення: коли є двокроковий шлях 2→1→3, є і пряма стрілка-«зріз» 2→3](img/l02_transitive.png)

**Приклад 2.9 (симетричне відношення).** Матриця

| $x \backslash y$ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| **1** | 0 | 1 | 1 | 0 |
| **2** | 1 | 0 | 0 | 0 |
| **3** | 1 | 0 | 0 | 0 |
| **4** | 0 | 0 | 0 | 0 |

задовольняє $M_R = M_R^{\mathsf{T}}$, тож $R = \{(1,2),(2,1),(1,3),(3,1)\}$ симетричне:
кожній стрілці $a \to b$ відповідає зворотна $b \to a$, і в орграфі дуги ходять
двонапрямленими парами. Транзитивним воно **не** є: $2\,R\,1$ і $1\,R\,3$, але
$\neg(2\,R\,3)$.

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

Рефлексивність теж найлегше впізнати за орграфом — це петля при *кожній* вершині:

![Рефлексивне відношення на {1,2,3}: петля при кожній вершині (діагональ матриці суцільно одинична) плюс додаткові дуги](img/l02_reflexive.png)

> **Типова помилка (рефлексивне й антирефлексивне — не протилежності).** Відношення може
> бути **ні тим, ні тим**. На $\{1, 2\}$ відношення $\{(1, 1)\}$ має $1\,R\,1$, але не має
> $2\,R\,2$, тож воно не рефлексивне (бракує $2\,R\,2$) і не антирефлексивне (є $1\,R\,1$).
> «Не рефлексивне» означає «*якоїсь* одиниці на діагоналі бракує»; «антирефлексивне»
> означає «на діагоналі *немає жодної* одиниці». Так само симетричність і
> антисиметричність — не протилежності: тотожне відношення $\Delta_A$ є **водночас**
> симетричним і антисиметричним, а $\{(1,2),(2,1),(1,3)\}$ — **ні тим, ні тим**.

---

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

Комбінуючи властивості §2.5, дістаємо найважливіші «породи» відношень. Три з них
особливо помітні:

| Тип відношення | Рефлексивність | Симетричність | Антисиметричність | Транзитивність |
|---|:--:|:--:|:--:|:--:|
| **Еквівалентності** | + | + | | + |
| **Часткового порядку** | + | | + | + |
| **Толерантності** | + | + | | |

Кожна з цих порід описує окремий спосіб мислення про множину: еквівалентність
*групує* однакове, порядок *ранжує* різне, толерантність фіксує *схожість* (близькість),
що не мусить бути транзитивною.

### 2.6.1 Відношення еквівалентності

> **Означення (еквівалентність).** Відношення на $A$, яке водночас **рефлексивне,
> симетричне й транзитивне**, називають **відношенням еквівалентності**. Зазвичай його
> позначають $\sim$ (або $\equiv$) і читають $a \sim b$ як «$a$ еквівалентне $b$».

Еквівалентності формалізують ідею «однаковості *для наших потреб*»: мати ту саму остачу
при діленні на $n$, той самий колір, той самий колірний профіль, ту саму останню цифру.
Це інструмент, яким ми свідомо *забуваємо* неістотні розрізнення.

> **Означення (клас еквівалентності).** Нехай $\sim$ — еквівалентність на $A$ і
> $a \in A$. **Класом еквівалентності** елемента $a$ називають множину всіх
> еквівалентних йому елементів:
> $$ [a] = \{\, x \in A \mid x \sim a \,\}. $$
> Будь-який $b \in [a]$ називають **представником** цього класу.

Нам знадобиться і множинне поняття-супутник.

> **Означення (розбиття).** **Розбиттям** множини $A$ називають сім'ю
> $\mathcal{P}$ її підмножин (їх звуть **блоками** або **класами**) таку, що
> **(i)** кожен блок непорожній; **(ii)** різні блоки попарно неперетинні;
> **(iii)** блоки *покривають* $A$, тобто їх об'єднання дорівнює $A$.

Головна теорема цього параграфа стверджує, що еквівалентності й розбиття — це *та сама
річ, висловлена двома мовами*. Спершу — дві леми, на яких усе тримається.

> **Лема 2.10.** Нехай $\sim$ — еквівалентність на $A$. Для всіх $a, b \in A$:
> $$ a \sim b \iff [a] = [b]. $$
>
> *Доведення.* ($\Rightarrow$) Нехай $a \sim b$. Покажемо $[a] \subseteq [b]$: якщо
> $x \in [a]$, то $x \sim a$; разом з $a \sim b$ транзитивність дає $x \sim b$, тобто
> $x \in [b]$. За симетричністю з $a \sim b$ маємо й $b \sim a$, і той самий доказ дає
> $[b] \subseteq [a]$. Отже, $[a] = [b]$.
> ($\Leftarrow$) Нехай $[a] = [b]$. За рефлексивністю $a \sim a$, тож $a \in [a] = [b]$,
> а це означає $a \sim b$. $\blacksquare$

> **Лема 2.11 (класи або збігаються, або не перетинаються).** Нехай $\sim$ —
> еквівалентність на $A$. Для всіх $a, b \in A$ виконано **або** $[a] = [b]$, **або**
> $[a] \cap [b] = \varnothing$.
>
> *Доведення.* Припустимо, що класи перетинаються; покажемо, що вони збігаються.
> Візьмемо $c \in [a] \cap [b]$. Тоді $c \sim a$ і $c \sim b$. За симетричністю
> $a \sim c$, і разом з $c \sim b$ транзитивність дає $a \sim b$; за Лемою 2.10 звідси
> $[a] = [b]$. Отже, тільки-но класи мають спільний елемент, вони рівні, — а це рівно
> сформульована альтернатива. $\blacksquare$

> **Теорема 2.12 (основна теорема про відношення еквівалентності).** Нехай $A \ne
> \varnothing$.
> 1. Якщо $\sim$ — еквівалентність на $A$, то множина класів
>    $A/{\sim} = \{\, [a] \mid a \in A \,\}$ є **розбиттям** множини $A$.
> 2. Навпаки, якщо $\mathcal{P}$ — розбиття $A$, то відношення $\sim_{\mathcal{P}}$,
>    задане правилом
>    $$ a \sim_{\mathcal{P}} b \iff a \text{ і } b \text{ лежать в одному блоці } \mathcal{P}, $$
>    є **еквівалентністю** на $A$, а його класи — це рівно блоки $\mathcal{P}$.
> 3. Ці дві побудови взаємно обернені: вони встановлюють **бієкцію** між
>    еквівалентностями на $A$ і розбиттями $A$.
>
> *Доведення частини 1.* Перевіримо три умови означення розбиття для $A/{\sim}$.
> *Непорожність.* За рефлексивністю $a \sim a$, тож $a \in [a]$; отже, жоден клас не
> порожній. *Покриття.* Кожен клас $[a] \subseteq A$, і кожен елемент $a$ лежить у своєму
> класі $[a]$, тому об'єднання всіх класів дорівнює $A$. *Неперетинність.* Два різні класи
> не перетинаються за Лемою 2.11 (якби перетиналися — збіглися б, усупереч тому, що вони
> різні). Отже, різні класи утворюють розбиття $A$. $\blacksquare$
>
> *Доведення частини 2.* Оскільки блоки $\mathcal{P}$ покривають $A$ й попарно
> неперетинні, **кожен** $a \in A$ лежить у **точно одному** блоці; позначимо його
> $B_a$. Тоді за означенням $a \sim_{\mathcal{P}} b \iff B_a = B_b$.
> *Рефлексивність:* $B_a = B_a$, тож $a \sim a$.
> *Симетричність:* з $B_a = B_b$ випливає $B_b = B_a$.
> *Транзитивність:* з $B_a = B_b$ і $B_b = B_c$ випливає $B_a = B_c$.
> Отже, $\sim_{\mathcal{P}}$ — еквівалентність. Її клас елемента $a$ є
> $[a] = \{\, x \mid B_x = B_a \,\} = B_a$, тобто саме блок, що містить $a$. $\blacksquare$
>
> *Доведення частини 3 (ескіз).* Вирушивши від еквівалентності $\sim$, побудувавши
> розбиття $A/{\sim}$ і взявши його «відношення спільного блоку», ми повертаємось до
> $\sim$ (два елементи ділять блок $\iff [a] = [b] \iff a \sim b$ за Лемою 2.10). Навпаки,
> вирушивши від розбиття, за частиною 2 його класи — це вихідні блоки. Отже, побудови
> взаємно обернені. $\blacksquare$

> **Зауваження (навіщо це важить).** Теорема 2.12 каже, що «еквівалентність» і «розбиття»
> — це дві мови для одного явища. Щойно ви розсортували об'єкти на категорії, які не
> перетинаються й разом охоплюють усе, — ви, хочете того чи ні, задали еквівалентність, і
> навпаки. Саме тому теорему застосовують усюди: компоненти зв'язності графа, класи
> лишків цілих чисел, групування шрифтів за гарнітурою — і, у майбутній лекції з
> імовірності, розклад простору елементарних подій на несумісні події, за якими
> підсумовують імовірності. Множину класів $A/{\sim}$ називають **фактор-множиною** $A$
> за $\sim$.

**Приклад 2.13 (три обличчя однієї еквівалентності).** На $A = \{0, 1, 2, 3, 4, 5\}$
означимо $a \sim b \iff 3 \mid (a - b)$ («конгруентні за модулем $3$»). Це відношення
рефлексивне ($3 \mid 0$), симетричне (якщо $3 \mid (a - b)$, то $3 \mid (b - a)$) і
транзитивне (якщо $3 \mid (a - b)$ і $3 \mid (b - c)$, то $3 \mid (a - c)$), — отже,
еквівалентність. Його класи —
$$ [0] = \{0, 3\}, \qquad [1] = \{1, 4\}, \qquad [2] = \{2, 5\}, $$
що дає розбиття $\bigl\{ \{0, 3\},\ \{1, 4\},\ \{2, 5\} \bigr\}$ множини $A$. І навпаки,
оголосивши два числа еквівалентними, коли вони в одному блоці цього розбиття, ми
відновимо саме конгруентність за модулем $3$ — «замкнене коло», обіцяне частиною 3
Теореми 2.12.

![Класи еквівалентності «за модулем 3» розбивають множину {0,…,5} на три непорожні неперетинні блоки, що разом покривають її](img/l02_partition.png)

### 2.6.2 Відношення часткового порядку

Замінивши в переліку властивостей *симетричність* на *антисиметричність*, дістаємо
відношення зовсім іншого характеру — не «групування рівних», а «упорядкування нерівних».

> **Означення (частковий порядок, ЧУМ).** Відношення $\preceq$ на $A$, яке
> **рефлексивне, антисиметричне й транзитивне**, називають **частковим порядком**, а
> пару $(A, \preceq)$ — **частково впорядкованою множиною** (ЧУМ). Запис $a \prec b$
> означає «$a \preceq b$ і $a \ne b$» (відповідний **строгий** порядок).

Часткові порядки моделюють **ранжування з можливою непорівнянністю**: передування задач,
уточнення специфікацій, включення підмножин, подільність.

> **Означення (порівнянність, лінійний порядок).** У ЧУМ $(A, \preceq)$ елементи $a, b$
> **порівнянні**, якщо $a \preceq b$ або $b \preceq a$; інакше вони **непорівнянні**.
> Якщо порівнянна **кожна** пара, порядок називають **лінійним** (повним, тотальним), а
> $(A, \preceq)$ — **ланцюгом**.

Порядок $\le$ на $\mathbb{Z}$, $\mathbb{Q}$ чи $\mathbb{R}$ лінійний; лексикографічний
порядок на рядках лінійний; а от включення підмножин і подільність — лише часткові.

**Приклад 2.14 (подільність — частковий порядок).** На множині $D = \{1, 2, 3, 4, 6, 12\}$
(додатні дільники числа $12$) відношення «$a$ ділить $b$», позначене $a \mid b$, є
частковим порядком: $a \mid a$ (рефлексивність); для додатних чисел $a \mid b$ і
$b \mid a$ разом дають $a = b$ (антисиметричність); з $a \mid b$ і $b \mid c$ випливає
$a \mid c$ (транзитивність). Порядок лише *частковий*: $2 \mid 3$ і $3 \mid 2$ обидва
хибні, тож $2$ і $3$ непорівнянні; так само непорівнянні $4$ і $6$.

Малювати всі стрілки часткового порядку марнотратно: рефлексивні петлі й дуги, вимушені
транзитивністю, захаращують картину. Діаграма Гассе прибирає все зайве.

> **Означення (покриття; діаграма Гассе).** У ЧУМ кажуть, що $b$ **покриває** $a$
> (запис $a \lessdot b$), якщо $a \prec b$ і **немає** проміжного $c$ з $a \prec c \prec
> b$. **Діаграма Гассе** зображує по одній вершині на елемент і по одному відрізку на
> кожну пару покриття, причому *менший* елемент розміщують **нижче**; напрямок читають з
> висоти, тож стрілки не потрібні. Рефлексивні петлі й транзитивно вимушені дуги
> опускають.

**Приклад 2.15 (діаграма Гассе для $(D, \mid)$).** Для $D = \{1, 2, 3, 4, 6, 12\}$ пари
покриття такі:
$$ 1 \lessdot 2,\quad 1 \lessdot 3,\quad 2 \lessdot 4,\quad 2 \lessdot 6,\quad 3 \lessdot 6,\quad 4 \lessdot 12,\quad 6 \lessdot 12. $$
Наприклад, $1 \lessdot 4$ покриттям **не** є, бо $1 \prec 2 \prec 4$; так само $3 \lessdot 12$
не є покриттям, бо $3 \prec 6 \prec 12$. Унизу стоїть $1$, угорі — $12$; решту зв'язків
(як-от $1 \mid 12$) відновлюють, ідучи відрізками *вгору* й користуючись транзитивністю.

![Діаграма Гассе дільників числа 12 за подільністю: унизу 1, угорі 12, по одному відрізку на кожну пару покриття](img/l02_hasse.png)

Наостанок розрізнимо чотири близькі, але різні поняття крайніх елементів.

> **Означення (мінімальний/максимальний, найменший/найбільший).** Нехай $(A, \preceq)$ —
> ЧУМ.
> - $m$ — **мінімальний** елемент, якщо жоден $x$ не задовольняє $x \prec m$ (нічого
>   строго нижчого немає).
> - $m$ — **максимальний**, якщо жоден $x$ не задовольняє $m \prec x$.
> - $\ell$ — **найменший** елемент, якщо $\ell \preceq x$ для **кожного** $x \in A$.
> - $g$ — **найбільший**, якщо $x \preceq g$ для **кожного** $x \in A$.

> **Твердження 2.16 (єдиність найменшого).** ЧУМ має **щонайбільше один** найменший
> елемент.
>
> *Доведення.* Нехай $\ell$ і $\ell'$ — обидва найменші. Оскільки $\ell$ найменший, а
> $\ell' \in A$, то $\ell \preceq \ell'$. Оскільки $\ell'$ найменший, а $\ell \in A$, то
> $\ell' \preceq \ell$. Антисиметричність дає $\ell = \ell'$. $\blacksquare$

> **Типова помилка (мінімальний $\ne$ найменший).** *Мінімальний* означає «нижче нього
> нічого немає»; *найменший* означає «він нижчий за все». ЧУМ може мати кілька
> мінімальних елементів і жодного найменшого. У $(D, \mid)$ вся множина має найменший
> елемент $1$ і найбільший $12$; але *підмножина* $\{2, 3, 4, 6\}$ має **два** мінімальні
> елементи ($2$ і $3$) і жодного найменшого, а також два максимальні ($4$ і $6$) і жодного
> найбільшого.

### 2.6.3 Відношення толерантності

> **Означення (толерантність).** Відношення на $A$, яке **рефлексивне й симетричне**
> (транзитивність *не* вимагається), називають **відношенням толерантності**.

Толерантність — це послаблена еквівалентність: ми зберігаємо «$a$ схоже саме на себе»
(рефлексивність) і «схожість взаємна» (симетричність), але відмовляємось від
транзитивності. Саме відмова від транзитивності робить толерантність придатною для
моделювання **близькості, подібності, нерозрізнюваності**, які накопичуються й тому не
є транзитивними.

**Приклад 2.17 (нерозрізнюваність відтінків).** Нехай елементи — відтінки сірого, а
$a \sim b$ означає «людське око не відрізняє $a$ від $b$» (різниця яскравостей нижча за
поріг). Це відношення рефлексивне (кожен відтінок нерозрізнюваний із собою) і симетричне
(нерозрізнюваність взаємна), але **не** транзитивне: сусідні відтінки $a$ і $b$ попарно
нерозрізнювані, і $b$ та $c$ теж, — а от крайні $a$ і $c$ вже помітно різні. Це класичний
«парадокс купи»: багато малих непомітних кроків дають помітну відмінність. Отже, ми маємо
толерантність, що не є еквівалентністю. Подібні відношення виникають у поліграфії скрізь,
де йдеться про *допустиму відмінність* кольору чи розміру (див. §2.10).

> **Зауваження.** Кожна еквівалентність є толерантністю (вона додатково транзитивна), але
> не навпаки. Толерантність не породжує розбиття: її «класи схожості» можуть
> перекриватися — і в цьому вся суть.

---

## 2.7 Функціональні відношення та функції

Серед усіх відношень особливо важливі ті, що пов'язують кожен вхід не більш ніж з одним
виходом.

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

Наочно: у матриці функціонального відношення в кожному рядку **не більше однієї
одиниці**; в орграфі (двочастковому) з кожної вершини зліва виходить **не більше однієї**
стрілки.

> **Означення (функція).** Якщо функціональне відношення $F \subseteq A \times B$
> додатково пов'язує **кожен** $x \in A$ рівно з одним $y$, його називають **функцією**
> (відображенням) з $A$ у $B$ і пишуть $f\colon A \to B$, а замість $(x, y) \in F$ —
> звичне $y = f(x)$. При цьому **областю визначення** є вся $A$, тобто $\operatorname{dom}
> f = A$, а **областю значень** — образ $f(A) = \{\, f(x) \mid x \in A \,\} \subseteq B$.

Отже, функція *є* відношенням — таким, що задовольняє умову однозначності. Це не
формальність: саме як **графік** $\{\, (x, f(x)) \mid x \in A \,\} \subseteq A \times B$
функцію строго означують у теорії множин і саме так її зберігають у пам'яті комп'ютера —
таблицею «ключ — значення».

**Приклад 2.18 (які відношення не є функціями).** На $\{1, 2, 3\}$:
- Відношення $\{(1, 2), (1, 3)\}$ **не** є функцією: вхід $1$ має два виходи —
  однозначність порушено.
- Відношення $\{(1, 2), (2, 2)\}$ **є** функцією (частковою), хоча два входи ділять один
  вихід $2$: однозначність обмежує *кількість виходів на вхід*, а не *входів на вихід*.
- Щоб бути *всюди визначеною* функцією $f\colon \{1,2,3\} \to B$, треба ще, щоб і вхід $3$
  мав (рівно один) вихід.

---

## 2.8 Відображення: ін'єкції, сюр'єкції, бієкції

Функції класифікують за тим, як вони «накривають» цільову множину $B$.

> **Означення (ін'єкція, сюр'єкція, бієкція).** Нехай $f\colon A \to B$.
> - $f$ **ін'єктивне** (ін'єкція, взаємно однозначне *в*), якщо різні входи дають різні
>   виходи: $x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2)$ (рівносильно $f(x_1) = f(x_2)
>   \Rightarrow x_1 = x_2$).
> - $f$ **сюр'єктивне** (сюр'єкція, відображення *на*), якщо кожен $y \in B$ є образом
>   принаймні одного входу: $\operatorname{ran} f = B$.
> - $f$ **бієктивне** (бієкція, взаємно однозначна відповідність), якщо воно водночас
>   ін'єктивне й сюр'єктивне.

![Три види відображень: ін'єктивне (різні входи — різні виходи, але накрито не все B), сюр'єктивне (накрито все B, але два входи злилися) і бієктивне (взаємно однозначна відповідність)](img/l02_mappings.png)

**Приклад 2.19.** Нехай $A = \{a_1, a_2, a_3\}$.
- $f\colon A \to \{1, 2, 3, 4\}$, $f(a_1)=1, f(a_2)=2, f(a_3)=3$, — ін'єктивне (виходи
  різні), але не сюр'єктивне (значення $4$ не досягається).
- $g\colon A \to \{1, 2\}$, $g(a_1)=1, g(a_2)=2, g(a_3)=2$, — сюр'єктивне (обидва
  значення досягаються), але не ін'єктивне ($a_2$ і $a_3$ мають один образ).
- $h\colon A \to \{1, 2, 3\}$, $h(a_1)=1, h(a_2)=2, h(a_3)=3$, — бієкція.

> **Зауваження (бієкція й обернена функція).** Функція $f\colon A \to B$ має обернену
> функцію $f^{-1}\colon B \to A$ тоді й лише тоді, коли вона бієктивна; при цьому обернене
> *відношення* $f^{-1}$ (§2.5) саме є функцією. Саме бієкції задають рівнопотужність
> множин $A \sim B$, з якою ми познайомилися в [Лекції 1](ODM-L01.md): дві скінченні
> множини рівнопотужні тоді й лише тоді, коли між ними існує бієкція, а отже, мають
> однакову кількість елементів.

---

## 2.9 Реляційна структура даних і реляційна алгебра

Узагальнення до $n$-арних відношень (§2.2) — не абстрактна забаганка: це буквально модель
даних кожної **реляційної бази даних**.

> **Означення (реляційна таблиця).** $n$-арне відношення $R \subseteq A_1 \times \dots
> \times A_n$ — це **таблиця**: кожен кортеж $(a_1, \dots, a_n) \in R$ — це **рядок**
> (запис), кожен множник $A_i$ — це **стовпець** (атрибут) зі своєю областю значень
> (доменом), а число $n$ — **арність** таблиці (кількість стовпців).

Повернімося до Прикладу 2.3. Тернарне відношення навчальних записів — це таблиця:

| СТУДЕНТ | ПРЕДМЕТ | ОЦІНКА |
|---|---|---|
| Шевченко | Інформатика | B |
| Косач | Дизайн прототипів | A |
| Франко | ОДМ | E |

![Таблиця бази даних як тернарне відношення: кожен рядок — кортеж (студент, предмет, оцінка), кожен стовпець — атрибут зі своїм доменом](img/l02_db_table.png)

> **Зауваження (множина не має ані порядку, ані повторів).** Оскільки відношення — це
> *множина* кортежів, у цій ідеалізованій моделі таблиця не має ані повторюваних рядків,
> ані наперед заданого порядку рядків — точнісінько як $\{x, x\} = \{x\}$ і множини
> невпорядковані. Реальні системи SQL це послаблюють (працюють з мультимножинами), але
> теорія — множинна.

### Операції реляційної алгебри

Оскільки відношення — це множини, до двох таблиць **однакової форми** (з тією самою
послідовністю атрибутів) застосовні операції з Лекції 1: **об'єднання** $R \cup S$,
**перетин** $R \cap S$ та **різниця** $R \setminus S$. Додавши кілька специфічних для
таблиць операцій, дістаємо **реляційну алгебру** — теорію, що лежить в основі SQL.

- **Декартів добуток** $R \times S$ — зчіплює кожен рядок $R$ з кожним рядком $S$ (той
  самий добуток, що й у §2.1).
- **Проєкція** $\pi_{i_1, \dots, i_k}(R)$ — лишає тільки вказані стовпці, відкидаючи
  решту (і злипаючи однакові рядки, що виникли); це вибір *підмножини атрибутів*
  (відповідник `SELECT` конкретних стовпців у SQL).
- **Вибірка (селекція)** $\sigma_{\varphi}(R)$ — лишає тільки рядки, що задовольняють
  умову $\varphi$; це вибір *підмножини кортежів* (відповідник `WHERE` у SQL).
- **Натуральне з'єднання** $R \bowtie S$ — поєднує ті рядки $R$ і $S$, що **збігаються на
  спільних атрибутах**; це відфільтрований, узгоджений декартів добуток. Саме з'єднання
  «зшиває» дані, розкидані по кількох таблицях.

**Приклад 2.20 (проєкція, вибірка, з'єднання).** Нехай задано дві таблиці:

| ЗАПИС: СТУДЕНТ | КУРС |
|---|---|
| Косач | Алгебра |
| Косач | ОДМ |
| Франко | ОДМ |

| АУДИТОРІЯ: КУРС | КІМНАТА |
|---|---|
| Алгебра | 101 |
| ОДМ | 205 |

Тоді:
- Проєкція $\pi_{\text{СТУДЕНТ}}(\text{ЗАПИС}) = \{\text{Косач}, \text{Франко}\}$
  (повтор «Косач» злипається).
- Вибірка $\sigma_{\text{КУРС} = \text{ОДМ}}(\text{ЗАПИС})$ лишає два рядки з курсом ОДМ.
- Натуральне з'єднання за спільним атрибутом КУРС дає:

| ЗАПИС $\bowtie$ АУДИТОРІЯ: СТУДЕНТ | КУРС | КІМНАТА |
|---|---|---|
| Косач | Алгебра | 101 |
| Косач | ОДМ | 205 |
| Франко | ОДМ | 205 |

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

> **Історична довідка.** Реляційну модель даних запропонував **Едґар Ф. Кодд** (IBM) у
> статті «A Relational Model of Data for Large Shared Data Banks» (1970). Ідея була
> радикальною: подати дані не як заплутану мережу вказівників, а як прості *математичні
> відношення* — таблиці, — з якими працює строга алгебра операцій. На цьому фундаменті
> побудовано мову SQL і практично всі сучасні бази даних. Абстрактне поняття $n$-арного
> відношення виявилося, можливо, найкомерційніше успішним застосуванням дискретної
> математики.

---

## 2.10 Застосування у видавництві та поліграфії

Мова відношень безпосередньо описує задачі фаху:

- **Бази даних видавництва.** Каталог видань (автор, назва, ISBN, наклад, рік),
  облік замовлень і клієнтів, склад матеріалів — усе це реляційні таблиці, тобто
  $n$-арні відношення. Кожен звіт («усі книжки автора $X$ за 2025 рік») — це комбінація
  вибірки, проєкції та натурального з'єднання (§2.9).
- **Толерантність кольору.** Відношення «два зразки кольору візуально збігаються в межах
  допуску $\Delta E$» рефлексивне й симетричне, але **не** транзитивне (Приклад 2.17):
  саме тому колірні допуски задають попарно, а не «класами». Це відношення толерантності,
  а не еквівалентності.
- **Частковий порядок технологічного процесу.** Етапи виробництва — препрес, кольороподіл,
  спуск шпальт, друк, фальцювання, різання, оправлення — впорядковані відношенням
  передування «має бути виконане раніше». Це частковий порядок: деякі етапи непорівнянні
  (їх роблять паралельно). Діаграма Гассе такого порядку — це, по суті, мережевий графік
  робіт, а лінійне впорядкування, узгоджене з ним, дає коректну послідовність операцій.
- **Еквівалентність і групування.** Розбиття зображень за колірним профілем (sRGB,
  Adobe RGB, CMYK) або шрифтів за гарнітурою — це класи еквівалентності; за Теоремою 2.12
  таке групування *є* відношенням еквівалентності, і навпаки.
- **Функції перетворення.** Відповідності «символ $\to$ гліф» у шрифті та «колір RGB $\to$
  колір CMYK» у растровому процесорі — це функції $f\colon A \to B$; коли перетворення
  оборотне без втрат, воно бієктивне (§2.8).

---

## Підсумок

- **Відношення** — це підмножина декартового добутку; **бінарне** відношення — це
  $R \subseteq A \times B$, а $(a, b) \in R$ пишуть як $a\,R\,b$. Задають його
  **переліком** пар або **предикатом**; записують як **множину пар**, **булеву матрицю**
  або **орграф**.
- Опорні відношення: **повне** $A \times A$ (усі одиниці), **пусте** $\varnothing$ (усі
  нулі), **тотожне** $\Delta_A$ (одинична матриця).
- Основні **властивості** — рефлексивність, антирефлексивність, симетричність,
  антисиметричність, асиметричність, транзитивність — мають матричні ознаки й
  алгебраїчні форми: $\Delta_A \subseteq R$; $R = R^{-1}$; $R \cap R^{-1} \subseteq
  \Delta_A$ (Теорема 2.6). Асиметричність $=$ антирефлексивність $+$ антисиметричність
  (Твердження 2.7).
- **Еквівалентність** (рефлексивне + симетричне + транзитивне) відповідає **розбиттю** —
  це **основна теорема** (Теорема 2.12), доведена в обидва боки; прообраз — конгруентність
  за модулем $n$.
- **Частковий порядок** (рефлексивне + антисиметричне + транзитивне) малюють **діаграмою
  Гассе** за парами покриття. Розрізняйте **мінімальний/максимальний** і
  **найменший/найбільший** (найменший єдиний — Твердження 2.16).
- **Толерантність** (рефлексивне + симетричне) — послаблена еквівалентність без
  транзитивності; моделює схожість і нерозрізнюваність.
- **Функція** — це однозначне (функціональне) відношення; всюди визначену функцію пишуть
  $f\colon A \to B$. Відображення бувають **ін'єктивні**, **сюр'єктивні** й **бієктивні**;
  бієкції задають рівнопотужність (Лекція 1).
- $n$-арні відношення — це **таблиці** реляційної моделі даних; ними керує **реляційна
  алгебра** (об'єднання, перетин, різниця, декартів добуток, проєкція, вибірка, натуральне
  з'єднання) — математична основа SQL.

Далі, у [Лекції 3](ODM-L03.md), ми переходимо до **булевої алгебри** — числення над двома
значеннями (1 і 0), у якому операції $\wedge$, $\vee$, $\neg$ дзеркалять перетин, об'єднання
й доповнення множин, а самі множини кодуються бітовими векторами.

## Вправи

### Для розігріву

1. Нехай $A = \{1, 2, 3\}$, $B = \{x, y\}$. Випишіть повністю $A \times B$ і $B \times A$.
   Скільки елементів у кожному? Чи рівні ці множини?
2. Для відношення $R = \{(1,1),(1,2),(2,3),(3,4),(4,4)\}$ на $\{1,2,3,4\}$:
   **(а)** побудуйте матрицю $M_R$; **(б)** знайдіть $\operatorname{dom}(R)$ і
   $\operatorname{ran}(R)$; **(в)** визначте, чи воно рефлексивне, симетричне,
   антисиметричне, транзитивне.
3. Для кожного з відношень на $\{1, 2, 3\}$ визначте, яке з властивостей (рефлексивність,
   симетричність, антисиметричність, транзитивність) воно має: **(а)** $\varnothing$;
   **(б)** $A \times A$; **(в)** $\Delta_A = \{(1,1),(2,2),(3,3)\}$.
4. Випишіть класи еквівалентності конгруентності за модулем $4$ на $\{0, 1, \dots, 11\}$ і
   запишіть відповідне розбиття.
5. Побудуйте орграф відношення $R = \{(1,2),(2,1),(2,3),(3,3)\}$ на $\{1,2,3\}$. Скільки
   петель і скільки звичайних дуг він має?

### Стандартні

6. Доведіть, що відношення $\{(1,2),(2,1),(1,3)\}$ на $\{1,2,3\}$ не є ані симетричним,
   ані антисиметричним. Який найменший набір пар треба додати, щоб зробити його
   симетричним?
7. На $\mathbb{Z}$ означимо $a \sim b \iff a$ і $b$ мають однакову парність. Доведіть, що
   $\sim$ — відношення еквівалентності, і опишіть його класи як розбиття $\mathbb{Z}$.
8. Розгляньте подільність на $D_{24} = \{1, 2, 3, 4, 6, 8, 12, 24\}$. **(а)** Поясніть,
   чому це ЧУМ. **(б)** Випишіть усі пари покриття й накресліть діаграму Гассе.
   **(в)** Укажіть найменший, найбільший, мінімальні й максимальні елементи.
9. Наведіть приклад відношення на $\{1, 2, 3\}$, яке рефлексивне й симетричне, але **не**
   транзитивне (тобто толерантність, що не є еквівалентністю). Поясніть, яка саме трійка
   елементів порушує транзитивність.
10. Розбиття $\{\{1, 4\}, \{2\}, \{3, 5\}\}$ множини $\{1,2,3,4,5\}$ породжує
    еквівалентність $\sim$. Випишіть усі пари $\sim$ і знайдіть $|{\sim}|$ (кількість пар).
11. Для кожної з функцій $\{1,2,3\} \to \{1,2,3\}$ визначте, чи вона ін'єктивна,
    сюр'єктивна, бієктивна: **(а)** $f(x) = x$; **(б)** $g(1)=g(2)=1,\ g(3)=2$;
    **(в)** $h(1)=2, h(2)=3, h(3)=1$.
12. З таблицями ЗАПИС і АУДИТОРІЯ з Прикладу 2.20 випишіть **(а)**
    $\sigma_{\text{СТУДЕНТ} = \text{Косач}}(\text{ЗАПИС})$; **(б)**
    $\pi_{\text{КУРС}}(\text{ЗАПИС})$; **(в)** натуральне з'єднання
    $\text{ЗАПИС} \bowtie \text{АУДИТОРІЯ}$, — і поясніть одним реченням, що означає кожен
    результат.

### Підвищеної складності

13. Доведіть, що коли $R$ і $S$ — транзитивні відношення на $A$, то $R \cap S$ теж
    транзитивне. Потім наведіть конкретний приклад на $\{1, 2, 3\}$ двох транзитивних
    відношень, **об'єднання** яких не транзитивне.
14. На множині з $|A| = n$ елементів порахуйте кількість **(а)** усіх відношень;
    **(б)** рефлексивних відношень; **(в)** симетричних відношень; **(г)** відношень,
    що водночас рефлексивні й симетричні. Обчисліть кожну відповідь для $n = 3$.
    *(Підказка: відношення — це заповнення сітки $n \times n$ бітами.)*
15. Доведіть, що якщо ЧУМ $(A, \preceq)$ має найменший елемент $\ell$, то $\ell$ —
    **єдиний** мінімальний елемент. Чи правильне обернене твердження для скінченних ЧУМ?
    Для нескінченних? Обґрунтуйте або спростуйте прикладом.
16. **(Замикання до еквівалентності.)** Нехай $R$ — довільне відношення на $A$. Доведіть,
    що перетин будь-якої непорожньої сім'ї еквівалентностей на $A$ знову є
    еквівалентністю. Виведіть звідси, що існує **найменша** еквівалентність $e(R)$, яка
    містить $R$.