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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

Джерела інформації[ред.ред. код]