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

Матеріал з Вікіпедії — вільної енциклопедії.

БІНАРНЕ ВІДНОШЕННЯ, бінарне відношення на множині — в математиці окремий випадок відношення, яке встановлюється між двома елементами множини. Кажуть також, що елементи a1,a2M знаходяться у бінарному відношенні R, якщо впорядкована пара (a1,a2)∈R. Тобто, в загальному випадку, RA×B.

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

Якщо елементи a,bM знаходяться в бінарному відношенні 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.

  1. Відношення R називається рефлексивним, якщо для всіх aM має місце aRa.
  2. Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного a∈M не виконується aRa.
  3. Відношення R називається симетричним, якщо для всіх a,b∈M таких, що aRb маємо bRa.
  4. Відношення R називається антисиметричним, якщо для всіх a,b∈M таких, що aRb і bRa маємо a = b.
  5. Відношення R називається асиметричним, якщо для всіх a,b∈M таких, що aRb не виконується bRa. "Greater than" is an asymmetric relation, because if x>y then not y>x.
  6. Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.
  7. Відношення R називається повним або лінійним, якщо для будь-яких a, b∈M з факту рівності a = b випливає, що aRb або bRa.

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

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

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