Изменения

== Определение ==[[Определение отношения|Бинарное отношение ]] <mathtex>R</mathtex> на [[Множества|множестве]] <tex>X</tex> называется ''транзитивным'', если для любых трёх элементов <tex>a, b, c</tex> из выполнения отношений <tex> aRb </tex> и <tex> bRc </tex> следует выполнение отношения <tex> aRc </tex>.{{Определение|definition =Бинарное отношение <tex>R</tex>, заданное на множестве <mathtex>X,</mathtex> называется '''транзитивным'''(англ. ''transitive binary relation''), если для <mathtex>\forall ~a, b, c \in X</math> выполняется <math>\colon ~(aRb, )~ \land ~(bRc ) \Rightarrow ~(aRc)</mathtex>.}}

* Если отношение <mathtex>R</mathtex> транзитивно, то обратное отношение <mathtex>R^{-1}</mathtex> также транзитивно. Пусть <mathtex>aR^{-1}b, ~bR^{-1}c</mathtex>, но по определению обратного отношения <mathtex>cRb, ~bRa</mathtex>. Так как <mathtex>R</mathtex> транзитивно, то <mathtex>cRa</mathtex> и <mathtex>aR^{-1}c</mathtex>, что и требовалось доказать.* Если отношения <mathtex>R, ~S</mathtex> транзитивны, то отношение <mathtex>T ~ = ~R \cap S</mathtex> тразнитивнотранзитивно. Пусть <mathtex>aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc</mathtex>. Из транзитивности <mathtex>R, ~S</mathtex> следует <mathtex>aRc, ~aSc</mathtex>, но из определения пересечения отношений получаем <mathtex>aTc</mathtex>, что и требовалось доказать. == Примеры транзитивных отношений ==* Отношения '''[[Частичный порядок|частичного порядка]]''':** строгое неравенство <tex>\colon ~(a < b), ~(b < c)~ \Rightarrow ~(~a < c)\;</tex>** нестрогое неравенство <tex>\colon ~("\leqslant ")\;</tex>** '''включение подмножества:'''*** строгое подмножество <tex>\colon ~ ("\subset ")\;</tex>*** Из последнего свойства следуетнестрогое подмножество <tex>\colon ~ ("\subseteq ")\;</tex>** '''делимость:''' *** <tex>(a \mid b), ~(b \mid c)~ \Rightarrow ~(a \mid c)\;</tex>*** <tex>(a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;</tex>* '''Равенство''' <tex>\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;</tex>* '''[[Отношение эквивалентности|Эквивалентность]]''' <tex>\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;</tex>* '''Импликация''' <tex>\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;</tex>* '''Параллельность''' <tex>\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;</tex>* Отношение ''подобия'' геометрических фигур* Являться предком == Примеры нетранзитивных отношений ==* Пищевая цепочка: это отношение не всегда является транзитивным (пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву).* ''Быть предпочтительнее чем''. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что пересечение любого количества транзитивных мы предпочтём арбуз апельсину.* Быть другом.* Являться коллегой по работе.* Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: ''Вассал моего вассала {{---}} не мой вассал''.* Быть похожим на другого человека. == Примеры антитранзитивных отношений транзитивно==* Быть сыном (отцом, бабушкой). * Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д. == См. также ==* [[Определение_отношения|Определение отношения]]* [[Транзитивное_замыкание|Транзитивное замыкание]]* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения)]]* [[Транзитивный_остов|Транзитивный остов]]* [[Отношение_порядка|Отношение порядка]]* [[Отношение_эквивалентности|Отношение эквивалентности]] == Источники информации ==* [[wikipedia:Transitive_relation | Wikipedia {{---}} Transitive relation]]* [[wikipedia:Intransitivity | Wikipedia {{---}} Intransivity]]* [[wikipedia:ru:Отношение_эквивалентности | Wikipedia {{---}} Отношение эквивалентности]]* [http://golovolomka.hobby.ru/books/gardner/gotcha/ch5/11.html Парадокс Кондорсе]* [http://sarodom.ru/Statyi/002.htm Отношения на графах]* [http://www.hse.ru/data/2010/11/21/1209059687/intr.doc Развитие понимания транзитивности и нетранзитивности]* [http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm Бинарные отношения.Отношения эквивалентности] (очень хорошая статья про отношения, в ней суть раскрыта более подробно)

== Примеры ==[[Категория: Дискретная математика и алгоритмы]]Следующие отношения являются транзитивными[[Категория:* отношение <math>\le</math> на множестве вещественных чисел* отношение <math>\subset</math> на множестве наборов* отношение параллельности на множестве прямыхОтношения]]