Изменения

[[Определение отношения|Бинарное отношение]] <tex>R</tex> на [[Множества|множестве]] <tex>X</tex> называется ''транзитивным'', если для любых трёх элементов ''<tex>a, b, c'' </tex> из выполнения отношений <tex> aRb </tex> и <tex> bRc </tex> следует выполнение отношения <tex> aRc </tex>.

Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''транзитивным'''(англ. ''transitive binary relation''), если для <tex>\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc) \Rightarrow ~(aRc)</tex>.

Если это условие соблюдается не для всех троек ''<tex>a, b, c''</tex>, то такое отношение называется нетранзитивным. Например, не для всех троек <tex> a, b, c \in \mathbb{N} </tex> верно, что <tex>~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c) </tex>.

Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''нетранзитивным'''(англ. ''intransitive binary relation''), если <tex>\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow land ~\neg(aRc)</tex>.

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

Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''антитранзитивным'''(англ. ''antitransitive binary relation''), если для <tex>\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)</tex>.

** нестрогое неравенство <tex>\colon ~("\le leqslant ")\;</tex>

* '''[[Отношение эквивалентности|Эквивалентность]]''' <tex>\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;</tex>

* Пищевая цепочка: это отношение не всегда является транзитивным (пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву).* ''Быть предпочтительнее чем''. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз яблокуапельсину.* Быть другом.* Являться коллегой по работе.

* Быть похожим на другого человека.

* Быть сыном (отцом, бабушкой). Но! Можно быть братом (сестрой) {{---}} тогда отношение транзитивное.

== Отношение эквивалентностиСм. Класс эквивалентности также ==Бинарное отношение <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> ~C(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> a \equiv b~(mod ~ m) </tex>* В ''Евклидовой геометрии:''** отношение подобия<tex> ("\thicksim ") </tex>** отношение параллельности<tex>\colon ~ ("\parallel ") </tex>** отношение конгруэнтности<tex>\colon ~ ("\cong ") </tex>* Разбиение многоугольников по количеству вершин* Оношение ''равносильности'' на множестве уравнений* Отношение [[Мощность множестваОтношение_порядка|равномощностиОтношение порядка]] множеств* Отношение ''принадлежать к одному виду'' на множестве животных* Отношение ''жить в одном городе'' на множестве людей == Неэквивалентные отношения ==* Отношения '''[[Частичный порядокОтношение_эквивалентности|частичного порядкаОтношение эквивалентности]]''' не являются симметричными* Отношение ''иметь наибольший общий делитель больше 1'' нетранзитивное. Например, <tex> ~\gcd (2,6) = 2, ~\gcd (3,6) = 3, ~\gcd(2,3) = 1 </tex>* Отношение ''быть родственниками'' на множестве людей нерефлексивное. Человек не может быть родственником самому себе* Разбиение треугольников по свойствам сторон (разносторонние, равнобедренные, равносторонние) не образует классы эквивалентности, так как множество равносторонних треугольников является подмножеством равнобедренных треугольников

* [http[wikipedia://en.wikipedia.org/wiki/Transitive_relation | Wikipedia | {{---}} Transitive relation]]* [http[wikipedia://en.wikipedia.org/wiki/Intransitivity | Wikipedia | {{---}} Intransivity]]* [http[wikipedia://ru.wikipedia.org/wiki/:Отношение_эквивалентности | Wikipedia | {{---}} Отношение эквивалентности]]

* [http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm Бинарные отношения. Отношения эквивалентности] (очень хорошая статья про отношения, в ней суть раскрыта более полноподробно)