Бінарне відношення

Властивості бінарних відношень:
${\displaystyle \forall a,b,c\;\in {X}:}$

рефлексивність ${\displaystyle (aRa)\!}$
антирефлексивність ${\displaystyle \lnot (aRa)\!}$

симетричність ${\displaystyle aRb\Rightarrow bRa\!}$
асиметричність ${\displaystyle aRb\;\Rightarrow \lnot (bRa)}$

антисиметричність ${\displaystyle aRb\wedge bRa\Rightarrow a=b}$

транзитивність ${\displaystyle aRb\wedge bRc\Rightarrow aRc}$
антитранзитивність ${\displaystyle aRb\wedge bRc\Rightarrow \lnot (aRc)}$

повнота ${\displaystyle aRb\vee bRa\!}$

Бінарне відношення (бінарне відношення на множині) — в математиці окремий випадок відношення заданого на множині M, яке встановлюється між двома елементами множини. Іншими словами, це підмножина декартового квадрата M² = M × M.

Також кажуть, що елементи a, b ∈ M перебувають у бінарному відношенні R (часто записують у вигляді aRb), якщо впорядкована пара (a, b) ∈ R і записують, що R ⊆ M×M.

Взагалі, бінарне відношення між двома множинами A і B — це підмножина A × B. В цьому випадку вживають термін відповідність між множинами. Термін 2-місне відношення або 2-арне відношення є синонімами бінарного відношення.

В деяких системах аксіом теорії множин, відношення розширюються до класів, які є узагальненнями множин. Таке розширення потрібне, зокрема для того, щоб формалізувати поняття «є елементом» або «є підмножиною» теорії множин і запобіганню таких невідповідностей, як парадокс Расселла.

Приклади

Шахова дошка 5x5

У чорних клітин сума координат — парне число.

Приклади бінарних відношень на множині натуральних чисел ${\displaystyle \mathbb {N} }$:

• R₁ — відношення ${\displaystyle \leqslant }$ («менше або дорівнює»), тоді 4 R₁ 9 та 5 R₁ 5.
• R₂ — відношення «ділиться на», тоді 4 R₂ 2, 49 R₂ 7, m R₂ 1 для будь-якого натурального m.
• R₃ — відношення «є взаємно простими», тоді 15 R₃ 8, 366 R₃ 121, 1001 R₃ 612.
• R₄ — відношення «складаються з однакових цифр», тоді 127 R₄ 721, 230 R₄ 302, 3231 R₄ 3213311.
• Шахівниця. Множина ${\displaystyle A=\{1,2,3,4,5\}.}$ На декартовому добутку ${\displaystyle A\times A}$ задано відношення ${\displaystyle R=\{(a,b)|\,a,b\in A,(a+b)\equiv 0{\pmod {2}}\}.}$ Відношення ${\displaystyle R}$ задає на шаховій дошці чорні клітини — клітини у яких сума координат буде парним числом.

Види відношень

• Рефлексивне транзитивне відношення називається відношенням квазіпорядку.
• Рефлексивне симетричне транзитивне відношення називається відношенням еквівалентності.
• Рефлексивне антисиметричне транзитивне відношення називається відношенням (часткового) порядку.
• Антирефлексивне антисиметричне транзитивне відношення називається відношенням строгого порядку.
• Повне антисиметричне (для будь-яких x, y виконується xRy або yRx) транзитивне відношення називається відношенням лінійного порядку.
• Антирефлексивне антисиметричне відношення називається відношенням домінування.

Операції з відношеннями

Оскільки відношення на M є також множинами, то над ними дозволені теоретико-множинні операції. Наприклад:

• перетином бінарних відношень «більше або дорівнює» і «менше або дорівнює» є відношення «дорівнює»,
• об'єднанням відношень «менше» і «більше» є відношення «не дорівнює»,
• доповненням відношення «ділиться на» є відношення «не ділиться на» тощо.

Обернене відношення

Відношення R⁻¹ називається оберненим до відношення R, якщо bR⁻¹a тоді і тільки тоді, коли aRb. Очевидно, що (R⁻¹)⁻¹=R.

Наприклад, для відношення «більше або дорівнює» оберненим є відношення «менше або дорівнює», для відношення «ділиться на» — відношення «є дільником».

Композиція

Композицією відношень R₁ і R₂ на множині M (позначається R₁oR₂) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент c∈M, для якого виконується aR₁c і cR₂b.

Наприклад, композицією відношень R₁ — «є сином» і R₂ — «є братом» на множині чоловіків є відношення R₁oR₂ — «є небожем».

Властивості

Нехай R — деяке відношення на множині M. Відношення R називається:

