Транзитивне відношення

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

В математиці, бінарне відношення R на множині X є транзитивним, якщо для будь-яких a, b, та c з X, виконується: коли a відноситься до b і b відноситься до c, то a відноситься до c.

Формально:

$\forall a, b, c \in X,\ a R b \and b R c \; \Rightarrow a R c$

Нетранзитивне відношення

• Якщо ця умова дотримується не для всіх трійок a, b, c, то таке відношення називається нетранзитивним. Наприклад, не для всіх трійок $a, b, c \in \mathbb{N}$ вірно, що $~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c)$.
• Бінарне відношення R, задане на множині X називається нетранзитивним, якщо $\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \land ~\neg(aRc)$.

Антитранзитивне відношення

• Існує більш «сильна» властивість — антитранзитивність. Під цим терміном розуміється, що для будь-яких трійок a, b, c відсутня транзитивність. Антитранзитивне відношення, наприклад — відношення перемогти в турнірах «на виліт»: якщо A переміг гравця B, а B переміг гравця C, то A не грав з C, отже, не міг його перемогти.
• Бінарне відношення $R$, задане на множині $X,$ називається антитранзитивним, якщо для $\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)$.

Особливості

• Якщо відношення $R$ транзитивне, то зворотне відношення $R^{-1}$ також транзитивне. Нехай $aR^{-1}b, ~bR^{-1}c$ , але за визначенням оберненого відношення $cRb, ~bRa$. Так як $R$ транзитивне, то $cRa$ і $aR^{-1}c$, що й потрібно було довести.
• Якщо відношення $R, ~S$ транзитивні, то відношення $T~ = ~R \cap S$ транзитивне. Нехай $aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc$. З транзитивності $R, ~S$ слідує $aRc, ~aSc$, але з визначення перетину відносин отримуємо $aTc$, що й потрібно було довести.

Приклади транзитивних відношень

• Відношення часткового порядку:
  • строга нерівність $\colon ~(a < b), ~(b < c)~ \Rightarrow ~(~a < c)\;$
  • нестрога нерівність $\colon ~(a <= b), ~(b <= c)~ \Rightarrow ~(~a <= c)\;$
  • включення підмножини:
    • строга підмножина $(A \subset B \ ; and ; B \subset C ) \Rightarrow ( A \subset C )$
    • нестрога підмножина $(A \subseteq B \ ; and ; B \subseteq C ) \Rightarrow ( A \subseteq C )$
  • подільність:
    • $(a \mid b), ~(b \mid c)~ \Rightarrow ~(a \mid c)\;$
    • $(a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;$
• Рівність $\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;$
• Еквівалентність $\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;$
• Імплікація $\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;$
• Паралельність $\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;$
• Відношення подібності геометрических фігур
• Бути предком.

Приклади нетранзитивних відношень

• Харчовий ланцюжок: це відношення не завжди є транзитивним (приклад — вовки їдять оленів, олені їдять траву, але вовки не їдять траву).
• Бути переважніше ніж. Якщо ми хочемо яблуко замість апельсина, а замість яблука ми б хотіли кавун, то це не значить, що ми віддамо перевагу кавуну.
• Бути другом.
• Бути колегою по роботі.
• Бути підлеглим. Наприклад, у часи феодального ладу в Західній Європі була в ходу приказка: «Васал мого васала — не мій васал».
• Бути схожим на іншу людину.

Приклади антитранзитивних відношень

• Бути сином (батьком, бабусею).
• Гра «Камінь, ножиці, папір». Камінь перемагає ножиці, ножиці виграють у паперу, але камінь програє паперові і т. д.

Джерела інформації

• Транзитивное отношение