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

Властивості бінарних відношень:
$\forall a,b,c\;\in {X}:$

рефлексивність $(aRa)\!$
антирефлексивність $\lnot (aRa)\!$

симетричність $aRb\Rightarrow bRa\!$
асиметричність $aRb\;\Rightarrow \lnot (bRa)$

антисиметричність $aRb\wedge bRa\Rightarrow a=b$

транзитивність $aRb\wedge bRc\Rightarrow aRc$
антитранзитивність $aRb\wedge bRc\Rightarrow \lnot (aRc)$

повнота $aRb\vee bRa\!$

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

Формально:

$\forall a,b,c\in X,\ aRb\land bRc\;\Rightarrow aRc$

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

• Якщо ця умова дотримується не для всіх трійок 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)\;$
• Відношення подібності геометрических фігур
• Бути предком.

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

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

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

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

Джерела

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

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