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

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

Властивості бінарних відношень:
\forall a,b,c \; \in{X}:

рефлексивність (a R a) \!
антирефлексивність \lnot(a R a) \!

симетричність a R b \Rightarrow b R a \!
асиметричність a R b \; \Rightarrow \lnot(b R a)

антисиметричність a R b \wedge b R a \Rightarrow a=b
транзитивність a R b \wedge b R c \Rightarrow a R c
антитранзитивність a R b \wedge b R c \Rightarrow \lnot(a R c)

повнота a R b \vee b R a \!


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

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

Іноді розрізняють поняття бінарного відношення на множині та бінарного відношення між множинами, яке в цій енциклопедії називається відповідністю між множинами.


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

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

  • R1 — відношення \leqslant («менше або дорівнює»), тоді 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.
  • Взаємообернене відношення - відносини, що є зворотними один по відношенню до одного. Область значень одного з них служить областю визначення іншого , а область визначення першого - областю значень іншого.

Бінарне відношення R , визначене на деякій множині і відрізняється тим , що для будь-якого х цієї множини елемент х знаходиться у відношенні R до самого себе , тобто для будь-якого елемента х цієї множини має місце xRx . Приклади рефлексивних відносин : рівність , одночасність , подібність.

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

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

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

Властивості відношень за назвами[ред.ред. код]

Назва рефлексивність антирефлексивність симетричність асиметричність антисиметричність транзитивність повнота
Перевага +
Подібність (толерантність) + +
Еквівалентність + + +
Часткова еквівалентність + +
Квазіпорядок + +
Впорядкування + + +
Частковий порядок + + +
Лінійний порядок + + + +
Строгий квазіпорядок + +
Строгий порядок + + +
Домінування + +
Строгий частковий порядок + + +
Строгий лінійний порядок + + + +

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

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