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

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

Властивості бінарних відношень:
$\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\!$

Також кажуть, що елементи 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 ∈ M не виконується aRa. Відзначимо, що так само, як антисиметричність не збігається з несиметричною, іррефлексівність не збігається з нерефлексивним. Двомісне відношення R, визначене на деякій множині M і відрізняється тим, що для будь-якого елемента х цієї множини не виконується, що воно знаходиться у відношенні R до самого себе (відсутнє xRx), тобто можливий випадок, що елемент множини не знаходиться у відношенні R до самого себе. Приклади нерефлексивних відносин: «дбати про», «розважати», «нервувати».
симетричним, якщо для всіх a, b∈ M таких, що aRb маємо bRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких елементів х і у цієї множини з того, що х знаходиться до у відносно R (xRy), випливає, що і у знаходиться в тому ж відношенні до х (уRx). Прикладом симетричних відносин можуть бути рівність (=), відношення еквівалентності, подібності, одночасності, деякі відносини споріднення.

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

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

Нетранзитивне — бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz не слідує xRz. Приклад нетранзитивного відношення: «x батько y».

Повним, якщо для будь-яких a, b ∈ M випливає, що aRb або bRa.

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

Функція — бінарне відношення R, визначене на деякій множині, яке відрізняється тим, що кожному значенню x відносини xRy відповідає лише одне — єдине значення y. Приклад: «y батько x». Властивість функціональності відносини R записується у вигляді аксіоми: (xRy і xRz) → (y ≡ z). Оскільки кожному значенню x у виразах xRy і xRz відповідає одне і те ж значення, то y і z збіжаться, виявляться одними і тими ж. Функціональне відношення однозначне, оскільки кожному значенню x відносини xRy відповідає лише одне — єдине значення y, але не навпаки.

Бієкція — бінарне відношення R, визначене на деякій множині, яке відрізняється тим, що в ньому кожному значенню х відповідає єдине значення у, і кожному значенню у відповідає єдине значення х.

Відношення зв'язку — це бінарне відношення R, визначене на деякій множині, яке відрізняється тим, що для будь-яких двох різних елементів х та у з цієї множини, одне з них знаходиться у відношенні 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).

Див. також

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.