Перегляд вихідного коду сторінки Бінарне відношення

{{Властивості бінарних відношень}}
'''Бінарне відношення''' (''бінарне відношення на множині'')&nbsp;— в [[математика|математиці]] окремий випадок [[відношення]] заданого на [[Множина|множині]] ''M'', яке встановлюється між двома елементами множини. Іншими словами, це [[підмножина]] [[Декартів добуток множин|декартового квадрата]] ''M''<sup>2</sup> = {{nowrap|''M'' × ''M''}}.

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

Взагалі, бінарне відношення між двома множинами ''A'' і ''B''&nbsp;— це підмножина {{nowrap|''A'' × ''B''}}. В цьому випадку вживають термін ''[[відповідність між множинами]]''. Термін ''2-місне відношення'' або ''2-[[Арність|арне]] відношення'' є синонімами бінарного відношення.

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

== Приклади ==
{{Шахова діаграма 5x5
| tright
| Шахова дошка 5x5
|= 
 5 |__|__|__|__|__|=
 4 |__|__|__|__|__|=
 3 |__|__|__|__|__|=
 2 |__|__|__|__|__|=
 1 |__|__|__|__|__|=
 a  b  c  d  e 
| У чорних клітин сума координат&nbsp;— парне число.
}}
Приклади бінарних відношень на множині [[Натуральні числа|натуральних чисел]] <math>\N</math>:
* R<sub>1</sub>&nbsp;— відношення <math>\leqslant</math> («менше або дорівнює»), тоді 4 R<sub>1</sub> 9 та 5 R<sub>1</sub> 5.
* R<sub>2</sub>&nbsp;— відношення «ділиться на», тоді 4 R<sub>2</sub> 2, 49 R<sub>2</sub> 7, m R<sub>2</sub> 1 для будь-якого натурального m.
* R<sub>3</sub>&nbsp;— відношення «є взаємно простими», тоді 15 R<sub>3</sub> 8, 366 R<sub>3</sub> 121, 1001 R<sub>3</sub> 612.
* R<sub>4</sub>&nbsp;— відношення «складаються з однакових цифр», тоді 127 R<sub>4</sub> 721, 230 R<sub>4</sub> 302, 3231 R<sub>4</sub> 3213311.
* [[Шахівниця]]. Множина <math>A=\{1,2,3,4,5 \}.</math> На декартовому добутку <math>A\times A</math> задано відношення <math>R=\{(a,b)| \, a,b \in A, (a+b) \equiv 0 \pmod {2} \}.</math> Відношення <math>R</math> задає на шаховій дошці чорні клітини&nbsp;— клітини у яких сума координат буде парним числом.

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

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

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

Оскільки відношення на ''M'' є також множинами, то над ними дозволені [[теоретико-множинні операції]]. Наприклад:
* [[перетин множин|перетином]] бінарних відношень «більше або дорівнює» і «менше або дорівнює» є відношення «дорівнює»,
* [[об'єднання множин|об'єднанням]] відношень «менше» і «більше» є відношення «не дорівнює»,
* [[різниця множин|доповненням]] відношення «ділиться на» є відношення «не ділиться на» тощо.

== Обернене відношення ==
{{main|Обернене відношення}}
Відношення ''R''<sup>−1</sup> називається '''оберненим''' до відношення ''R'', якщо ''b''R<sup>−1</sup>''a'' [[тоді і тільки тоді]], коли ''a''R''b''. Очевидно, що (''R''<sup>−1</sup>)<sup>−1</sup>=''R''.

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

== Композиція ==
'''Композицією відношень''' ''R''<sub>1</sub> і ''R''<sub>2</sub> на множині ''M'' (позначається ''R''<sub>1</sub>o''R''<sub>2</sub>) називається відношення ''R'' на ''M'' таке, що ''a''R''b'' тоді і тільки тоді, коли існує елемент c∈M, для якого виконується ''a''R<sub>1</sub>''c'' і ''c''R<sub>2</sub>''b''.

Наприклад, композицією відношень ''R''<sub>1</sub>&nbsp;— «є сином» і ''R''<sub>2</sub>&nbsp;— «є братом» на множині чоловіків є відношення ''R''<sub>1</sub>o''R''<sub>2</sub>&nbsp;— «є небожем».

