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

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

Властивості бінарних відношень:
\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.

Операції з відношеннями[ред.ред. код]

Оскільки відношення на 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−1 також має ту саму властивість. Таким чином, операція обернення зберігає всі ці властивості відношень.

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

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

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

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

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

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

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