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

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

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

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

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

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

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

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

Формально:

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

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

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

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

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

Особливості

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

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

• Відношення часткового порядку:
  • строга нерівність ${\displaystyle \colon ~(a<b),~(b<c)~\Rightarrow ~(~a<c)\;}$
  • нестрога нерівність ${\displaystyle \colon ~(a<=b),~(b<=c)~\Rightarrow ~(~a<=c)\;}$
  • включення підмножини:
    • строга підмножина ${\displaystyle (A\subset B\ ;and;B\subset C)\Rightarrow (A\subset C)}$
    • нестрога підмножина ${\displaystyle (A\subseteq B\ ;and;B\subseteq C)\Rightarrow (A\subseteq C)}$
  • подільність:
    • ${\displaystyle (a\mid b),~(b\mid c)~\Rightarrow ~(a\mid c)\;}$
    • ${\displaystyle (a\,\vdots \,b),~(b\,\vdots \,c)~\Rightarrow ~(a\,\vdots \,c)\;}$
• Рівність ${\displaystyle \colon ~(a=b),~(b=c)\Rightarrow ~(a=c)\;}$
• Еквівалентність ${\displaystyle \colon ~(a\Leftrightarrow b),~(b\Leftrightarrow c)~\Rightarrow ~(a\Leftrightarrow c)\;}$
• Імплікація ${\displaystyle \colon ~(a\Rightarrow b),~(b\Rightarrow c)~\Longrightarrow ~(a\Rightarrow c)\;}$
• Паралельність ${\displaystyle \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.(рос.)