== Властивості ==
Нехай R&nbsp;— деяке відношення на множині M. Відношення R називається:
* [[Обернене відношення|'''оберненим''']] (відношення, обернене до R), якщо воно складається з пар елементів (у, х), отриманих перестановкою пар елементів (х, у) даного відношення R. Позначається: ''R''<sup>−1</sup>. Для даного відношення і оберненого до нього виконується рівність: &nbsp;(''R''<sup>−1</sup>)<sup>−1</sup> = R.
** '''взаємообернені відношення'''&nbsp;— відношення, що є оберненими одне до одного. Область значень одного з них служить областю визначення іншого, а область визначення першого&nbsp;— областю значень іншого.
* '''[[рефлексивне відношення|рефлексивним]]''', якщо для всіх ''a'' ∈ M має місце ''a''R''a''. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого х цієї множини елемент х перебуває у відношенні R до самого себе, тобто для будь-якого елемента х цієї множини має місце xRx. Приклади рефлексивних відношень: рівність, одночасність, подібність.
* [[корефлексивне відношення|корефлексивним]], якщо будь-які два елементи <math>(a,b)</math> множини <math>X</math>, що перебувають у відношенні <math>(a,b)\in R</math> (що записують ще як <math>aRb</math>), збігаються <math>a=b</math><ref>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 {{Webarchive|url=https://web.archive.org/web/20180617183744/https://link.springer.com/chapter/10.1007%2F978-3-540-27764-4_18 |date=2018-06-17 }}</ref>.
* '''[[антирефлексивне відношення|антирефлексивним]]''' ('''іррефлексивним'''), якщо для жодного ''a'' ∈ M не виконується ''a''R''a''. Відзначимо, що так само, як антисиметричність не збігається з несиметричністю, іррефлексівність не збігається з нерефлексивністю. Двомісне відношення R, визначене на деякій множині M і відрізняється тим, що для будь-якого елемента х цієї множини не виконується, що воно перебуває у відношенні R до самого себе (відсутнє xRx), тобто можливий випадок, що елемент множини не перебуває у відношенні R до самого себе. Приклади нерефлексивних відношень: «дбати про», «розважати», «нервувати».
* '''[[симетричне відношення|симетричним]]''', якщо для всіх ''a, b''∈ M таких, що ''a''R''b'' маємо ''b''R''a''. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких елементів х і у цієї множини з того, що х перебуває до у відношенні R (xRy), випливає, що й у перебуває в тому ж відношенні до х (yRx). Прикладами симетричних відношень є рівність (=), відношення еквівалентності, подібності, одночасності, деякі відношення споріднення.
[[Файл:Роплрол7.GIF|міні|Симетричне відношення]]
* '''[[асиметричне відношення|асиметричним]]''', якщо для всіх ''a, b''∈ M таких, що ''a''R''b'' не виконується ''b''R''a''. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy слідує заперечення yRx. Приклад: відношення «більше» (>) і «менше» (<).
* '''[[антисиметричне відношення|антисиметричним]]''', якщо для всіх ''a, b''∈ M таких, що ''a''R''b'' і a <math>\ne</math> b, маємо що ''b''R''a''&nbsp;— не виконується. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR&nbsp;— 1y випливає х = у (тобто R і R<sup>−1</sup> виконуються одночасно лише для рівних між собою членів).
* '''[[транзитивне відношення|транзитивним]]''', якщо зі співвідношень ''a''R''b'' і ''b''R''c'' випливає ''a''R''c''. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz випливає xRz (xRy & <math>yRz \to xRz</math>). Приклади транзитивних відношень: «більше», «менше», «дорівнює», «подібно», «вище», «північніше».
* '''нетранзитивним''', якщо для будь-яких х, у, z із множини, на якій визначено відношення, з xRy і yRz не випливає xRz. Приклад нетранзитивного відношення: «x батько y».
* '''[[повне відношення|повним]]''', якщо для будь-яких ''a, b'' ∈ M випливає, що ''a''R''b'' або ''b''R''a''.
* '''відношенням порядку''', якщо воно володіє тільки деякими з трьох властивостей відношення еквівалентності. Зокрема, відношення рефлексивне і транзитивне, але несиметричне (наприклад, «не більше») утворює «нестрогий» порядок. Відношення транзитивне, але нерефлексивне і несиметричне (наприклад, «менше»)&nbsp;— «строгий» порядок.
* [[Функція (математика)|'''функцією''']], якщо кожному значенню x відношення xRy відповідає лише одне&nbsp;— єдине значення y. Приклад: «y батько x». Властивість функціональності відношення R записується у вигляді аксіоми: (xRy і xRz) → (y ≡ z). Оскільки кожному значенню x у виразах xRy і xRz відповідає одне і те ж значення, то y і z збіжаться, виявляться одними і тими ж. Функціональне відношення однозначне, оскільки кожному значенню x відношення xRy відповідає єдине значення y, але не навпаки.
* [[Бієкція|'''бієкцією''']], якщо кожному значенню х відповідає єдине значення у, і кожному значенню у відповідає єдине значення х.
* '''відношенням зв'язку''', якщо для будь-яких двох різних елементів х та у із множини, на якій визначено відношення, одне з них перебуває у відношенні R до іншого (тобто виконано одне з двох співвідношень: xRy або yRx). Приклад: відношення «менше» (<).

Якщо відношення ''R'' має будь-яку з перерахованих вище властивостей, то обернене відношення R<sup>−1</sup> також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.

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

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

==== ''Теорема 1''.&nbsp;Відношення Е є відношенням еквівалентності на множині R тоді й лише тоді, коли воно визначає розбиття П<sub>Е&nbsp;</sub>на множині R. ====
'''''Доведення'''''.&nbsp;

'''а) Пряме'''. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що&nbsp;означає, що належать одній і тій ж підмножині R<sub>i</sub> розбиття П. Тоді відношення Е(П)&nbsp;— рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду для кожного симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду  то включаємо і пару вигляду, транзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду, то включаємо і пару вигляду  Таким чином, відношення Е(П)&nbsp;— відношення еквівалентності.

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

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

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

=== Властивості відношень за назвами ===
{|class="wikitable"
! Назва !! [[рефлексивність]] !! [[антирефлексивність]] !! [[симетричне відношення|симетричність]] !! [[асиметричне відношення|асиметричність]] !! [[антисиметричне відношення|антисиметричність]] !! [[транзитивність]] !! [[повне відношення|повнота]]
|-
| Перевага || + || || || || || ||
|-
| [[Відношення толерантності|Подібність (толерантність)]] || + || || + || || || ||
|-
| [[Відношення еквівалентності|Еквівалентність]] || + || || + || || || + ||
|-
| [[Частково еквівалентне відношення|Часткова еквівалентність]] || || || + || || || + ||
|-
| [[Передпорядок|Квазіпорядок]] || + || || || || || + ||
|-
| Впорядкування || + || || || || || + || +
|-
| [[Частковий порядок]] || + || || || || + || + ||
|-
| [[Лінійний порядок]] || + || || || || + || + || +
|-
| Строгий квазіпорядок ||  || + || || || || + ||
|-
| Строгий порядок ||  || + || || + || (+) || + ||
|-
| Домінування ||  || + || || + || (+) || ||
|-
| Строгий частковий порядок ||  || + || || + || (+) || + ||
|-
| Строгий лінійний порядок ||  || + || || + || (+) || + || +
|}


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

=== Задання відношення за допомогою матриці ===
Нехай множина Ω складається з ''n'' елементів, ''R''– подане на цій множині бінарне відношення. Пронумеруємо елементи множини Ω цілими числами від 1 до ''n''. Для того, щоб задати відношення, побудуємо квадратну таблицю розміром ''n×n''. Її ''i''-й рядок відповідає елементу ''x''<sub>''i''</sub> множини Ω, ''j''-й стовпчик&nbsp;— елементу ''x''<sub>''j''</sub> з множини Ω. На перетині ''i''-го рядка та ''j''-го стовпчика ставимо 1, якщо елемент ''x''<sub>''i''</sub> перебуває у відношенні R з елементом ''x''<sub>''j''</sub> , і нуль в інших випадках.

=== Задання відношення за допомогою графу ===
Для того, щоб задати відношення за допомогою графу, поставимо у взаємно однозначну відповідність елементам скінченної множини Ω, на якій визначено відношення, вершини графу ''x''<sub>''1''</sub>,…,''x''<sub>''n''</sub> (за будь-якою нумерацією).

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

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

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

Отже, верхній розріз (множина ''R''<sup>+</sup>) являє собою множину всіх таких елементів ''y'', що перебувають у відношенні ''R'' з фіксованим елементом ''х(yRx)''. Нижній розріз (множина ''R''<sup>-</sup>)&nbsp;— це множина всіх таких елементів у, з якими фіксований елемент х перебуває у відношенні ''R(xRy)''.

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

== Див. також ==
* [[Відношення на множині]]
* [[Відповідність між множинами]]
* [[Відношення порядку]]
* [[Відношення еквівалентності]]
* [[Відношення домінування]]
* [[Евклідове відношення]]

== Примітки ==
{{reflist}}

== Джерела ==
* {{Куратовский.Мостовский.Теория множеств}}
* {{Хаусдорф.Теория множеств}}

{{Теорія порядку|state=expanded}}

[[Категорія:Математичні відношення]]
[[Категорія:Теорія множин]]
[[Категорія:Дискретна математика]]
[[Категорія:Бінарні відношення]]