Изменения

== Определение ==[[Определение отношения|Бинарное отношение ]] <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 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>, что и требовалось доказать.* Если отношения <tex>R, ~S</tex> транзитивны, то отношение <tex>T~ = ~R \cap S</tex> транзитивно. Пусть <tex>aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc</tex>. Из транзитивности <tex>R, ~S</tex> следует <tex>aRc, ~aSc</tex>, но из определения пересечения отношений получаем <tex>aTc</tex>, что и требовалось доказать. == Примеры транзитивных отношений ==* Отношения '''[[Частичный порядок|частичного порядка]]''':** строгое неравенство <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>* Отношение ''подобия'' геометрических фигур* Являться предком == Примеры нетранзитивных отношений ==* Пищевая цепочка: это отношение не всегда является транзитивным (пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву).* ''Быть предпочтительнее чем''. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз апельсину.* Быть другом.* Являться коллегой по работе.* Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: ''Вассал моего вассала {{---}} не мой вассал''.* Быть похожим на другого человека. == Примеры антитранзитивных отношений ==* Быть сыном (отцом, бабушкой). * Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д. == См. также ==* [[Определение_отношения|Определение отношения]]* [[Транзитивное_замыкание|Транзитивное замыкание]]* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения)]]* [[Транзитивный_остов|Транзитивный остов]]* [[Отношение_порядка|Отношение порядка]]* [[Отношение_эквивалентности|Отношение эквивалентности]]

Если отношения <math>R, S<== Источники информации ==* [[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:/math> транзитивны, то отношение <math>T = R \cap S</math> тразнитивноwww.hse. Пусть <math>aTb, bTc \rightarrow aRb, aSb, bRc, bSc<ru/data/2010/11/21/1209059687/math>intr. Из doc Развитие понимания транзитивности <math>R, S<и нетранзитивности]* [http://www.smolensk.ru/user/sgma/math> следует <math>aRc, aSc<MMORPH/math>, но из определения пересечения отношений <math>aTc<N-3-html/math>1.htm Бинарные отношения. Отношения эквивалентности] (очень хорошая статья про отношения, что и требовалось доказать.в ней суть раскрыта более подробно)