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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Властивості бінарних відношень:

рефлексивність
антирефлексивність

симетричність
асиметричність

антисиметричність
транзитивність
антитранзитивність

повнота

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

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

Взагалі, бінарне відношення між двома множинами A і B — це підмножина A × B. В цьому випадку вживають термін відповідність між множинами. Термін 2-місне відношення або 2-арне відношення є синонімами бінарного відношення.

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

Приклади[ред.ред. код]

Шахова дошка 5x5
a5 b5 c5 d5 e5
a4 b4 c4 d4 e4
a3 b3 c3 d3 e3
a2 b2 c2 d2 e2
a1 b1 c1 d1 e1
У чорних клітин сума координат — парне число.

Приклади бінарних відношень на множині натуральних чисел :

  • 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 . Приклади рефлексивних відносин: рівність, одночасність, подібність.

  • антирефлексивним (іррефлексивним), якщо для жодного 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 і bRa маємо a = b. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х та у з xRy і xR — 1y слід х = у (тобто R і R−1 виконуються одночасно лише для рівних між собою членів).
  • транзитивним, якщо зі співвідношень aRb і bRc випливає aRc. Бінарне відношення R, визначене на деякій множині і відрізняється тим, що для будь-яких х, у, z цієї множини з xRy і yRz слід xRz (xRy & yRz \ toxRz). Приклади транзитивних відносин: «більше», «менше», «дорівнює», «подібно», «вище», «північ».
  • Нетранзитивне — бінарне відношення 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 також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.

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

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

Теорема 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).

Див. також[ред.ред. код]

Джерела[ред.ред. код]