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

Властивості бінарних відношень:

рефлексивність
антирефлексивність

симетричність
асиметричність

антисиметричність

транзитивність
антитранзитивність

повнота


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

Формально:

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

  • Якщо ця умова дотримується не для всіх трійок a, b, c, то таке відношення називається нетранзитивним. Наприклад, не для всіх трійок   вірно, що  .
  • Бінарне відношення R, задане на множині X називається нетранзитивним, якщо  .

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

  • Існує більш «сильна» властивість — антитранзитивність. Під цим терміном розуміється, що для будь-яких трійок a, b, c відсутня транзитивність. Антитранзитивне відношення, наприклад — відношення перемогти в турнірах «на виліт»: якщо A переміг гравця B, а B переміг гравця C, то A не грав з C, отже, не міг його перемогти.
  • Бінарне відношення  , задане на множині   називається антитранзитивним, якщо для  .


Особливості ред.

  • Якщо відношення   транзитивне, то зворотне відношення   також транзитивне. Нехай   , але за визначенням оберненого відношення  . Так як   транзитивне, то   і  , що й потрібно було довести.
  • Якщо відношення   транзитивні, то відношення   транзитивне. Нехай  . З транзитивності   слідує  , але з визначення перетину відносин отримуємо  , що й потрібно було довести.

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

  • Відношення часткового порядку:
    • строга нерівність  
    • нестрога нерівність  
    • включення підмножини:
      • строга підмножина  
      • нестрога підмножина  
    • подільність:
      •  
      •  
  • Рівність  
  • Еквівалентність  
  • Імплікація  
  • Паралельність  
  • Відношення подібності геометрических фігур
  • Бути предком.

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

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

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

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

Джерела ред.