Бінарне відношення
Матеріал з Вікіпедії — вільної енциклопедії.
БІНАРНЕ ВІДНОШЕННЯ, бінарне відношення на множині — в математиці окремий випадок відношення, яке встановлюється між двома елементами множини. Кажуть також, що елементи a1,a2∈M знаходяться у бінарному відношенні R, якщо впорядкована пара (a1,a2)∈R. Тобто, в загальному випадку, R⊆A×B.
В математичній літературі іноді розрізняють поняття бінарного відношення на множині та бінарного відношення між (різними) множинами, яке в цій енциклопедії називається відповідністю між множинами.
Якщо елементи a,b∈M знаходяться в бінарному відношенні R (тобто визначена впорядкована пара (a,b)∈R), то це часто записують у вигляді aRb.
Зміст |
[ред.] Приклади
Приклади бінарних відношень на множині натуральних чисел N:
- R1 — відношення ≤ ("менше або дорівнює"), тоді 4 R1 9, 5 R1 5
- R2 — відношення "ділиться на", тоді 4 R2 2, 49 R2 7, m R2 1 для будь-якого m∈N
- R3 — відношення "є взаємно простими", тоді 15 R3 8, 366 R3 121, 1001 R3 612
- R4 — відношення "складаються з однакових цифр", тоді 127 R4 721, 230 R4 302, 3231 R4 3213311
[ред.] Операції з відношеннями
Оскільки відношення на M є також множинами, то для них означені всі відомі теоретико-множинні операції. Наприклад, перетином бінарних відношень "більше або дорівнює" і "менше або дорівнює" є відношення "дорівнює", об’єднанням відношень "менше" і "більше" є відношення "не дорівнює", доповненням відношення "ділиться на" є відношення "не ділиться на" тощо.
[ред.] Обернене відношення
Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і тільки тоді, коли aRb. Очевидно, що (R-1)-1=R. Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" — відношення "є дільником".
[ред.] Композиція
Композицією відношень R1 і R2 на множині M (позначається R1oR2 ) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент c∈M, для якого виконується aR1c і cR2b. Наприклад, композицією відношень R1 — "є сином" і R2 — "є братом" на множині чоловіків є відношення R1oR2 — "є небожем".
[ред.] Властивості
Нехай R - деяке відношення на множині M.
- Відношення R називається рефлексивним, якщо для всіх a∈M має місце aRa.
- Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного a∈M не виконується aRa.
- Відношення R називається симетричним, якщо для всіх a,b∈M таких, що aRb маємо bRa.
- Відношення R називається антисиметричним, якщо для всіх a,b∈M таких, що aRb і bRa маємо a = b.
- Відношення R називається асиметричним, якщо для всіх a,b∈M таких, що aRb не виконується bRa. "Greater than" is an asymmetric relation, because if x>y then not y>x.
- Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.
- Відношення R називається повним або лінійним, якщо для будь-яких a, b∈M з факту рівності a = b випливає, що aRb або bRa.
Якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R-1 також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.
Відношення, яке є рефлексивним, симетричним та транзитивним, називається відношенням еквівалентності. Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається відношенням часткового порядку. Відношення часткового порядку, яке є лінійним, називається лінійним порядком.
[ред.] Дивись також
- Відношення на множині
- Відповідність між множинами
- Відношення порядку
- Відношення еквівалентності
- Відношення домінування
- Декартів добуток