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

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

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

Формально:

\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)\;$
Відношення подібності геометрических фігур
Бути предком.

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

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

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

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

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.