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

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

• R₁ — відношення ≤ ("менше або дорівнює"), тоді 4 R₁ 9 та 5 R₁ 5.
• R₂ — відношення "ділиться на", тоді 4 R₂ 2, 49 R₂ 7, m R₂ 1 для будь-якого m∈N.
• R₃ — відношення "є взаємно простими", тоді 15 R₃ 8, 366 R₃ 121, 1001 R₃ 612.
• R₄ — відношення "складаються з однакових цифр", тоді 127 R₄ 721, 230 R₄ 302, 3231 R₄ 3213311.

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

Оскільки відношення на M є також множинами, то над ними дозволені теоретико-множинні операції. Наприклад:

• перетином бінарних відношень "більше або дорівнює" і "менше або дорівнює" є відношення "дорівнює",
• об’єднанням відношень "менше" і "більше" є відношення "не дорівнює",
• доповненням відношення "ділиться на" є відношення "не ділиться на" тощо.

Обернене відношення

Відношення R⁻¹ називається оберненим до відношення R, якщо bR⁻¹a тоді і тільки тоді, коли aRb. Очевидно, що (R⁻¹)⁻¹=R.

Наприклад, для відношення "більше або дорівнює" оберненим є відношення "менше або дорівнює", для відношення "ділиться на" — відношення "є дільником".

Композиція

Композицією відношень R₁ і R₂ на множині M (позначається R1oR2 ) називається відношення R на M таке, що aRb тоді і тільки тоді, коли існує елемент c∈M, для якого виконується aR1c і cR2b.

Наприклад, композицією відношень R₁ — "є сином" і R₂ — "є братом" на множині чоловіків є відношення R₁oR₂ — "є небожем".

Властивості

Нехай R — деяке відношення на множині M. Відношення R називається

• рефлексивним, якщо для всіх a∈M має місце aRa.
• антирефлексивним (іррефлексивним), якщо для жодного a∈M не виконується aRa.
• симетричним, якщо для всіх a,b∈M таких, що aRb маємо bRa.
• асиметричним, якщо для всіх a,b∈M таких, що aRb не виконується bRa.
• антисиметричним, якщо для всіх a,b∈M таких, що aRb і bRa маємо a = b.
• транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.
• повним, якщо для будь-яких a,b∈M випливає, що aRb або bRa.

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

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

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

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

Властивості відношень за назвами

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

Див. також

• Відношення на множині
• Відповідність між множинами
• Відношення порядку
• Відношення еквівалентності
• Відношення домінування

Джерела

• Куратовский К., Мостовский А. (1970). Теория множеств. Москва: Мир. с. 416. 
• Хаусдорф Ф. (1937). Теория множеств. Москва, Ленинград: ОНТИ. с. 304. ISBN 978-5-382-00127-2.