• оберненим (відношення, обернене до R), якщо воно складається з пар елементів (у, х), отриманих перестановкою пар елементів (х, у) даного відношення R. Позначається: R⁻¹. Для даного відношення і оберненого до нього виконується рівність:  (R⁻¹)⁻¹ = R.
  • взаємообернені відношення — відношення, що є оберненими одне до одного. Область значень одного з них служить областю визначення іншого, а область визначення першого — областю значень іншого.
• рефлексивним, якщо для всіх a ∈ M має місце aRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого х цієї множини елемент х перебуває у відношенні R до самого себе, тобто для будь-якого елемента х цієї множини має місце xRx. Приклади рефлексивних відношень: рівність, одночасність, подібність.
• корефлексивним, якщо будь-які два елементи ${\displaystyle (a,b)}$ множини ${\displaystyle X}$, що перебувають у відношенні ${\displaystyle (a,b)\in R}$ (що записують ще як ${\displaystyle aRb}$), збігаються ${\displaystyle a=b}$^[1].
• антирефлексивним (іррефлексивним), якщо для жодного a ∈ M не виконується aRa. Відзначимо, що так само, як антисиметричність не збігається з несиметричністю, іррефлексівність не збігається з нерефлексивністю. Двомісне відношення R, визначене на деякій множині M і відрізняється тим, що для будь-якого елемента х цієї множини не виконується, що воно перебуває у відношенні R до самого себе (відсутнє xRx), тобто можливий випадок, що елемент множини не перебуває у відношенні R до самого себе. Приклади нерефлексивних відношень: «дбати про», «розважати», «нервувати».
• симетричним, якщо для всіх a, b∈ M таких, що aRb маємо bRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких елементів х і у цієї множини з того, що х перебуває до у відношенні R (xRy), випливає, що й у перебуває в тому ж відношенні до х (yRx). Прикладами симетричних відношень є рівність (=), відношення еквівалентності, подібності, одночасності, деякі відношення споріднення.

Симетричне відношення

• асиметричним, якщо для всіх a, b∈ M таких, що aRb не виконується bRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy слідує заперечення yRx. Приклад: відношення «більше» (>) і «менше» (<).
• антисиметричним, якщо для всіх a, b∈ M таких, що aRb і a ${\displaystyle \neq }$ b, маємо що bRa — не виконується. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR — 1y випливає х = у (тобто R і R⁻¹ виконуються одночасно лише для рівних між собою членів).
• транзитивним, якщо зі співвідношень aRb і bRc випливає aRc. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz випливає xRz (xRy & ${\displaystyle yRz\to xRz}$). Приклади транзитивних відношень: «більше», «менше», «дорівнює», «подібно», «вище», «північніше».
• нетранзитивним, якщо для будь-яких х, у, z із множини, на якій визначено відношення, з xRy і yRz не випливає xRz. Приклад нетранзитивного відношення: «x батько y».
• повним, якщо для будь-яких a, b ∈ M випливає, що aRb або bRa.
• відношенням порядку, якщо воно володіє тільки деякими з трьох властивостей відношення еквівалентності. Зокрема, відношення рефлексивне і транзитивне, але несиметричне (наприклад, «не більше») утворює «нестрогий» порядок. Відношення транзитивне, але нерефлексивне і несиметричне (наприклад, «менше») — «строгий» порядок.
• функцією, якщо кожному значенню x відношення xRy відповідає лише одне — єдине значення y. Приклад: «y батько x». Властивість функціональності відношення R записується у вигляді аксіоми: (xRy і xRz) → (y ≡ z). Оскільки кожному значенню x у виразах xRy і xRz відповідає одне і те ж значення, то y і z збіжаться, виявляться одними і тими ж. Функціональне відношення однозначне, оскільки кожному значенню x відношення xRy відповідає єдине значення y, але не навпаки.
• бієкцією, якщо кожному значенню х відповідає єдине значення у, і кожному значенню у відповідає єдине значення х.
• відношенням зв'язку, якщо для будь-яких двох різних елементів х та у із множини, на якій визначено відношення, одне з них перебуває у відношенні R до іншого (тобто виконано одне з двох співвідношень: xRy або yRx). Приклад: відношення «менше» (<).

Якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R⁻¹ також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.

Відношення, яке є рефлексивним, симетричним та транзитивним, називається відношенням еквівалентності.

З поняттям відношення еквівалентності тісно пов'язане поняття розбиття.

Теорема 1. Відношення Е є відношенням еквівалентності на множині R тоді й лише тоді, коли воно визначає розбиття П_Е на множині R.

Доведення. 

а) Пряме. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що означає, що належать одній і тій ж підмножині R_i розбиття П. Тоді відношення Е(П) — рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду для кожного симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду  то включаємо і пару вигляду, транзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду, то включаємо і пару вигляду  Таким чином, відношення Е(П) — відношення еквівалентності.

