Транзитивное отношение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Свойства)
(Добавлены определения нетранзитивного и антитранзитивного отношения, добалены также примеры и источники информации.)
Строка 1: Строка 1:
 +
== Определение ==
 +
В математике [[Определение отношения|бинарное отношение]] <tex>R</tex> на множестве <tex>X</tex> называется ''транзитивным'', если для любых трёх элементов ''a, b, c'' из выполнения отношений <tex> aRb </tex> и <tex> bRc </tex> следует выполнение отношения <tex> aRc </tex>. Свойство ''транзитивности'' на отношениях в [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графе]] означает, что существоние пути из вершины ''a'' в ''b'' и из ''b'' в ''с'' влечёт существование пути из ''a'' в ''с''. Формально записывается <tex> (a \mapsto b) \land (b \mapsto c) \Rightarrow (a \mapsto c) </tex>. Также это можно понимать, что вершины графа ''a, b, c'' находятся в одной [[Отношение связности, компоненты связности|компоненте связности]].
 
{{Определение
 
{{Определение
|definition=
+
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''транзитивным''', если для <tex>\forall a, b, c \in X</tex> выполняется <tex>aRb, bRc \Rightarrow aRc</tex>}}
+
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''транзитивным''', если для <tex>\forall a, b, c \in X</tex>: <tex>(aRb) \land (bRc) \Rightarrow (aRc)</tex>.
 +
}}
  
 +
Если это условие соблюдается не для всех троек ''a, b, c'', то такое отношение называется нетранзитивным. Например, не для всех троек <tex> a, b, c \in N </tex> верно, что <tex> (a \nmid b) \land (b \nmid c) \Rightarrow (a \nmid c) </tex>.
 +
{{Определение
 +
|definition =
 +
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''нетранзитивным''', если <tex>\exists a, b, c \in X</tex>: <tex>(aRb) \land (bRc) \Rightarrow \neg(aRc)</tex>.
 +
}}
 +
 +
Существует более "сильное" свойство {{---}} '''антитранзитивность'''. Под этим термином понимается, что для любых троек ''a, b, c'' отсутствует транзитивность. Антитранзитивное отношение {{---}} отношение '''победить''' в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить.
 +
{{Определение
 +
|definition =
 +
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''антитранзитивным''', если для <tex>\forall a, b, c \in X</tex>: <tex>(aRb) \land (bRc) \Rightarrow \neg(aRc)</tex>.
 +
}}
 
== Свойства ==
 
== Свойства ==
  
 
* Если отношение <tex>R</tex> транзитивно, то обратное отношение <tex>R^{-1}</tex> также транзитивно. Пусть <tex>aR^{-1}b, bR^{-1}c</tex>, но по определению обратного отношения <tex>cRb, bRa</tex>. Так как <tex>R</tex> транзитивно, то <tex>cRa</tex> и <tex>aR^{-1}c</tex>, что и требовалось доказать.
 
* Если отношение <tex>R</tex> транзитивно, то обратное отношение <tex>R^{-1}</tex> также транзитивно. Пусть <tex>aR^{-1}b, bR^{-1}c</tex>, но по определению обратного отношения <tex>cRb, bRa</tex>. Так как <tex>R</tex> транзитивно, то <tex>cRa</tex> и <tex>aR^{-1}c</tex>, что и требовалось доказать.
 
* Если отношения <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>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>(a < b), (b < c) \Rightarrow (a < c)\;</tex>
 +
** ''нестрогое неравенство'' <tex>\le\;</tex>
 +
** '''включение подмножества:'''
 +
*** ''строгое подмножество'' <tex>\subset\;</tex>
 +
*** ''нестрогое подмножество'' <tex>\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>(a = b), (b = c) \Rightarrow (a = c)\;</tex>
 +
* '''Эквивалентность:''' <tex>(a \Leftrightarrow b), (b \Leftrightarrow c) \Rightarrow (a \Leftrightarrow c)\;</tex>
 +
* '''Импликация:''' <tex>(a \Rightarrow b), (b \Rightarrow c) \Longrightarrow (a \Rightarrow c)\;</tex>
 +
* '''Параллельность:''' <tex>(a \parallel b), (b \parallel c) \Rightarrow (a \parallel c)\;</tex>
 +
* Отношение ''подобия'' геометрических фигур
 +
* Являться предком
 +
 
 +
== Примеры нетранзитивных отношений ==
 +
* Пищевая цепочка: это отношение не всегда является транзитивным(пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву, контрпример {{---}} люди едят кроликов, кролики едят морковь, но люди тоже едят морковь)
 +
* Быть предпочтительнее чем. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз яблоку.
 +
* Быть другом
 +
* Являться коллегой по работе
 +
* Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: ''Вассал моего вассала {{---}} не мой вассал''.
 +
 
 +
== Примеры антитранзитивных отношений ==
 +
* Быть сыном(отцом, бабушкой). Но! Можно быть братом(сестрой) {{---}} тогда отношение транзитивное.
 +
* Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
 +
* Отношение ''бойцовской силы'' между биологическими видами(1-й вид организмов вытесняет 2-й вид, 2-й вытесняет 3-й, а тот, в свою очередь, вытесняет 1-й). Это относится и к группам людей, использующих разные экономические стратегии.
 +
 
 +
== Источники информации ==
 +
* [http://en.wikipedia.org/wiki/Transitive_relation Wikipedia | Transitive relation]
 +
* [http://en.wikipedia.org/wiki/Intransitivity Wkipedia | Intransivity]
 +
* [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 Развитие понимания транзитивности и нетранзитивности]
  
== Примеры ==
+
[[Категория: Дискретная математика и алгоритмы]]
Следующие отношения являются транзитивными:
+
[[Категория: Отношения]]
* отношение <tex>\le</tex> на множестве вещественных чисел
 
* отношение <tex>\subset</tex> на множестве наборов
 
* отношение параллельности на множестве прямых
 

Версия 09:40, 15 октября 2011

Определение

В математике бинарное отношение [math]R[/math] на множестве [math]X[/math] называется транзитивным, если для любых трёх элементов a, b, c из выполнения отношений [math] aRb [/math] и [math] bRc [/math] следует выполнение отношения [math] aRc [/math]. Свойство транзитивности на отношениях в графе означает, что существоние пути из вершины a в b и из b в с влечёт существование пути из a в с. Формально записывается [math] (a \mapsto b) \land (b \mapsto c) \Rightarrow (a \mapsto c) [/math]. Также это можно понимать, что вершины графа a, b, c находятся в одной компоненте связности.

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X[/math] называется транзитивным, если для [math]\forall a, b, c \in X[/math]: [math](aRb) \land (bRc) \Rightarrow (aRc)[/math].


Если это условие соблюдается не для всех троек a, b, c, то такое отношение называется нетранзитивным. Например, не для всех троек [math] a, b, c \in N [/math] верно, что [math] (a \nmid b) \land (b \nmid c) \Rightarrow (a \nmid c) [/math].

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X[/math] называется нетранзитивным, если [math]\exists a, b, c \in X[/math]: [math](aRb) \land (bRc) \Rightarrow \neg(aRc)[/math].


Существует более "сильное" свойство — антитранзитивность. Под этим термином понимается, что для любых троек a, b, c отсутствует транзитивность. Антитранзитивное отношение — отношение победить в турнирах «на вылет»: если A победил игрока B, а B победил игрока C, то A не играл с C, следовательно, не мог его победить.

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X[/math] называется антитранзитивным, если для [math]\forall a, b, c \in X[/math]: [math](aRb) \land (bRc) \Rightarrow \neg(aRc)[/math].

Свойства

  • Если отношение [math]R[/math] транзитивно, то обратное отношение [math]R^{-1}[/math] также транзитивно. Пусть [math]aR^{-1}b, bR^{-1}c[/math], но по определению обратного отношения [math]cRb, bRa[/math]. Так как [math]R[/math] транзитивно, то [math]cRa[/math] и [math]aR^{-1}c[/math], что и требовалось доказать.
  • Если отношения [math]R, S[/math] транзитивны, то отношение [math]T = R \cap S[/math] транзитивно. Пусть [math]aTb, bTc \Rightarrow aRb, aSb, bRc, bSc[/math]. Из транзитивности [math]R, S[/math] следует [math]aRc, aSc[/math], но из определения пересечения отношений получаем [math]aTc[/math], что и требовалось доказать.
  • Из последнего свойства следует, что пересечение любого количества транзитивных отношений транзитивно. Пересечение всех транзитивных отношений на множестве называется транзитивным замыканием.

Примеры транзитивных отношений

  • Отношения частичного порядка:
    • строгое неравенство: [math](a \lt b), (b \lt c) \Rightarrow (a \lt c)\;[/math]
    • нестрогое неравенство [math]\le\;[/math]
    • включение подмножества:
      • строгое подмножество [math]\subset\;[/math]
      • нестрогое подмножество [math]\subseteq\;[/math]
    • делимость:
      • [math](a \mid b), (b \mid c) \Rightarrow (a \mid c)\;[/math]
      • [math](a \,\vdots\, b), (b \,\vdots\, c) \Rightarrow (a \,\vdots\, c)\;[/math]
  • Равенство: [math](a = b), (b = c) \Rightarrow (a = c)\;[/math]
  • Эквивалентность: [math](a \Leftrightarrow b), (b \Leftrightarrow c) \Rightarrow (a \Leftrightarrow c)\;[/math]
  • Импликация: [math](a \Rightarrow b), (b \Rightarrow c) \Longrightarrow (a \Rightarrow c)\;[/math]
  • Параллельность: [math](a \parallel b), (b \parallel c) \Rightarrow (a \parallel c)\;[/math]
  • Отношение подобия геометрических фигур
  • Являться предком

Примеры нетранзитивных отношений

  • Пищевая цепочка: это отношение не всегда является транзитивным(пример — волки едят оленей, олени едят траву, но волки не едят траву, контрпример — люди едят кроликов, кролики едят морковь, но люди тоже едят морковь)
  • Быть предпочтительнее чем. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз яблоку.
  • Быть другом
  • Являться коллегой по работе
  • Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: Вассал моего вассала — не мой вассал.

Примеры антитранзитивных отношений

  • Быть сыном(отцом, бабушкой). Но! Можно быть братом(сестрой) — тогда отношение транзитивное.
  • Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
  • Отношение бойцовской силы между биологическими видами(1-й вид организмов вытесняет 2-й вид, 2-й вытесняет 3-й, а тот, в свою очередь, вытесняет 1-й). Это относится и к группам людей, использующих разные экономические стратегии.

Источники информации