Бінарне відношення
Бінарне відношення (бінарне відношення на множині) — в математиці окремий випадок відношення заданого на множині M, яке встановлюється між двома елементами множини. Іншими словами, це підмножина декартового квадрата M2 = M × M.
Також кажуть, що елементи a, b ∈ M перебувають у бінарному відношенні R (часто записують у вигляді aRb), якщо впорядкована пара (a, b) ∈ R і записують, що R ⊆ M×M.
Взагалі, бінарне відношення між двома множинами A і B — це підмножина A × B. В цьому випадку вживають термін відповідність між множинами. Термін 2-місне відношення або 2-арне відношення є синонімами бінарного відношення.
В деяких системах аксіом теорії множин, відношення розширюються до класів, які є узагальненнями множин. Таке розширення потрібне, зокрема для того, щоб формалізувати поняття «є елементом» або «є підмножиною» теорії множин і запобіганню таких невідповідностей, як парадокс Расселла.
Приклади бінарних відношень на множині натуральних чисел :
- R1 — відношення («менше або дорівнює»), тоді 4 R1 9 та 5 R1 5.
- R2 — відношення «ділиться на», тоді 4 R2 2, 49 R2 7, m R2 1 для будь-якого натурального m.
- R3 — відношення «є взаємно простими», тоді 15 R3 8, 366 R3 121, 1001 R3 612.
- R4 — відношення «складаються з однакових цифр», тоді 127 R4 721, 230 R4 302, 3231 R4 3213311.
- Шахівниця. Множина На декартовому добутку задано відношення Відношення задає на шаховій дошці чорні клітини — клітини у яких сума координат буде парним числом.
- Рефлексивне транзитивне відношення називається відношенням квазіпорядку.
- Рефлексивне симетричне транзитивне відношення називається відношенням еквівалентності.
- Рефлексивне антисиметричне транзитивне відношення називається відношенням (часткового) порядку.
- Антирефлексивне антисиметричне транзитивне відношення називається відношенням строгого порядку.
- Повне антисиметричне (для будь-яких x, y виконується xRy або yRx) транзитивне відношення називається відношенням лінійного порядку.
- Антирефлексивне антисиметричне відношення називається відношенням домінування.
Оскільки відношення на 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 називається:
- оберненим (відношення, обернене до R), якщо воно складається з пар елементів (у, х), отриманих перестановкою пар елементів (х, у) даного відношення R. Позначається: R−1. Для даного відношення і оберненого до нього виконується рівність: (R−1)−1 = R.
- взаємообернені відношення — відношення, що є оберненими одне до одного. Область значень одного з них служить областю визначення іншого, а область визначення першого — областю значень іншого.
- рефлексивним, якщо для всіх a ∈ M має місце aRa. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-якого х цієї множини елемент х перебуває у відношенні R до самого себе, тобто для будь-якого елемента х цієї множини має місце xRx. Приклади рефлексивних відношень: рівність, одночасність, подібність.
- корефлексивним, якщо будь-які два елементи множини , що перебувають у відношенні (що записують ще як ), збігаються [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 b, маємо що bRa — не виконується. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR — 1y випливає х = у (тобто R і R−1 виконуються одночасно лише для рівних між собою членів).
- транзитивним, якщо зі співвідношень aRb і bRc випливає aRc. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz випливає xRz (xRy & ). Приклади транзитивних відношень: «більше», «менше», «дорівнює», «подібно», «вище», «північніше».
- нетранзитивним, якщо для будь-яких х, у, 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 також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.
Відношення, яке є рефлексивним, симетричним та транзитивним, називається відношенням еквівалентності.
З поняттям відношення еквівалентності тісно пов'язане поняття розбиття.
Теорема 1. Відношення Е є відношенням еквівалентності на множині R тоді й лише тоді, коли воно визначає розбиття ПЕ на множині R.
[ред. | ред. код]Доведення.
а) Пряме. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що означає, що належать одній і тій ж підмножині Ri розбиття П. Тоді відношення Е(П) — рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду для кожного симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду то включаємо і пару вигляду, транзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду, то включаємо і пару вигляду Таким чином, відношення Е(П) — відношення еквівалентності.
б) Обернене. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію котра елементу ri ставить у відповідність підмножину Тому що відношення Е рефлексивне, то а отже Залишається показати, що будь-які дві підмножини або не перетинаються, або є рівними. Нехай це не так і є загальний елемент але підмножини і не рівні. Але тоді справедливо В силу симетричності відношення E, якщо виконується то виконується За наявності в відношенні E пар в силу транзитивності відношення E в ньому присутня пара З того, що для будь-якого справедливо і, отже, в силу транзитивності справедливо слідує, що Помінявши місцями елементи аналогічно встановлюємо справедливість Але це означає Іншими словами, будь-які підмножини або не перетинаються, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовольняють другому обмеженню на розбиття. Теорема доведена.
Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається відношенням часткового порядку.
Відношення часткового порядку, яке є повним, називається відношенням лінійного порядку (чи лінійним порядком).
Назва | рефлексивність | антирефлексивність | симетричність | асиметричність | антисиметричність | транзитивність | повнота |
---|---|---|---|---|---|---|---|
Перевага | + | ||||||
Подібність (толерантність) | + | + | |||||
Еквівалентність | + | + | + | ||||
Часткова еквівалентність | + | + | |||||
Квазіпорядок | + | + | |||||
Впорядкування | + | + | + | ||||
Частковий порядок | + | + | + | ||||
Лінійний порядок | + | + | + | + | |||
Строгий квазіпорядок | + | + | |||||
Строгий порядок | + | + | (+) | + | |||
Домінування | + | + | (+) | ||||
Строгий частковий порядок | + | + | (+) | + | |||
Строгий лінійний порядок | + | + | (+) | + | + |
Для того, щоб задати відношення (R, Ω), необхідно задати всі пари елементів (x, y)∈Ω×Ω, які включено в множину R. Крім повного переліку всіх пар, існують три способи задання відношень: за допомогою матриці, графу й розрізів. Перші два способи застосовують, щоб задати відношення на скінченних множинах, задання відношення розрізами може бути застосовано й до нескінченних множин.
Нехай множина Ω складається з n елементів, R– подане на цій множині бінарне відношення. Пронумеруємо елементи множини Ω цілими числами від 1 до n. Для того, щоб задати відношення, побудуємо квадратну таблицю розміром n×n. Її i-й рядок відповідає елементу xi множини Ω, j-й стовпчик — елементу xj з множини Ω. На перетині i-го рядка та j-го стовпчика ставимо 1, якщо елемент xi перебуває у відношенні R з елементом xj , і нуль в інших випадках.
Для того, щоб задати відношення за допомогою графу, поставимо у взаємно однозначну відповідність елементам скінченної множини Ω, на якій визначено відношення, вершини графу x1,…,xn (за будь-якою нумерацією).
Провести дугу від вершини xi до xj, можна тоді й тільки тоді, коли елемент xi перебуває у відношенні R з елементом xj, коли ж i = j, то дуга (xi,xj) перетворюється на петлю при вершині xi.
Верхнім розрізом відношення (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.(рос.)
- ↑ 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.]