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

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

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

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

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

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

повнота $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

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

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

• R₁ — відношення $\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.
• Шахівниця. Множина $A=\{1,2,3,4,5\}.$ На декартовому добутку $A\times A$ задано відношення $R=\{(a,b)|\,a,b\in A,(a b)\equiv 0{\pmod {2}}\}.$ Відношення $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. Приклади рефлексивних відношень: рівність, одночасність, подібність.
• корефлексивним, якщо будь-які два елементи $(a,b)$ множини $X$, що перебувають у відношенні $(a,b)\in R$ (що записують ще як $aRb$), збігаються $a=b$.
• антирефлексивним (іррефлексивним), якщо для жодного 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 $\neq$ b, маємо що bRa — не виконується. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR — 1y випливає х = у (тобто R і R⁻¹ виконуються одночасно лише для рівних між собою членів).
• транзитивним, якщо зі співвідношень aRb і bRc випливає aRc. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz випливає xRz (xRy & $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.(рос.)