3622
правки
Изменения
Добавлена информация про классы и отношения эквивалентности, тема расширена примерами, слегка дополнены источники
== Определение ==
В математике [[Определение отношения|бинарное отношение]] <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 =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''транзитивным''', если для <tex>\forall a, b, c \in X</tex>: <tex>\colon (aRb) \land (bRc) \Rightarrow (aRc)</tex>.
}}
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''нетранзитивным''', если <tex>\exists a, b, c \in X</tex>: <tex>\colon (aRb) \land (bRc) \Rightarrow \neg(aRc)</tex>.
}}
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X</tex> называется '''антитранзитивным''', если для <tex>\forall a, b, c \in X</tex>: <tex>\colon (aRb) \land (bRc) \Rightarrow \neg(aRc)</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>
* Являться коллегой по работе
* Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: ''Вассал моего вассала {{---}} не мой вассал''.
* Быть похожим на другого человека
== Примеры антитранзитивных отношений ==
* Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
* Отношение ''бойцовской силы'' между биологическими видами(1-й вид организмов вытесняет 2-й вид, 2-й вытесняет 3-й, а тот, в свою очередь, вытесняет 1-й). Это относится и к группам людей, использующих разные экономические стратегии.
== Отношение эквивалентности. Класс эквивалентности ==
Бинарное отношение <tex> R </tex> на множестве <tex> X </tex> называется ''отношением эквивалентности'', если оно [[Рефлексивное отношение|рефлексивно]], [[Симметричное отношение|симметрично]] и [[Транзитивное отношение|транзитивно]]. На письме обозначается, как <tex>\thicksim{,} \thickapprox{,} ={,} \equiv{,} \Leftrightarrow{.} </tex> Примером отношения эквивалентности может быть отношение ''иметь одинаковый рост'' на множестве людей.
{{Определение
|definition =
Бинарное отношение <tex>\thicksim</tex>, заданное на множестве <tex>X</tex> называется '''отношение эквивалентности''', если
* <tex> \forall a \in X\colon (a\thicksim a) </tex>
* <tex> \forall a, b \in X\colon (a\thicksim b) \Rightarrow (b\thicksim a)</tex>
* <tex> \forall a, b, c \in X\colon (a\thicksim b) \land (b\thicksim c) \Rightarrow (a\thicksim c)</tex>
}}
С ''отношением эквивалентности'' тесно связано разбиение множества на классы.
{{Определение
|definition =
Система непустых подмножеств <tex> \{ M_1, M_2,...,M_n\} </tex> множества <tex> M </tex> называется '''разбиением''' этого множества, если <tex> M = M_1 \cup M_2 \cup ... \cup M_n </tex> и при <tex> i \ne j\colon ~M_i \cap M_j = \varnothing{.} </tex> Сами множества <tex>M_1, M_2,...,M_n</tex> называются '''классами''' данного разбиения.
}}
''Классом эквивалентности'' <tex> C(a) </tex> элемента ''a'' называется подмножество элементов эквивалентных ''a''. Из определения следует, что, если <tex> b \in C(a) </tex>, то <tex> С(a) = C(b) </tex>. Класс эквивалентности элемента ''a'' обозначают: <tex> [a],~ a/^{\sim} , ~\overline{a} </tex>.
{{Определение
|definition =
Подмножество элементов множества <tex> X </tex> эквивалентных данному элементу <tex> a </tex> называется его '''классом эквивалентности''', т. е. <tex> [a] = \{ b ~ \in ~ X \mid a \thicksim b \}.</tex>
}}
Пусть <tex> a, b \in X </tex>, тогда либо <tex> [a] \cap [b] = \emptyset </tex>, либо <tex> [a] = [b] </tex>. Таким образом отношение эквивалентности порождает разбиение множества на ''классы эквивалентности''. Семейство всех классов эквивалентности образует множество, называемое ''фактор-множеством'', и обозначается <tex> X/^{\thicksim} </tex>.
== Примеры отношений эквивалентности ==
* '''Равенство''' <tex> ("=") </tex> - классический пример отношения эквивалентности на любом множестве, в т. ч. [[Вещественные числа|вещественных чисел]]
* Равенство по ''модулю:'' <tex> a \equiv b(mod ~ m) </tex>
* В ''Евклидовой геометрии:''
** отношение подобия<tex> ("\thicksim ") </tex>
** отношение параллельности<tex> ("\parallel ") </tex>
** отношение конгруэнтности<tex> ("\cong ") </tex>
* Разбиение многоугольников по количеству вершин
* Оношение ''равносильности'' на множестве уравнений
* Отношение [[Мощность множества|равномощности]] множеств
* Отношение ''принадлежать к одному виду'' на множестве животных
* Отношение ''жить в одном городе'' на множестве людей
== Неэквивалентные отношения ==
* Отношения '''[[Частичный порядок|частичного порядка]]''' не являются симметричными
* Отношение ''иметь наибольший общий делитель больше 1'' - нетранзитивное. Например, <tex> \gcd (2,6) = 2, \gcd (3,6) = 3, \gcd(2,3) = 1 </tex>
* Отношение ''быть родственниками'' на множестве людей - нерефлексивное. Человек не может быть родственником самому себе
* Разбиение треугольников по свойствам сторон(разносторонние, равнобедренные, равносторонние) не образует классы эквивалентности, так как множество равносторонних треугольников является подмножеством равнобедренных треугольников
== Источники информации ==
* [http://en.wikipedia.org/wiki/Transitive_relation Wikipedia | Transitive relation]
* [http://en.wikipedia.org/wiki/Intransitivity Wkipedia Wikipedia | Intransivity]* [http://ru.wikipedia.org/wiki/Отношение_эквивалентности 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 Бинарные отношения. Отношения эквивалентности] (очень хорошая статья про отношения, в ней суть раскрыта более полно)
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения]]
