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

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

Формально:

$\mathrm{\forall }a,b,c\in X,aRb\wedge bRc\Rightarrow aRc$

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

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

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

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

Особливості

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

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

• Відношення часткового порядку:
  • строга нерівність $:(a<b),(b<c)\Rightarrow (a<c)$
  • нестрога нерівність $:(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⋮b),(b⋮c)\Rightarrow (a⋮c)$
• Рівність $:(a=b),(b=c)\Rightarrow (a=c)$
• Еквівалентність $:(a\iff b),(b\iff c)\Rightarrow (a\iff c)$
• Імплікація $:(a\Rightarrow b),(b\Rightarrow c)⟹(a\Rightarrow c)$
• Паралельність $:(a\parallel b),(b\parallel c)\Rightarrow (a\parallel c)$
• Відношення подібності геометрических фігур
• Бути предком.

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

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

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

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

Джерела

• Шаблон:Куратовский.Мостовский.Теория множеств
• Шаблон:Хаусдорф.Теория множеств