б) Обернене. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію  котра елементу r_i ставить у відповідність підмножину Тому що відношення Е рефлексивне, то а отже Залишається показати, що будь-які дві підмножини  або не перетинаються, або є рівними. Нехай це не так і є загальний елемент але підмножини і  не рівні. Але тоді справедливо  В силу симетричності відношення E, якщо виконується  то виконується За наявності в відношенні E пар  в силу транзитивності відношення E в ньому присутня пара  З того, що для будь-якого  справедливо і, отже, в силу транзитивності справедливо слідує, що  Помінявши місцями елементи аналогічно встановлюємо справедливість  Але це означає  Іншими словами, будь-які підмножини або не перетинаються, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовольняють другому обмеженню на розбиття. Теорема доведена.

Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається відношенням часткового порядку.

Відношення часткового порядку, яке є повним, називається відношенням лінійного порядку (чи лінійним порядком).

Властивості відношень за назвами

Назва	рефлексивність	антирефлексивність	симетричність	асиметричність	антисиметричність	транзитивність	повнота
Перевага	+
Подібність (толерантність)	+		+
Еквівалентність	+		+			+
Часткова еквівалентність			+			+
Квазіпорядок	+					+
Впорядкування	+					+	+
Частковий порядок	+				+	+
Лінійний порядок	+				+	+	+
Строгий квазіпорядок		+				+
Строгий порядок		+		+	(+)	+
Домінування		+		+	(+)
Строгий частковий порядок		+		+	(+)	+
Строгий лінійний порядок		+		+	(+)	+	+

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

Для того, щоб задати відношення (R, Ω), необхідно задати всі пари елементів (x, y)∈Ω×Ω, які включено в множину R. Крім повного переліку всіх пар, існують три способи задання відношень: за допомогою матриці, графу й розрізів. Перші два способи застосовують, щоб задати відношення на скінченних множинах, задання відношення розрізами може бути застосовано й до нескінченних множин.

Задання відношення за допомогою матриці

Нехай множина Ω складається з n елементів, R– подане на цій множині бінарне відношення. Пронумеруємо елементи множини Ω цілими числами від 1 до n. Для того, щоб задати відношення, побудуємо квадратну таблицю розміром n×n. Її i-й рядок відповідає елементу x_i множини Ω, j-й стовпчик — елементу x_j з множини Ω. На перетині i-го рядка та j-го стовпчика ставимо 1, якщо елемент x_i перебуває у відношенні R з елементом x_j , і нуль в інших випадках.

Задання відношення за допомогою графу

Для того, щоб задати відношення за допомогою графу, поставимо у взаємно однозначну відповідність елементам скінченної множини Ω, на якій визначено відношення, вершини графу x₁,…,x_n (за будь-якою нумерацією).

Провести дугу від вершини x_i до x_j, можна тоді й тільки тоді, коли елемент x_i перебуває у відношенні R з елементом x_j, коли ж i = j, то дуга (x_i,x_j) перетворюється на петлю при вершині x_i.

Задання відношень за допомогою розрізів

Верхнім розрізом відношення (R,Ω) в елементі x, позначене через R⁺(x), називається множина елементів y∈Ω, для яких виконано умову: (y, x)∈R, тобто R⁺(x)={y∈Ω|(y, x)∈R}.

Нижнім розрізом відношення (R,Ω) в елементі x, позначене через R^-(x), називається множина елементів y∈Ω, для яких виконано умову: (x, y)∈R, а саме R^-(x)={y∈Ω|(x, y)∈R}.

Отже, верхній розріз (множина R⁺) являє собою множину всіх таких елементів y, що перебувають у відношенні R з фіксованим елементом х(yRx). Нижній розріз (множина R^-) — це множина всіх таких елементів у, з якими фіксований елемент х перебуває у відношенні R(xRy).

Таким чином, для того, щоб задати відношення за допомогою розрізів, необхідно описати всі верхні або всі нижні його розрізи. Тобто відношення R буде задано, якщо для кожного елемента x∈Ω задано множину R⁺(x) або для кожного елемента x∈Ω задано множину R^-(x).

Див. також

• Відношення на множині
• Відповідність між множинами
• Відношення порядку
• Відношення еквівалентності
• Відношення домінування
• Евклідове відношення

Джерела

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ(інші мови), 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)

1. Fonseca de Oliveira, J. N., & Pereira Cunha Rodrigues, C. D. J. (2004). Transposing Relations: From Maybe Functions to Hash Tables. In Mathematics of Program Construction (p. 337). URL: https://link.springer.com/chapter/10.1007%2F978-3-540-27764-4_18 [Архівовано 2018-06-17 у Wayback Machine.]