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

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

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

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

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

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

повнота


В математиці, бінарне відношення 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, отже, не міг його перемогти.
  • Бінарне відношення , задане на множині називається антитранзитивним, якщо для .


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

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

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

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

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

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

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

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

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