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

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

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). Підставивши $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$ виокремлюють три «крайні» відношення, з якими корисно порівнювати своє:

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$. Нижче зібрано властивості, які треба вміти перевіряти, разом із тим, як кожна з них виглядає в орграфі та в матриці.

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

Типова помилка (рефлексивність проти антирефлексивності). Це не протилежні властивості. Відношення може бути ні рефлексивним, ні антирефлексивним — досить, щоб петля була в однієї вершини й не було в іншої. Скажімо, на $\{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$ на неперетинні класи еквівалентності (розбиття): кожен елемент потрапляє рівно в один клас пов’язаних із ним елементів. Приклади: рівність, «однакова парність», «однакова остача при діленні на $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 \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; для цієї роботи достатньо вміти відрізняти функціональне відношення від нефункціонального.

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$:

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

Крок 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. Функціональність — подивіться, чи немає рядка матриці (вершини орграфа) з більш ніж однією одиницею (вихідною дугою); поясніть висновок.

Practical/Practical2/2method.md · 27.4 KB · updated 2026-08-04 14:37