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

Огляд #

Множини, які ми вивчали в Лекції 1, описують сукупності об’єктів. Проте майже кожне змістовне твердження математики чи інформатики стосується не окремих об’єктів, а зв’язків між ними: «$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\}$ матриця така:

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

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

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

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

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

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

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

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

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

Означення (повне, пусте, тотожне). Нехай $A$ — множина, $|A| = n$.

• Повне (універсальне) відношення $R = A \times A$ пов’язує кожну пару; його матриця складається суцільно з одиниць.
• Пусте (порожнє) відношення $R = \varnothing$ не пов’язує жодної пари; його матриця складається суцільно з нулів.
• Тотожне (діагональне) відношення

  $$\Delta_A = \{\, (a, a) \mid a \in A \,\}$$

  пов’язує кожен елемент лише із самим собою; його матриця — одинична (одиниці на головній діагоналі, нулі поза нею), а орграф — це петля при кожній вершині й більше нічого.

Тотожне відношення $\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\}$:

тобто $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.9 (симетричне відношення). Матриця

задовольняє $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)$.

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

Типова помилка (рефлексивне й антирефлексивне — не протилежності). Відношення може бути ні тим, ні тим. На $\{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.

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$) відновлюють, ідучи відрізками вгору й користуючись транзитивністю.

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

Означення (мінімальний/максимальний, найменший/найбільший). Нехай $(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$ бієктивне (бієкція, взаємно однозначна відповідність), якщо воно водночас ін’єктивне й сюр’єктивне.

Приклад 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: дві скінченні множини рівнопотужні тоді й лише тоді, коли між ними існує бієкція, а отже, мають однакову кількість елементів.

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. Тернарне відношення навчальних записів — це таблиця:

Зауваження (множина не має ані порядку, ані повторів). Оскільки відношення — це множина кортежів, у цій ідеалізованій моделі таблиця не має ані повторюваних рядків, ані наперед заданого порядку рядків — точнісінько як $\{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 (проєкція, вибірка, з’єднання). Нехай задано дві таблиці:

Тоді:

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

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

Історична довідка. Реляційну модель даних запропонував Едґар Ф. Кодд (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, ми переходимо до булевої алгебри — числення над двома значеннями (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{АУДИТОРІЯ}$, — і поясніть одним реченням, що означає кожен результат.